Page 240 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

Any sorting algorithm that uses comparisons of keys needs at least O(n log n) time to accomplish Notes
the sorting.

Sorting Methods
Internal External
(In memory) (Appropriate for secondary storage)
quick sort
heap sort merge sort
bubble sort radix sort
insertion sort poly-phase sort
selection sort
shell sort

12.2 Insertion Sort

This is a naturally occurring sorting method exemplified by a card player arranging the cards
dealt to him. He picks up the cards as they are dealt and inserts them into the required position.
Thus at every step, we insert an item into its proper place in an already ordered list.

We will illustrate insertion sort with an example (refer to Figure 9.1) before presenting the formal
algorithm.

Example: Sort the following list using the insertion sort method:
4, 1, 3, 2, 5
(1) 4

1 < 4, Therefore insert before 4
(2) 1 4

3 > 1, 3 Insert between 1 & 4

(3) 1 3 4
2 > 1, 2 Insert between 1 & 3

(4) 1 2 3 4

5 > 1, 2, 3, 4 Insert after 4
(5) 1 2 3 4 5

Insertion Sort
Thus to fi nd the correct position search the list till an item just greater than the target is found.
Shift all the items from this point one down the list. Insert the target in the vacated slot. Repeat
this process for all the elements in the list. This results in sorted list.

12.2.1 Algorithm of Insertion Sort

Insertion sort algorithm somewhat resembles selection sort. Array is imaginary divided into

two parts - sorted one and unsorted one. At the beginning, sorted part contains first element of

the array and unsorted one contains the rest. At every step, algorithm takes first element in the

LOVELY PROFESSIONAL UNIVERSITY 235