ADA: Sorting - Concept of Insertion Sort Algorithm

Concept of Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quick sort, heap sort, or merge sort. However, insertion sort provides several advantages:

• Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version^[2]
• Efficient for (quite) small data sets, much like other quadratic sorting algorithms
• More efficient in practice than most other simple quadratic (i.e., O(n²)) algorithms such as selection sort or bubble sort
• Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position

Problem Statement

Imagine that you are playing a card game. You’re holding the cards in your hand, and these cards are sorted. The dealer hands you exactly one new card. You have to put it into the correct place so that the cards you’re holding are still sorted.Imagine that you are playing a card game. You’re holding the cards in your hand, and these cards are sorted. The dealer hands you exactly one new card. You have to put it into the correct place so that the cards you’re holding are still sorted.

Output

File: Download here