Insertion sort using C

Question

Objective: Use insertion sort to sort an array of pointers from descending order. At the same time when the array of pointers are being sorted the array that the pointers are pointing too will sort with it as well.

void insert(int **table, int row)

{

//  Local Declaration

    int temp, current, walker;

    //  Statement
    for(current = 1; current < row; current++)
    {
        temp = *table[current];
        walker = current - 1;
        while(walker >= 0 && temp > *table[walker])
        {
            *table[walker + 1] = *table[walker];
            walker--;
        }
        *table[walker + 1] = temp;
    }

return;

}

Sample Output:

Before insertion sort:

1 -66

2 51 0

3 68 61 37

4 91 80 31 -9

5 59 42 -15 -19 -75

After insertion sort:

5 -66 -59 134218571 4132481 0

4 51 0 31 131357707

3 68 61 37

2 91 80

1 59

Should I create a copy of each array and when I use insertion sort swap the arrays around or is there a more efficient way to complete the task?

Complete Program:

/*********************************************************************************
** CIS 15BG                                                           Winter, 2013
***************
**
** Homework 3:
**        Pointers, Dynamic Allocation of Memory, Ragged Arrays, and Sorting
**
**********************************************************************************

  This program creates a dynamic table that can store a ragged 2D array
  of integers, sorts each row then rearranges them by length

***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#ifdef _MSC_VER
#include <crtdbg.h>  // needed to check for memory leaks (Windows only!)
#endif

#define MEM_ERROR printf("Not enough memory\n")

int** getRow(int *row);
void valiRow(int *row);
void getSize(int **table, int row);
int  valiSize(int size);
void fillTable(int **table, int row);
void bubble(int **table, int row);
void insert(int **table, int row);
void save(int **table, int row);

int main (void)
{
    //  Local Declaration
    int **table;
    int row;

    //  Statement
    table = getRow(&row);
    getSize(table, row);
    fillTable(table, row);
    bubble(table, row);
    insert(table, row);

    #ifdef _MSC_VER
    printf( _CrtDumpMemoryLeaks() ? "Memory Leak\n" : "No Memory Leak\n");
    #endif
    return 0;

}// main

/* getRow */
int** getRow(int *row)
{
    //  Local Declaration
    int **table;

    //  Statement
    printf("Please enter the number of rows (1-10): ");
    scanf("%d", &*row);

    valiRow(&*row);

    table =(int**)calloc(*row+1, sizeof(int));
    if(table == NULL)
        MEM_ERROR, exit(100);

    return table;
}

/* valiRow */
void valiRow(int *row)
{
    //  Statement
    while(*row > 10 || *row < 1)
    {
        while(getchar() != '\n')
        ;
        printf("Please enter a number between (1-10): ");
        scanf("%d", &*row);
    }

    return;
}
/* getSize */
void getSize(int **table, int row)
{
    //  Local Declaration
    int i, size;

    //  Statement
    for(i = 0; i < row; i++)
    {
        printf("<ROW %2d> Please enter a size (1-15): ", i + 1);
        scanf("%d", &size);

        size = valiSize(size);

        table[i] = (int*)calloc(size + 1, sizeof(int));
        table[i][0] = size;
    }

    if(table == NULL)
        MEM_ERROR, exit(101);

    return;
}

/* valiSize */
int valiSize(int size)
{
    //  Statement
    while(size > 15 || size < 1)
    {
        while(getchar() != '\n')
        ;
        printf("Please enter a valid size (1-15): ");
        scanf("%d", &size);
    }

    return size;
}

/* fillTable */
void fillTable(int **table, int row)
{
    //  Local Declaration
    int random, i, j;

    //  Statement
    srand(time(NULL));
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < (table[i][0]) + 1; j++)
        {
            random = -99 + rand() % 199;
            table[i][j + 1] = random;
        }
    }

    return;
}

/* bubble */
void bubble(int **table, int row)
{
    //  Local Declaration
    int current, last, walker, temp;
    int i, j;
    //  Statment

    for(i = 0; i < row; i++)
    {
        last = table[i][0];
        for(current = 1; current < last; current++)
        {
            for(walker = last; walker > current; walker--)
            {
                if(table[i][walker] > table[i][walker - 1])
                {
                    temp = table[i][walker];
                    table[i][walker] = table[i][walker - 1];
                    table[i][walker - 1] = temp;
                }
            }
        }
    }

    return;
}

/* insert */
void insert(int **table, int row)
{
    //  Local Declaration
    int temp, current, walker;

    //  Statement
    for(current = 1; current < row; current++)
    {
        temp = *table[current];
        walker = current - 1;
        while(walker >= 0 && temp > *table[walker])
        {
            *table[walker + 1] = *table[walker];
            walker--;
        }
        *table[walker + 1] = temp;
    }

    return;
}

Answer 1

memmove() is your friend:

#include <stdio.h>
#include <string.h> /* for memmove() */


void insertion_sort(int **table, size_t cnt);
void insertion_sort(int **table, size_t cnt)
{
    int *tmp;
    size_t src,dst;

    for(src = 1; src < cnt; src++)
    {
        tmp = table[src];
        for(dst=src; dst-- > 0 && *tmp < *table[dst]; ) {;}
                /* when we get out of the loop, 
                ** table[dst] is the element BEFORE our insertion point,
                ** so re-increment it to point at the insertion point */
        if (++dst == src) continue;

        memmove(table+dst+1,table+dst, (src-dst) * sizeof  table[0] );
        table[dst] = tmp;
    }

return 0;
}

int array[5] = { 11,12,13,14,15};
int *ptrs[5] = { array+3, array+0, array+4, array+2, array+1 };
int main (void)
{
size_t idx;
insertion_sort(ptrs, 5);

for (idx=0; idx < 5; idx++) {
        printf  ("[%zu] : %p: %d\n"
                , idx, (void*) ptrs[idx], *ptrs[idx]
                );

        }
return 0;
}

Answer 2

You should swap pointers in insert function swapping values of first elements(size) doesn't mean swapping remaining elements of the arrays.

void insert(int **table, int row)
{
    //  Local Declaration
    int *temp, current, walker;

    //  Statement
    for(current = 1; current < row; current++)
    {
        temp = table[current];
        walker = current - 1;
        while(walker >= 0 && *temp > *table[walker])
        {
            table[walker + 1] = table[walker];
            walker--;
        }
        table[walker + 1] = temp;
    }

    return;
}