What is insertion sort?

Answer 1

The function on insertion sort is to insert a value into its proper place using an algorithm automatically. It sorts through an array and puts it in the appropriate order according to absolute smallest element.

Answer 2

Insertion is a stable sort, ideally suited to sorting small sets of data. It is a quadratic algorithm with a time complexity of O(n*n), but in practice it performs better than other quadratic algorithms such as selection sort.

The algorithm has the following implementation (in pseudocode):

proc insertionsort (A)

for i := 1 to length(A)-1

j := i

while j > 0 and A[j-1] > A[j]

swap A[j] and A[j-1]

j := j - 1

end while

end for

Insertion sort can also be used on large, partially-sorted sets. This is useful when used in conjunction with an in-place, divide-and-conquer algorithm, such as quicksort, where the unsorted set is divided and subdivided into smaller and smaller unsorted subsets. When a subset has been reduced to a critical size (fewer than k elements), the algorithm can stop dividing that subset. Once all subsets have been reduced, insertion sort can be applied across the entire set in O(nk) time because all the unsorted elements will be less than k positions from their final sorted position (assuming the subsets themselves are in the correct order relative to each other, as they would be with an in-place quicksort).

The following pseudocode demonstrates this (where the critical length is 15 elements):

proc sort (A)

quicksort (A, 0, length(A))

insertionsort (A)

proc quicksort (A, lo, hi)

if hi - lo < 15 then return; // critical length reached

pivot := partition (A, lo, hi)

quicksort (A, lo, pivot-1)

quicksort (A, pivot + 1, hi)

Note that although insertion sort is a stable sort, quicksort is unstable so the end result is unstable. This means that elements of equal value may not be in the same order they were input. Although this is of little importance when elements have only one value (and therefore only one sort key), stability is important when there are multiple sort keys to choose from. For instance, when sorting a set of files, we might choose to initially sort by name. If we subsequently choose to sort by type, we would expect all files of the same type to remain in sorted order (by name), as per the input order. Thus the primary key becomes the secondary key of the next sort. Stable sorting algorithms guarantee this automatically. Unstable sorts do not, but are generally quicker than stable sorts. In order to make them stable, we need to use the input order as a secondary key (essentially indexing the elements), but it takes an additional O(n) time to establish those secondary keys, and adds additional time to each comparison because we need to test for equality. Stable sorts do not test for equality, they only use the strict weak ordering predicate (typically the less-than operator).

Answer 3

Insertion sort is a recursive sort which recursively adds a single element to a sorted list thus creating a sorted list of one longer length.

An empty array and an array of one element is by default sorted.

Taking a sorted array, and the next element, we find the spot in the sorted array where we will insert the next element. We then shift all the elements after that, to make room for this element, and then finally insert the element in the proper spot.

At the end of the algorithm, the array should be completely sorted.

Answer 4

Insertion sort is the sorting mechanism where the sorted array is built having one item at a time. The array elements are compared with each other sequentially and then arranged simultaneously in some particular order. The analogy can be understood from the style we arrange a deck of cards.

To learn more about data science please visit- Learnbay.co