Inssertion sort

What is Insertion sort

a sorting algorithm
dividng an array into sroted and unsorted sections
removes elements in idividually from un unosrted section of the list and inserts it into its correct position in a new sorted seqeuence

Algorithm

Set a key for the sections after the 1st element
repeat the following
- select first unsorted element as the key
- move sorted elements to the right to create space
- shift unsorted elemnet into correct position
- advance the key to the right by 1 element
Tests first unsorted element (key) to last element of sorted section
If key is larger, insertion sort leaves the element in place and hte next index’s element becomes the key
Else it finds the correct position within the sorted list
- Duplicate the larger element in to one ahead of its current index each time the key is tested
- By looping this, it makes space and inserts the key into that correct position

Pseudo code

for x = 1 : n
    key = list[x]
    y = x-1
    while y >= 0 && key < list[y]
        insert list[x] into the sorted sequence list[1 .. x-1]
        list[y+1] = list[y]
        y--
    list[y+1] = key

Code

for(int i=1; i<numbers.length; i++) {
    key = numbers[i];
    j = i-1;
    while(j >= 0 && numbers[j] > key) {
        numbers[j + 1] = numbers[j];
        j--;
    }
    numbers[j + 1] = key;
}

Attributes

Stable
- Instead of swapping elements, all elements are shifted one position ahead
Adaptable
- if input is already sorted then time complexity will be \(`O(n)`\)
Space complexity
- In-place sorting, original array is updated rather than creating a new one, space complexity \(`O(1)`\)
Very low overhead

Time Complexity

Best Case
- \(`O(N)`\)
Worst Case
- \(`O(N^2)`\)
Average Case
- \(`O(N^2)`\)

Number of passes and comparisons

Number of passes
- Insetion sort always require n-1 passes
Mininimum number of comparisons = \(`n-1`\)
maximum number of comparisons = \(`\dfrac{n^2-n}{2}`\) or \(`n(n-1)/2`\)
Average number of comparisons = \(`\dfrac{n^2-n}{4}`\) or \(`n(n-1)/4`\)

When To Use

Good to use when the array is nearly sorted, and only a few elements are misplaced
Method is efficient - reduces the number of comparisons if in a pratially sorted array
Method will simply insert the unsorted elements into its correct place.

When not to use

In efficient for inverse sorting
Descending order is considered the worst unsorted case
Not as efficient if list is completely unsorted

Relation to Selection Sort

Outer loop over every index
Inner loop
Each pass (within the inner loop) increases the number of sorted items by one until there are no more unsorted items

Differences To Selection Sort

Selection Sort - Taking the current item and swapping it with the smallest item on the right side of the list - More simple - One possible case \(`O(n^2)`\)

Insertion Sort - Taking the current item and inserting into the right position by adjusting the list - more efficient (best case \(`O(n)`\))

3.0 KiB Raw Permalink Blame History Unescape Escape