Insertion sort

Algorithms Insertion sort

Insertion sort is the King of simple sorting algorithms. It's stable, easy to implement, and acts intelligently while running on presorted arrays and on small arrays (less than a hundred elements). Due to its simplicity, it's even faster than QuickSort on these small arrays.

Insertion sort sees the array as two independent parts - sorted and unsorted. It continuously selects items from the unsorted part and inserts them between items in the sorted part so that it stays sorted. This is where its name comes from - it inserts the item exactly where it belongs and avoids doing any unnecessary actions like Bubble sort does.

However, a disadvantage for the algorithm appears when processing larger arrays. The disadvantage is its time complexity O(n2) which makes it inefficient when compared to smarter algorithms, in these cases.

Algorithm properties

Time complexity O(n2)
Stability Yes
Speed High on small arrays

Note. the time complexity is according to average cases and the speed is like this when compared to all of the other algorithms.

Process

Consider an array of the following items:

3 2 5 1 9 4

The first item (3) is seen as sorted and the rest of array as unsorted. Let's start up from the second item (2), which we'll save to the auxiliary memory.

Memory: 2

3 2 5 1 9 4

Next, we'll create a space for this item in the sorted part where we'll insert it afterward. We'll move the items in the sorted part to the right until we find an item which is smaller (or equal) to it or to the very beginning of array respectively. It could get a bit confusing that an item is physically written twice in the array since it'll represent an empty space once (highlighted in gray). Theoretically, there isn't anything there, but it'd be inefficient to actually remove the value from the memory.

Let's get back on track, we have 2 saved in the memory which is smaller than 3. Therefore, we'll move the third item to the right. In doing so, we'll lose the item 2, however, we have it saved in the memory, so it doesn't matter.

Memory: 2

3 3 5 1 9 4

There's the beginning of the array before the space we now have created. With that in mind, we'll place the item from the auxiliary memory to the "empty" space. The sorted part of the array now has two items.

Memory: 2

2 3 5 1 9 4

Let's go ahead and sort another item (5).

2 3 5 1 9 4

There is a smaller number before it, so it's already in the right place. The size of the sorted part has increased once more. Let's move on to the next one (1).

2 3 5 1 9 4

Memory: 1

2 3 5 5 9 4

Memory: 1

2 3 3 5 9 4

Memory: 1

2 2 3 5 9 4

Memory: 1

1 2 3 5 9 4

We're pretty much settled in regards to the beginning of the array since no other item is smaller than 1. With that in mind, the (9) will remain in place.

1 2 3 5 9 4

The last item is a (4), so let's get it sorted as well.

1 2 3 5 9 4

Memory: 4

1 2 3 5 9 9

Memory: 4

1 2 3 5 5 9

We'll stop before the (3) and insert the (4) from the auxiliary memory into the empty space we set up. That's it, we're done! :)

1 2 3 4 5 9

Visualization

Author of the visualization widget is Jenkings

Source code

public static void insertionSort(int[] list) {
  int item, j;
  for (int i = 1; i <= (list.length - 1); i++) {
    // insert item
    item = list[i];
    j = i - 1;
    while ((j >= 0) && (list[j] > item)) {
      list[j + 1] = list[j];
      j--;
    }
    list[j + 1] = item;
  }
}
public static void insertionSort(int[] list) {
  int item, j;
  for (int i = 1; i <= (list.Length - 1); i++) {
    // insert item
    item = list[i];
    j = i - 1;
    while ((j >= 0) && (list[j] > item)) {
      list[j + 1] = list[j];
      j--;
    }
    list[j + 1] = item;
  }
}
// sorts the array, assumes indexing from 0
procedure insertion_sort(var list: array of integer)
var i, j, item: integer;
begin
  for i:=1 to (length(list) - 1) do begin
    // insert item
    item:=list[i];
    j:=i - 1;
    while ((j >= 0) and (list[j] > item)) do begin
      list[j + 1]:=list[j];
      dec(j);
    end;
    list[j + 1]:=item;
  end;
end;
def insertion_sort(list)
  1.upto(list.length - 1) do |i|
    # insert item
    item = list[i]
    j = i - 1
    while ((j >= 0) && (list[j] > item))
      list[j + 1] = list[j]
      j -= 1;
    end
    list[j + 1] = item
  end
end

 

 

Article has been written for you by David Jancik
Avatar
Do you like this article?
No one has rated this quite yet, be the first one!
.
Thumbnail
Previous article
Merge Sort
Thumbnail
All articles in this section
Algorithms
Thumbnail
Next article
Heapsort
Activities (8)

 

 

Comments

To maintain the quality of discussion, we only allow registered members to comment. Sign in. If you're new, Sign up, it's free.

No one has commented yet - be the first!