CODEWITHSUNDEEP
calgorithmsortinginsertion-sort
user15033416
user15033416

Reputation:

Trying to implement insertion sort inc

I'm trying to implement insertion sort but I don't seem to be able to correctly swap the values into their right place.

Here's what I have so far:

void insertion(int ar[], int n) {
    for (int i = 1; i < n; i++) {
        int temp = ar[i];
        int j = i;
        while (ar[j - 1] > ar[i] && (j - 1) >= 0) {
            ar[i] = ar[j - 1];
            ar[j - 1] = temp;
        }
    }
}

Upvotes: 1

Views: 104

Answers (1)

dreamcrash
dreamcrash

Reputation: 51453

This source summarizes the steps of the insertion-sort algorithm as follows:

Algorithm : To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

The first step you got it right:

void insertion(int ar[], int n) {
    for (int i = 1; i < n; i++) {
        // ..
    }
}

however you completely miss the second step, and your while loop:

int j = i;
while (ar[j - 1] > ar[i] && (j - 1) >= 0) {
    ar[i] = ar[j - 1];
    ar[j - 1] = temp;
}

has some issues, namely 1) it is stuck in an infinite loop because the variable j is never decremented; 2) its conditionals should be swapped, so instead of ar[j - 1] > ar[i] && (j - 1) >= 0 it should be (j - 1) >= 0 && ar[j - 1] > ar[i]. Otherwise, you would be accessing the position -1 of the array ar

SPOILER

A possible implementation of the insertion sort could look like:

void insertionSort(int arr[], int n)
{
    int j = 0;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        for (j = i - 1; j >= 0 && arr[j] > key;) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Lets us see how it works with the input [8, 6, 4, 20, 10] (the key is represented by '()')

  1. i = 1, j = 0, key = 6; In the inner loop [<8>, (6), 4, 20, 10]; 6 < 8 true arr[j + 1] = arr[j]; which leads to [<8>, (8), 4, 20, 10]. j = -1, the inner loop stops and arr[j + 1] = key; turns the array into [(6), 8, 4, 20, 10].

At this point, we know that the smallest element is in the first position. Therefore, we do not have to consider it in the next iterations

  1. [6, <8>, (4), 20, 10]; 4 < 8 true so let's move 4 before 6; -> [(4), 6, 8, 20, 10];

At this point, we know that the two smallest elements are in the first two positions. Therefore, we do not have to consider them in the next iterations

  1. [4, 6, <8>, (20), 10]; 20 < 8 false so let's move on;

At this point, we know that the three smallest elements are in the first three positions. Therefore, we do not have to consider them in the next iterations

  1. [4, 6, 8, <20>, (10)]; 10 < 20 true so let us move 20 before 10 -> [4, 6, 8, (10), 20];

At this point, we know that the four smallest elements are in the first four positions. Therefore, we do not have to consider them in the next iterations

  1. i < n is false, we exit the outer loop and the array is sorted.

Upvotes: 2

Related Questions