Page 241 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes unsorted part and inserts it to the right place of the sorted one. When unsorted part becomes
empty, algorithm stops. Sketchy, insertion sort algorithm step looks like this:
Sorted partitial result Unsorted data
< X > X X . . .

becomes

Sorted partitial result Unsorted data
< X X > X . . .

Example: Sort {7, -5, 2, 16, 4} using insertion sort.
7 –5 2 16 4 unsorted

7 –5 2 16 4 –5 to be inserted
? 7 2 16 4 7 > –5, shift

–5 7 2 16 4 reached left boundary, insert-5

–5 7 2 16 4 2 to be inserted
–5 ? 7 16 4 7 > 2, shift
–5 2 7 16 4 –5 < 2, insert 2

–5 2 7 16 4 16 to be inserted
–5 2 7 16 4 7 < 16, insert 16

–5 2 7 16 4 4 to be inserted
–5 2 7 ? 16 16 > 4, shift

–5 2 ? 7 16 7 > 4, shift
–5 2 4 7 16 2 < 4, insert 4

–5 2 4 7 16 sorted

The Ideas of Insertion

The main operation of the algorithm is insertion. The task is to insert a value into the sorted part
of the array. Let us see the variants of how we can do it.

“Sifting down” using Swaps

The simplest way to insert next element into the sorted part is to sift it down, until it occupies
correct position. Initially the element stays right after the sorted part. At each step algorithm
compares the element with one before it and, if they stay in reversed order, swap them. Let us
see an illustration.

236 LOVELY PROFESSIONAL UNIVERSITY