6 Pages

# Chapter 2: Getting started Edit

## Sorting - Insertion sort Edit

• 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 sort Edit

• 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 illustration Edit

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

## Pseudocode for insertion sort Edit

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