FANDOM


Chapter 2: Getting startedEdit

Sorting - Insertion sortEdit

  • Insertion sort solves the sorting problem.
  • The sorting problem is defined as follows:
INPUT: A sequence of n numbers $ \{ a_{1}, a_{2},a_{3},...a_{n} \} $
OUTPUT: A permutation (or reordering) $ \{a_{1}^{'},a_{2}^{'},a_{3}^{'},...a_{n}^{'}, \} $
  • Keys are the numbers we want to sort.
  • Insertion sort is an efficient algorithm for sorting a small number of elements.

General working of insertion sortEdit

  • The essence of insertion sort is well explained by the typical process we use to sort playing cards:
    1. Keep all cards in a table.
    2. Pick a card with the right hand.
    3. Place the picked card in the left hand in its right spot.
    4. Until last card, repeat.
  • The cards in the left hand are always sorted.
  • Insertion sort is an in-place-sort because it rearranges numbers within the array, with at most a constant number of them stored outside the array as key at any instant of time.

Step by step illustrationEdit

  • Fig-2-2-insertion-sort-example

    The working of insertion sort. Black = Key, gray = sorted sub array, white = yet to be sorted (or unsorted) sub array







Pseudocode for insertion sortEdit

INSERTION-SORT(A)
1 for j ← 2 to length[A]
2   do key ← A[j]
3     // Insert A[j] into the sorted sequence A[1  j - 1].
4     i ← j - 1
5     while i > 0 and A[i] > key
6      do A[i + 1] ← A[i]
7         i ← i - 1
8     A[i + 1] ← key