Insertion Sort Algorithm

Question

I am reading Cormen Introduction To Algorithms book and i'm trying to translate the pseudocode of Insertion Sort example into real C code.

The problem is that the algorithm i wrote seems not working and i cannot understand why; for instance when i insert something like: {4, 3, 2, 1} the output still be the same and when i insert something like {8, 9, 1, 12, 3} the output become {8, 9, 1, 12, 3} which doesn't make any sense.

Someone can find what i did wrong?
This is the code i wrote:

#include <stdio.h>

void insertionSort(int *Arr, unsigned int size);

int main(void) {
//The size of the array
unsigned int size = 0;

printf("Insert how many elements you want to sort(min 2): ");
scanf_s("%d", &size);
//Check if the value are higher than 1
while (size < 2) {
    printf("\nPlease, choose a higher value: ");
    scanf_s("%d", &size);
}
//Let's define the array with the choosen size
//The array is allocated dynamically on the heap of the memory
int *Arr;
Arr = calloc(size, sizeof(int));
//Ask the elements
printf("Insert %d elements:\n", size);
for (int i = 0; i < size; i++) {
    printf("Insert the %d element: ", i+1);
    scanf_s("%d", &Arr[i]);
}
//Print the result
printf("Sorted array: \n");
for (int i = 0; i < size; i++)
    printf("%d\n", Arr[i]);
free(Arr);
return 0;
}

void insertionSort(int *Arr, unsigned int size) {
for (int j = 1; j < size; j++) { //Start with the 2nd element of the array
    int key = Arr[j]; //the current element of A[j] is stored in key
    int i = j;
    while ((i >= 1) && (Arr[i - 1] > key)) {
        Arr[i] = Arr[i - 1];
        i--;
    }
    Arr[i] = key; //at position I(decreased by 1) is stored Key.
 }
}

That single line Arr[i] = Arr[i - 1]; doesn't look like a swap to me, which is what insertion sort does. — meowgoesthedog
– meowgoesthedog, Commented Mar 9, 2018 at 17:24

Paul92 · Accepted Answer · 2018-03-09 17:28:13Z

1

You are not calling the insertionSort function. Just adding:

for (int i = 0; i < size; i++) {
    printf("Insert the %d element: ", i+1);
    scanf_s("%d", &Arr[i]);
}

insertionSort(Arr, size);

//Print the result
printf("Sorted array: \n");

Made it work for me.

Note that you alse have to include stdlib.h for calloc.

answered Mar 9, 2018 at 17:28

Paul92

9,1121 gold badge29 silver badges40 bronze badges

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

Collectives™ on Stack Overflow

Insertion Sort Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related