How to correctly implement an insertion sort algorithm in a 2D array?

Question

I need to sort the columns of my 2D array based on the first row of the array. This is my 2d array before sorting:

cargo

AFADA
DAFGF
DXAFA
DDFFX
GFXF

and this is the image of my 2D array:

acrgo

FAADA
ADFGF
XDAFA
DDFFX
FGXF

The correct output looks like this

acgor

FADAA
ADGFF
XDFAA
DDFXF
FGF X

. This is the code of my function to sort the array using insertion sort algorithm

void sort(char** newTable, int row, int col) {
    for (int top = 1; top < col; col++) {
        char item = newTable[0][top];
        int i = top;
        while (i > 0 && item < newTable[0][i - 1]) {
            for (int j = 0; j < row + 1; j++) {
                char temp = newTable[j][i];
                newTable[j][i] = newTable[j][i - 1];
                newTable[j][i - 1] = temp;
            }
            i--;
         }
         newTable[0][i] = item;
     }
 }

I called the function like this

    sort(newTable, row, strlen(key));

here, key is the string 'cargo'

The definition of newTable:

char** newTable = (char**)calloc(row + 1, sizeof(char*));
    for (int i = 0; i < row + 1; i++) {
        newTable[i] = (char*)calloc(strlen(key), sizeof(char));
    }

I am trying to sort the first row alphabetically and shift the columns below it accordingly — player_pi
– player_pi, Commented Jun 10, 2020 at 12:49
If the spacing in the last line is to be ignored, it is better to say that in the post, perhaps just to the right of the text of that last line //ignore space or just don't show the space in your data: FGFX. — ryyker
– ryyker, Commented Jun 10, 2020 at 13:05
Can you also include a short snippet showing how you call this function, i.e. show the input, and how you read the results. By the way, to get results you will need to pass the address of the 2D array to allow changes made in the function to be retrieved, requiring char** newTable to become char ***newTable in the prototype. Then called as (for example) sort(&some2DArray, 6,5); — ryyker
– ryyker, Commented Jun 10, 2020 at 13:11
i added the snippet on how i called the function. I think that there is some error in my implementation of the sorting algorithm cos it is sorting it partially correct — player_pi
– player_pi, Commented Jun 10, 2020 at 13:21

Serge Ballesta · Accepted Answer · 2020-06-10 14:29:24Z

1

newTable is indeed an array of pointers and not a 2D array, so using char **newTable makes sense.

The major error is close to a typo: in the first for loop of sort, you increment col when you want to increment top. And the last line newTable[0][i] = item; is useless.

This should work (even if the loop for (int j = 0; j < row + 1; j++) suggests that row is not the number of rows in newTable but only the number of *additional rows):

void sort(char** newTable, int row, int col) {
    for (int top = 1; top < col; top++) {
        char item = newTable[0][top];
        int i = top;
        while (i > 0 && item < newTable[0][i - 1]) {
            for (int j = 0; j < row + 1; j++) {
                char temp = newTable[j][i];
                newTable[j][i] = newTable[j][i - 1];
                newTable[j][i - 1] = temp;
            }
            i--;
         }
     }
 }

answered Jun 10, 2020 at 14:29

Serge Ballesta

150k13 gold badges137 silver badges267 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ryyker Over a year ago

Will this actually allow caller to see the changes made in the array? Doesn't caller have to pass the address of, therefore requring prototype to use char ***array ?

Serge Ballesta Over a year ago

@ryyker: You have to pass a pointer if you want to build a brand new array in the function. Here you just change elements inside the really same array, so you do not need an additional indirection level.

Collectives™ on Stack Overflow

How to correctly implement an insertion sort algorithm in a 2D array?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related