Page 242 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

Notes
1 3 7 9 16 5 16 > 5, swap
1 3 7 9 5 16 9 > 5, swap
1 3 7 5 9 16 7 > 5, swap
1 3 5 7 9 16 3 < 5 < 7, sifting is done

This approach writes sifted element to temporary position many times. Next implementation
eliminates those unnecessary writes.

Shifting Instead of Swapping

We can modify previous algorithm, so it will write sifted element only to the final correct position.

Let us see an illustration.
1 3 7 9 16 5 16 > 5, swap
1 3 7 9 ? 16 9 > 5, swap
1 3 7 ? 9 16 7 > 5, swap
1 3 5 7 9 16 3 < 5 < 7, sifting is done

insert 5 to final position
It is the most commonly used modification of the insertion sort.

Using Binary Search

It is reasonable to use binary search algorithm to find a proper place for insertion. This variant of
the insertion sort is called binary insertion sort. After position for insertion is found, algorithm
shifts the part of the array and inserts the element. This version has lower number of comparisons,
but overall average complexity remains O(n ). From a practical point of view this improvement is
2
not very important, because insertion sort is used on quite small data sets.
12.2.2 Complexity Analysis

Insertion sort’s overall complexity is O(n ) on average, regardless of the method of insertion. On
2
the almost sorted arrays insertion sort shows better performance, up to O(n) in case of applying
insertion sort to a sorted array. Number of writes is O(n ) on average, but number of comparisons
2
2
may vary depending on the insertion algorithm. It is O(n ) when shifting or swapping methods
are used and O(n log n) for binary insertion sort.
From the point of view of practical application, an average complexity of the insertion sort is not
so important. As it was mentioned above, insertion sort is applied to quite small data sets (from
8 to 12 elements).

12.3 Shell Sort

Most of the sorting algorithms seen so far such as insertion sort and selection sort have a run time
complexity of O(N ). We also know that no sorting algorithm can have time complexity less than
2
O(N), since we need to scan the list at least once. For example, insertion sort best case complexity
2
is O(N). Can we get a better performance and get run time complexity between O(N ) and O(N)?
The answer is Yes and there are many algorithms with a complexity in this range, with varying
tradeoffs. In this note, we describe one approach: Shell Sort. Shell Sort has evolved as a trial and
error algorithm. Analytical results are not available but empirically it has been found that the

LOVELY PROFESSIONAL UNIVERSITY 237