InsertionSort

 Insertion sort is another simple sorting algorithm that is even easier to explain than quicksort

•  Find the nth smallest element not yet sorted
  
• Swap it into the nth position

Suppose again we have our unsorted array:

3

7

2

4

1

5

6

We scan the array and find the smallest number is 1.

So 1 swaps with whatever is in the 1^st position (array[0]).

1

7

2

4

3

5

6

Now the 1 is sorted and won’t move again. The rest remains unsorted.
The smallest element in “the rest” is 2, so we swap 2 and arr[1].

1

2

7

4

3

5

6

Now [1,2] is sorted, and “the rest” still isn’t.

1

2

3

4

7

5

6

At this point, [1,2,3] is sorted. (The 4 happens to be in the right place, but that’s by luck.) Let’s swap the 4 with the 4^th element.

We still have

1

2

3

4

7

5

6

Because we got lucky.

Now, we can say for sure that [1,2,3,4] is sorted, and “the rest” is not.

So let’s swap 5.

1

2

3

4

5

7

6

Now, [1,2,3,4,5] is sorted and “the rest” is not. To sort the 6, we find the 6 and swap it with position arr[5].

1

2

3

4

5

6

7

 

Now, [1,2,3,4,5,6] is sorted. Let’s take the final (trivial) step and sort the 7 by swapping 7 with whatever happens to be in arr[6] (itself, so nothing will change).

1

2

3

4

5

6

7

Before you go on, do what I had to do when I first learned this algorithm: make a video or live demo for your family of you insertionSort-ing about that many red Solo cups marked with numbers on their bottoms. If you can correctly sort the cups, move on to the pseudocode.

In pseudocode, this is:

InsertionSort(A)

    for i ← 1 to length(A) - 1 do

        key ← A[i]

        j ← i - 1

        while j ≥ 0 and A[j] > key do

            A[j + 1] ← A[j]

            j ← j - 1

        end while

        A[j + 1] ← key

    end for

Spend some time with this pseudocode and understand why it is equivalent to the example, or to what you did for your family with the cups. Once you are confident you understand the pseudocode—and only then—move on to the real Java code, found below:

public class InsertionSort {

    public static void main(String[] args) {

        int[] array = {10, 20, 25, 63, 96, 57};

        int size = array.length;

 

        for (int i = 1; i < size; i++) {

            int val = array[i];

            int pos = i;

            while (pos > 0 && array[pos - 1] > val) {

                array[pos] = array[pos - 1];

                pos = pos - 1;

            }

            array[pos] = val;

        }

 

        for (int i = 0; i < size; i++) {

            System.out.print(" " + array[i]);

        }

    }

}