What is the sorting problem?

Have you ever find yourself in a situation in which you needed to reorder some papers in chronological order? Or maybe a deck of cards to play with your friends? Each time you have a collection of values (dates, numbers etc.) that you have to order, you are dealing with sorting.

 

The formal definition of the sorting problem is this:

Input
A sequence of n numbers [a1 ,a2 ,. . . . . . . , an]
Output
A permutation [a1' ,a2' ,. . . . . . . an'] of the input sequence such that a1' <= a2' <= . . . . . . <= an'

In Computer Science and Engineering in general, many problems require a list sorted in some order to be able to perform some common tasks, like searching for an element or storing some documents by date. Therefore, it is crucial to develop some techniques to optimize the sorting process in order to reduce the latency time. That is where Algorithms come to help us. We are going to explain to you the most common sorting algorithms in the most simple but detailed way possible. Today's algorithm is called Insertion sort, let's see how it works!

How can you sort a deck of cards?

Imagine you have some cards laid on the table. You must sort them in ascending order. How do you usually accomplish this task? Simple, you just use the Insertion sort! It actually pretty easy to understand. Take a look at this image.

Sorting a deck of cards

You simply take the first two cards, 8♣ and Q♠, and you order them together. Then you select the third card (10♦) and you order it with the first two by placing it in between them (8♣ - 10♦ - Q♠), and you do the same with each card on the list. By the time you reach the final card, you will have your list of cards sorted together. That is exactly how Insertion sort works.

The idea is to sort every card in a separate list. Each time you pick a new card you just need to select the right position in which to place it to keep your list sorted in ascending order. As I said, pretty easy!

Review

 

Name Insertion Sort
Best case Ο(n)
Average case Ο(n2)
Worst case Ο(n2)
Stable YES
In place YES
Adaptive YES
Difficulty Easy
Method Insertion

How to implement it, the pseudocode

Now we need to implement the code that will allow our PC to compute each step for us. This is how the pseudocode looks like:

for j = 2 to A.length
  key = A[j]
  i = j - 1
  while i > 0 and A[i] > key
    A[i + 1] = A[i]
    i = i - 1
  A[i + 1] = key

We cycle through the whole list starting from the second value (j = 2). We remove one element from the input data (key = A[j]), find the location it belongs within the sorted list by using a while cycle, and insert it there. The whole cycle repeats until no input elements remain. 

Properties

The Insertion sort algorithm is relatively efficient for small list and mostly sorted list and is often used as part of more sophisticated algorithms. These are his main properties:

  • Stable: Sort identical elements in the same order they appear in the input. For instance, if we have two equal numbers, the first one will be placed before the second as they were in the input list;
  • In place: Transforms input using no auxiliary data structure;
  • Adaptive: It benefits from the presortedness in the input sequence and sorts faster.

Complexity

The running time of the algorithm is the sum of the running times of each statement executed.

for j = 2 to A.length             c1      n
  key = A[j]                      c2      n - 1
  i = j - 1                       c3      n - 1
  while i > 0 and A[i] > key      c4      ∑t from 2 to n
    A[i + 1] = A[i]               c5      ∑(t - 1) from 2 to n
    i = i - 1                     c6      ∑(t - 1) from 2 to n
  A[i + 1] = key                  c7      n - 1
T(n) = c1n + c2(n - 1) + c3(n - 1) + c4(t) + c5((t - 1)) c6((t - 1)) + c7(n - 1)

Best case

The best case occurs when the list is already sorted; in this case, insertion sort has a linear running time Ο(n). The number of swaps in the best case is 0 because every number is already in place.

Worst case

The worst case occurs when the list is in reverse order; in this case, the insertion sort is pretty inefficient, with a quadratic running time Ο(n2). The number of swaps is also Ο(n2).

Average case

The average case for the insertion sort is also quadratic Ο(n2). The same for the number of swaps. We should not use the insertion sort to order a long list because in the average case the algorithm is inefficient and slow for a large amount of data.

Where do we use Insertion sort?

Although it is one of the elementary sorting algorithms with Ο(n2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

Source: http://www.sorting-algorithms.com/insertion-sort

Programming languages implementation

C++

// Starting from 1 (the first number is already sorted with itself)
// SIZE is the length of the array
for (int j = 1; j < SIZE; ++j) {
  // Get value of current selected number
  int key = A[j];
  
  // while cycle from the number before the 'key'
  int i = j - 1;

  // Switch values if current number is greater than key
  while (i >= 0 && A[i] > key) {
    A[i + 1] = A[i];
    --i;
  }

  // Reinsert the key in sorted order
  A[i + 1] = key;
}

PHP

// Starting from 1 (the first number is already sorted with itself)
for ($j = 1; $j < count($A); ++$j) {
  // Get the value of the current selected number
  $key = $A[$j];
  
  // while cycle from the number before the 'key'
  $i = $j - 1;
 
  // Switch values if the current number is greater than key
  while ($i >= 0 && $A[$i] > $key) {
    $A[$i + 1] = $A[$i];
    --$i;
  }

  // Reinsert the key in sorted order
  $A[$i + 1] = $key;
}

Reverse order sorting

To sort the list from the greatest to the smallest number (reverse sorting) you just need to change the A[i] > key with A[i] < key, that simple!

for j = 2 to A.length
  key = A[j]
  i = j - 1
  while i > 0 and A[i] < key
    A[i + 1] = A[i]
    i = i - 1
  A[i + 1] = key

 

 

 

This was the Insertion sort. We will guide you through all the other sorting algorithms in some future articles. Until then, stay tuned and subscribe to our newsletter to be notified about our next sorting explanation.