Insertion Sort C programming

Question

Since this year I'm starting studying C programming at university. In particular today I was trying to understand the insertion sort. I wrote this code that is perfectly working:

void insertionSort (int v[], int s) 
{
    int i;
    int j;
    int value;

    for (i = 1; i < s; i++)
    {
        value = v[i];

        for (j = i - 1; (j >= 0) && (value < v[j]); j --)
        {
            v[j + 1] = v[j];           
        }
        v[j + 1] = value;               // why v[j+1]?
     }                          
}

My question is about the last code line: v[j + 1] = value. If I understand correctly, j (that decreases every time), at the end of the for cycle, has a value of -1 and that's why is correct to write v[j + 1] = value. Am I right or am I missing something? Really thanks for anybody who wants to help me by explaining me better.

Walton Lee · Accepted Answer · 2017-05-27 22:45:43Z

The way you have your code setup right now, you need v[j + 1] because j will always be one before where you want to insert.

For example:

int v[6] = {1, 34, 2, 50, 4, 10}

s = sizeof(v) / sizeof(v[0]) = 6

Stepping through your code:

i = 1, j = 0
value = v[i] = 34
34 < 1 is false so it doesn't go into the inner for loop
v[j + 1] = 34 which is right where 34 should be
Looping your entire code a second time: value = 2, j = 1, i = 2
Both conditions are met where j = 1 && 2 < 34 and you go into your inner loop
Since you already stored v[2] earlier when you did value = v[i], v[2] = 34 at this point is where you decrease j by 1 making j = 0

Looking at your array, it looks like this: 1, 34, 34

The inner for loop will try to loop again but fail the second check
At this point, j is 0 and when you do v[j + 1] = value, you're storing value (2) in its proper place.
Your array at this point looks like 1, 2, 34

So again, the significance of v[j + 1] is to insert in the correct place. If the value is already in the correct place than you swap with itself.

Seanghay · Accepted Answer · 2017-05-27 18:47:52Z

2

This is the process of Insertion Sort. It will swap if the numbers are not ordered.

answered May 27, 2017 at 18:47

Seanghay

1,0861 gold badge11 silver badges24 bronze badges

Comments

Henri · Accepted Answer · 2017-05-27 20:12:36Z

Over here you can find an visualized example: https://visualgo.net/en/sorting

Here you have an example in C:

#include <stdio.h>

int main()
{
  int n, array[1000], c, d, t;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++) {
    scanf("%d", &array[c]);
  }


  // Insertion Sort
  for (c = 1 ; c <= n - 1; c++) {
    d = c;

    while ( d > 0 && array[d] < array[d-1]) {
      t          = array[d];
      array[d]   = array[d-1];
      array[d-1] = t;

      d--;
    }
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c <= n - 1; c++) {
    printf("%d\n", array[c]);
  }

  return 0;
}

mark first element as sorted

for each unsorted element

'extract' the element

for i = lastSortedIndex to 0

if currentSortedElement > extractedElement

move sorted element to the right by 1

else: insert extracted element

Collectives™ on Stack Overflow

Insertion Sort C programming

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related