Insertion Sort with a 2D pointer array by certain column in C

Question

Im currently struggling to implement a insertion sort algorithm for a 2D pointer array.
NO Qsort solutions please, it needs to be old school Here is my code

void insertionSort(double **arr, int rows,int c)
{
    double *temp;
    int i, j;
    for (i = 1; i < rows; i++) {
        temp = *(arr+i);
        j = i - 1;

        /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
        while (j >= 0 && arr[j][c] > arr[i][c]) {
            int r = j + 1;
            *(arr+r) = *(arr+j);
            j = j - 1;
        }
        int t= j + 1;
        *(arr+t) = temp;
    }
}

heres where i call it(rows = 3, the value 4 says which column to sort according to):

insertionSort(student,rows,4);

It needs to sort every row according to the value in the last column of each row: example : sort by column 3

input
10 11 71
71 25 65
98 42 16

output:
98 42 16
71 25 65
10 11 71\

Any help would be appreciated since this is due this week :)

Answer 1

I got my answer to my question, just had to point to the c column using pointers in my while loop as a comparable(instead of arr[i][c] it became *(temp+c):

void insertionSort(double **arr, int rows,int c)
{
    double *temp;
    int i, j;
    for (i = 1; i < rows; i++) {
        temp = *(arr+i);
        j = i - 1;

        /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
        
        while (j >= 0 && arr[j][c] > *(temp+c) ) {
            int r = j + 1;
            *(arr+r) = *(arr+j);
            j = j - 1;
        }
        int t= j + 1;
        *(arr+t) = temp;
    }
}

tx for help everyone

Answer 2

Presuming arr is an allocated block of pointers where each pointer holds the address of an allocated block of double, you simply need to compare by the last column in each block of double and swap pointers in arr to sort. Your insertionSort() function can be reduced to:

void insertionSort (double **arr, int rows, int cols)
{
    for (int i = 0; i < rows; i++) /* insertion sort of a by last col */
        for (int j = i; j > 0 && arr[j][cols-1] < arr[j-1][cols-1]; j--) {
            double *tmp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = tmp;
        }
}

(note: c has been changed to cols)

This will not work with a 2D array. With a 2D array you must save and copy rows instead of pointers with a loop or memcpy(). This all presumes your double **arr is correct and you have allocated pointers and allocated blocks for the double and are now sorting be the last double in each row of arr. An example would be:

#include <stdio.h>
#include <stdlib.h>

void insertionSort (double **arr, int rows, int cols)
{
    for (int i = 0; i < rows; i++) /* insertion sort of a by last col */
        for (int j = i; j > 0 && arr[j][cols-1] < arr[j-1][cols-1]; j--) {
            double *tmp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = tmp;
        }
}

void prnrowscols (size_t rows, size_t cols, double **arr)
{
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++)
            printf (j ? " %4g" : "%4g", arr[i][j]);
        putchar ('\n');
    }
}

int main (void) {
    
    double tmp[][3] = { {10, 11, 71},
                        {71, 25, 65},
                        {98, 42, 16} },
           **arr = NULL;
    size_t  rows = sizeof tmp / sizeof *tmp,
            cols = sizeof *tmp / sizeof **tmp;
    
    if (!(arr = malloc (rows * sizeof *arr))) {
        perror ("malloc-arr");
        return 1;
    }
    
    for (size_t i = 0; i < rows; i++) {
        if (!(arr[i] = malloc (cols * sizeof *arr[i]))) {
            perror ("malloc-arr[i]");
            return 1;
        }
        for (size_t j = 0; j < cols; j++)
            arr[i][j] = tmp[i][j];
    }
    
    puts ("orignal array:");
    prnrowscols (rows, cols, arr);
    
    insertionSort (arr, rows, cols);
    
    puts ("\nsorted array:");
    prnrowscols (rows, cols, arr);
    
    for (size_t i = 0; i < rows; i++)       /* free memory */
        free (arr[i]);
    free (arr);
}

Example Use/Output

$ ./bin/inssort_ptr2ptr
orignal array:
  10   11   71
  71   25   65
  98   42   16

sorted array:
  98   42   16
  71   25   65
  10   11   71

Look things over and let me know if you have further questions.