Toggle navigation

Insertion sortTaste of algorithms in JAVA

Insertion sort is a sorting algorithm based on comparison of elements. Insertion sort is stable and has quadratic asymptotic complexity O(n^{2}). Generalized version of this algorithm is Shell sort, which is an insertion sort with diminishing increment.

Description

The idea of the insertion sort is simple:

  1. One element is sorted trivially
  2. Pick element next to the already sorted sequence and insert it to the correct place - move every element of the already sorted sequence, which has a higher value than the element being sorted, one place right, than put the element into the gap (correct place within the sequence).
  3. While array contains any unsorted elements GOTO: 2.

Advantages of insertion sort

If the input sequence is already sorted, than the insertion sort only checks the ordering and does not perform any moves. Hence if there are only few unsorted elements, the complexity of insertion sort gets close to O(n). In these cases insertion sort outperforms divide-and-conquer algorithms with asymptotic complexity O(n \\cdot \\log{n}) such as quicksort, merge sort or heapsort.

Also for small inputs (n \\leq 10) the insertion sort tends to be faster than the algorithms mentioned above, so it might be used as a subroutine of divide-and-conquer algorithms for small sub-problems.

Visualization

Example

(3 2 8 7 6) // Initial array - sort it in descending order
(3 2 8 7 6) // Element 3 is sorted trivially
(3 2 8 7 6) // Pick 2 and insert it to the correct place (already done)
(3 2 8 7 6) // Insert 1 to the first place, move the elements 3 and 2 one place right
(8 3 2 7 6) // Insert 7 between 8 and 3, move 3 a 2 one place right
(8 7 3 2 6) // Insert 6 between 7 and 3, move 3 and 2 one place right
(8 7 6 3 2) // Sorted

Code

       function insertionSort(array a)
           for i in 0 -> a.length - 2 do
               j = i + 1
               tmp = a[j]
               while j > 0 AND tmp > a[j-1] do //create a gap
                   a[j] = a[j-1]
                   j--
               a[j] = tmp //insert
   
       /**
        * Insertion sort (descending order)
        * @param array array to be sorted
        */
       public static void insertionSort(int[] array) {
           for (int i = 0; i < array.length - 1; i++) {
               int j = i + 1;
               int tmp = array[j];
               while (j > 0 && tmp > array[j-1]) {
                   array[j] = array[j-1];
                   j--;
               }
               array[j] = tmp;
           }
       }
   
 
   /**
    * Insertion sort (descending order)
    * @param array array to be sorted
    * @param size size of the array
    */
   void insertionSort(int array[], int size) {
       for (int i = 0; i < size - 1; i++) {
           int j = i + 1;
           int tmp = array[j];
           while (j > 0 && tmp > array[j-1]) {
               array[j] = array[j-1];
               j--;
           }
           array[j] = tmp;
       }
   }
   
 
          /**
           * Insertion sort (descending order)
           * @param array array to be sorted
           */
           public static void InsertionSort(int[] array)
           {
               for (int i = 0; i < array.Length - 1; i++)
               {
                   int j = i + 1;
                   int tmp = array[j];
                   while (j > 0 && tmp > array[j - 1])
                   {
                       array[j] = array[j - 1];
                       j--;
                   }
                   array[j] = tmp;
               }
           }
   
     procedure Insert(var X : ArrayType; N : integer);
     var
       J,
       K,
       Y : integer;
       Found : boolean;
     begin
       for J := 2 to N do
         begin
           Y := X[J];
           K := J - 1;
           Found := false;
           while (K >= 1)
           and (not Found) do
             if (Y < X[K]) then
               begin
                 X[K + 1] := X[K];
                 K := K - 1
               end
             else
               Found := true;
           X[K + 1] := Y;
         end
      end;
   







INFO WEB s.r.o.

Company INFO WEB s.r.o. offers development of systems, GIS, presentations and interactive maps, using the microcontrollers from the IoT (Tnternet of Things) technology. Beside this on PROGRAMMING-ALGORITHMS.NET we publish some of the algorithms, which helps to solve some of the spatial analysis and spatial problems, conversion of coordinate systems and helps to solve standard computing operations.

ADVERTISEMENT

Place for your banner

Here is the position ready for our customer's banners.