Chapter9 Part2

COS 212
Sorting:
Shell Sort and Heap Sort
Intuitive Sorting Algorithms are Slow
 Why are the intuitive sorting algorithms so slow?
 Always involves a nested loop, bringing complexity up to O(n2)
 Can we alleviate this quadratic bane?
 Let’s look at an example
6 7 2 1 5 8 3 4
 This array contains 8 elements
 If sorting has O(n2) complexity, then t(n) = n2, and t(8) = 64
 What if we split the array in two halves?
6 7 2 1 5 8 3 4
 Using the same algorithm to sort the halves separately
 For each half of the array, t(4) = 16
 Therefore, for the entire array, t(4) x 2 = 32
 Much less time complex than sorting the whole array!
Efficient sorting
 However… sorting each half does not sort the entire array!
 But it does bring the array closer to a fully sorted array
 Arrays can be subdivided in many ways – not just halved
 Let’s consider comb sort again
 Compare elements that are m places apart
 Value of m is called a gap
 The gap shrinks non-linearly for each pass through the array
 In each pass we bubble sort only a subset of elements
33 98 74 13 55 20 77 45 64 83 m=7

33 98 74 13 55 20 77 45 64 83
33 64 74 13 55 20 77 45 98 83
33 64 74 13 55 20 77 45 98 83
 This improves performance

 Comb sort improves bubble sort to O(n lg n) in the best case
 Can we improve insertion sort and selection sort in a similar way?
Shell Sort
 How do insertion sort and selection sort work?
 Keep an “invisible wall” between the sorted and unsorted part
44 45 46 48 43 12
Sorted Unsorted
 Insertion sort removes elements from unsorted, inserting them into the correct
location in sorted
 Selection sort swaps the smallest element in unsorted with the element at the
head of unsorted, moving it into sorted
 The shell sort algorithm
 Uses comb sort’s idea: Use a variable gap to create sub-arrays
 Sort sub-arrays using any algorithm, decrease gap, until sorted
Shell Sort
 Let’s look at an example
n=6
 Choose an initial gap = 3
 Find sub-arrays
3 6 2 8 1 5
 Apply a sorting algorithm
to every sub-array
 Use any sorting algorithm
 Insertion sort is very commonly
used, so we’ll do the same
for this example 3 8
 Shrink the gap until gap = 1
6 1
2 5
3 1 2 8 6 5
Shell Sort
 Moving on to the second pass
 We’ll reduce the gap by 1
for this example
 gap = 2
 Find sub-arrays 3 1 2 8 6 5
 Apply insertion sort to
sub-arrays
3 2 6
 Now for the final pass 1 8 5
 gap = 1
 We’re now working with
the full array
 Apply insertion sort 2 1 3 5 6 8
 We performed a single move on the last iteration!

Shell Sort: Efficiency Iterate through all the
gaps
for (gap = initialValue; gap >= 1; gap = shrinkGap(gap)){

for (p = 0; p < gap; p++) { Generate all
// insert your favourite algorithm here to the sub-arrays
// sort each sub-array starting at index p
}
}
 How do we choose the gaps? O(n2), but will improve

 If the gaps decrease linearly significantly thanks to
 n-1, … , 3, 2, 1 sorting of sub-arrays
 How many times will the outer
loop execute?
 Even if the inner algorithm improves from O(n2) to O(n), complexity of the
outer loop will bring it back to O(n2)
 Gaps must decrease non-linearly!
 Divide by a factor
 Hard-code a sequence of gaps Best case: Worst case:
O(n lg n) O(n lg2 n )
Shell Sort: Efficiency
Revisiting Selection Sort
selectionSort(data[ ])
for i = 0 to data.length-1
select the smallest element among
data[i], ... , data[data.length-1];
swap it with data[i];
Selection Best Average Worst
 Why is selection sort slow? Comparisons O(n2) O(n2) O(n2)

 We have to search for the
Movements 0 O(n) O(n)
smallest element at every
outer loop iteration
 What if we had direct access to the smallest element?
 Do you recall any data structure that allows exactly that?
 Yes! Heaps
 Min-heap: The smallest element is always at the top
 Max-heap: The largest element is always at the top
 Heaps are especially appropriate for sorting
 They can be stored in arrays
Heap Sort
heapsort(data[])
transform data[] into a max-heap; // Floyd’s algorithm
for i = data.length-1 down to 2
swap the root with the element in position i;
restore heap property for the tree data[0], ... , data[i-1];
 Phase 1: Transform data into a max-heap

 Phase 2: The sorting procedure
 The opposite of classic selection sort (i.e. sorted part is on the right)
 Start with entire array in unsorted part
 Swap root (largest element in the heap) with last value in unsorted
 This removes root from heap, adding it to the left of the sorted part
 Thus the heap shrinks as the sorted part grows
 Finally, restore the heap in the unsorted part, and repeat
 The result of this heap sort
 Array in ascending order
 What if you wanted descending order instead?
Heap Sort
 Phase 1: Transform data into a max-heap
FloydAlgorithm(data[])
i = index of the last nonleaf
while i >= 0
p = data[i];
while p is not a leaf and p < any of its children
swap p with the larger child;
i = i--; // index of the previous non-leaf
 Floyd’s algorithm
 Start with the last non-leaf node
 While the non-leaf node has a smaller value than any of its children
 Swap the non-leaf node with the largest of these children
 Stop if no larger valued children found, or non-leaf node becomes a leaf
 Continue with the previous non-leaf node
 Efficiency is O(n)
Heap Sort
 Phase 1: Transform data into a max-heap (Floyd’s algorithm)
4
6 3 3 6 4
7 5 4 7 5 4 7 5 3
4 6 3 7 5 4 4 6 3 7 5 4 4 6 4 7 5 3
Last nonleaf
4 7 7
7 4 4 4 6 4
6 5 3 6 5 3 4 5 3
4 7 4 6 5 3 7 4 4 6 5 3 7 6 4 4 5 3
Heap Sort
for i = data.length-1 down to 2
p = the root;
while p is not a leaf and p < any of its children
swap p with the larger child;
 Dequeuing algorithm
 Swap largest element (always at data[0]) with last leaf (at data[i])
 Both are efficient to work with, due to direct access
 Restore the heap property
 Set p to the root of the heap
 While p is less than any of its children, swap p with its largest child
 Efficiency is O(lg n)
Heap Sort
7 3 6 6
6 4 6 4 3 4 5 4
4 5 3 4 5 7 4 5 4 3
7 6 4 4 5 3 3 6 4 4 5 7 6 3 4 4 5 7 6 5 4 4 3 7
3 5 5 3
5 4 3 4 4 4 4 4
4 6 4 3 5
3 5 4 4 6 7 5 3 4 4 6 7 5 4 4 3 6 7 3 4 4 5 6 7
Heap Sort
3 4 4 4 3
4 4 3 4 3 4 3 4
5
3 4 4 5 6 7 4 3 4 5 6 7 4 3 4 5 6 7 4 3 4 5 6 7 3 4 4 5 6 7
Heap Sort
 Efficiency of heap sort?
O(n)
heapsort(data[])
transform data[] into a heap; // Floyd’s heapifying algorithm
for i = data.length-1 down to 2 O(n)
restore the heap property for the tree data[0], …, data[i-1];
Best case: Worst case: O(lg n) Average case:

O(n lg n) O(n lg n ) O(n lg n )

Chapter9 Part2

Uploaded by

Copyright:

Available Formats

Chapter9 Part2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter9 Part2

Uploaded by

Copyright:

Available Formats

COS 212

33 98 74 13 55 20 77 45 64 83 m=7

 This improves performance

 We performed a single move on the last iteration!

for (gap = initialValue; gap >= 1; gap = shrinkGap(gap)){

 How do we choose the gaps? O(n2), but will improve

 Why is selection sort slow? Comparisons O(n2) O(n2) O(n2)

 Phase 1: Transform data into a max-heap

Best case: Worst case: O(lg n) Average case:

You might also like