Tue Apr 20 2021

Insertion Sort

Insertion sort is an efficient algorithm for sorting a small number of elements. Insertion sort sorts the array by shifting elements one by one. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

It is much less efficient on large lists than more advanced algorithms such as Quick Sort, Heap Sort, or merge sort. However, Insertion sort have several advantages, Like:

It is very simple for implementation
Efficient for small data sets
More efficient in practice than most other simple quadratic (Worst case O(n²)) algorithms such as selection sort or bubble sort
Adaptive, efficient for data sets that are already substantially sorted. The time complexity is O(n + d), where d is the number of inversions
Stable, does not change the relative order of elements with equal keys
In-place, only requires a constant amount O(1) of additional memory space
Online, can sort a list as it receives it

File Name: insertion-sort-algorithm.c

begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        done := false;
        repeat
            { To sort in descending order simply reverse
              the operator i.e. A[j] < value }
            if A[j] > value then
            begin
                A[j + 1] := A[j];
                j := j - 1;
                if j < 0 then
                    done := true;
            end
            else
                done := true;
        until done;
        A[j + 1] := value;
    end;
end;

Reference:

Insertion Sort

Author:Geekboots