C Language Practice: Sorting - Insertion Sort

Insertion Sort

What is insertion sort?

We have an easy train of thought for insertion sort, but this sorting method is a bit slow. What we do in insertion sort is we pick up the second element, and we compare it with the first element. Then we pick the next(third) element and we keep comparing it with the elements before it(the second and first) until we meet an element that is smaller or equal to it. We then pick up our third element, move the list behind forward, then we insert it. We'll keep doing this until we sorted the whole list.

What do we need in code in order to do insertion sort?

Well, we'll need these stuff:

• First, we'll need some variables (definitely (we did this multiple times before! Surely we'll need variables~)).
  • $Temp$ will help us push and insert our element.
  • $s$ and $n$ will help us do the element comparing.

Bought (Got) everything (the elements) from the supermarket (you can ignore these)? Okay then!

• Second, we'll need our for loop that keeps us running nicely until we've sorted the whole list.
• Now onto the things we need in the for loop!
  • A while loop that compares using $s$ and $n$...
  • ... and a for loop and $temp$ defining to help us push the list forward!

• don't forget to return the array!

#include <stdio.h>

int insertion_sort(int array[], int total)
{
    int temp, s, n;
    
    for (int i = 0; i < total; i++)
    {
        s = i;
        n = i;
        while (array[s] < array[n - 1] && n != 0)
        {
            n--;
        }
        temp = array[s];
        for (int j = s; j > n; j--)
        {
            array[j] = array[j - 1];
        }
        array[n] = temp;
    }

    return array;
}

int main(void)
{
    int total;
    printf("how many numbers do you want to enter?\n");
    scanf("%d", &total);
    int array[total];
    printf("enter your number list here\n");
    for (int i = 0; i < total; i++)
    {
        scanf("%d", &array[i]);
    }

    insertion_sort(array, total);

    printf("the sorted list looks like this.\n");
    for (int f = 0; f < total; f++)
    {
        printf("%d ", array[f]);
    }
    printf("\n");

    return 0;
}

Comment: You can try the code(and every other in the other websites at code). It works well!