Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
Algorithms: Sequential, Parallel and Distributed 5-1
Chapter 5
More on Sorting Algorithms
At a Glance
Table of Contents
Algorithms: Sequential, Parallel and Distributed 5-2
Lecture Notes
Overview
In Chapter 5 we discuss the widely used comparison-based sorting algorithm Shellsort. We
also discuss the comparison-based sorting algorithm BingoSort, which is an example of a
sorting algorithm that works well on lists with many repeated elements. We then present
RadixSort, which is not a comparison-based sorting algorithm, but rather makes specific use of
the nature of the keys. We finish Chapter 5 with a discussion of external sorting algorithms,
which are needed for sorting lists that are too large to reside in internal memory.
Chapter Objectives
After completing the chapter the student will know:
Instructor Notes
It is interesting that ShellSort, which is a simple variant of InsertionSort, comes within a
logarithm factor of having order optimal worst-case behavior for a suitable set of increments. It
It is of interest to design sorting algorithms that, while they might not exhibit good behavior for
arbitrary lists, nevertheless perform well on lists with many repeated elements. We present
5.9)
Algorithms: Sequential, Parallel and Distributed 5-3
In order to obtain sorting algorithms that perform less than O(nlogn) comparisons, we need to
abandon comparison-based algorithms, and make special assumptions about the lists we are
Solutions to Selected Exercises
Section 5.1 Shellsort
5.1 a)
Original list: 33, 2, 56, 23, 55, 78, 2, 98, 61, 108, 14, 60, 56, 77, 5, 3, 1
b)
Original list: 33, 2, 56, 23, 55, 78, 2, 98, 61, 108, 14, 60, 56, 77, 5, 3, 1
5.3 The only inversions that can be removed by interchanging π(i) and π(i+k) are of the form
5.4 Using Exercise 5.3, each comparison made by a comparison-based algorithm that only
5.5 Each comparison made by a k-subsort compares elements k positions apart. Thus, if k =
K[0] is the first increment used by ShellSort, and k is a constant not depending on n, the
5.7
Pass 1 2 1 1 5 1 2 4 4 4 7 1 1 1 3 3 5 5 5 1 7 7 4
Start position 0 1 2 1 5 1 2 4 4 4 7 1 1 1 3 3 5 5 5 1 7 7 4
Bingo value 1 1 1 2 5 1 2 4 4 4 7 1 1 1 3 3 5 5 5 1 7 7 4
1 1 1 5 2 2 4 4 4 7 1 1 1 3 3 5 5 5 1 7 7 4
5.8 Bingosort already can fail to be stable on the smallest possible list where it can fail, namely
a three element list. An example is the list 2, 2, 1.
5.9 Suppose the m distinct values in the list L[0:n – 1] are x1 < x2 < … < xm. We prove that
correctness of BingoSort by establishing the following loop invariants of the while loop.
For 0 ≤ i ≤ m – 1, after i iterations of the while loop, we have:
1. Those list elements having values in {x1 , x2 , … , xi} have been moved to correct final
positions in the list,
2. NextAvail is the first index where the elements having value xi+1 reside in a sorting of
the entire list,
5.10 BingoSort begins by calling MaxMin3, which performs 3n/2 – 2 comparisons.
Afterwards, during a given execution of the for loop, the comparison L[i] = Bingo is made
during each iteration, whereas the comparison L[i] < NextBingo is made only when L[i] ≠
Bingo. Thus, if the m distinct values in the list L[0:n – 1] are x1 < x2 < … < xm, and mj
5.11 We assume that each of the m distinct values in L[0:n – 1] occurs n/m times. Then the
number of comparisons is given by
Section 5.3 Radixsort
5.13 Original list:
1011101, 0100011, 1010110, 1111101, 0011101, 0000001, 1000000, 1010101
Pass 1
Bucket 0:
1010110, 1000000
Bucket 1:
1011101, 0100011, 1111101, 0011101,
0000001, 1010101
Extract list
1010110, 1000000, 1011101, 0100011,
1111101, 0011101, 0000001, 1010101
Pass 2
Bucket 0:
1000000, 1011101, 1111101, 0011101,
0000001, 1010101
Bucket 1:
1010110, 0100011
Extract list
1000000, 1011101, 1111101, 0011101,
0000001, 1010101, 1010110, 0100011
Pass 3
Bucket 0:
1000000, 0000001, 0100011
Bucket 1:
1011101, 1111101, 0011101, 1010101,
1010110
Extract list
1000000, 0000001, 0100011, 1011101,
1111101, 0011101, 1010101, 1010110
Pass 4
Bucket 0:
1000000, 0000001, 0100011, 1010101,
1010110
Bucket 1:
1011101, 1111101, 0011101
Extract list
1000000, 0000001, 0100011, 1010101,
1010110, 1011101, 1111101, 0011101
Pass 5
Bucket 0:
1000000, 0000001, 0100011
Bucket 1:
1010101, 1010110, 1011101, 1111101,
0011101
Extract list
1000000, 0000001, 0100011, 1010101,
1010110, 1011101, 1111101, 0011101
Pass 6
Bucket 0:
1000000, 0000001, 1010101, 1010110,
1011101, 0011101
Bucket 1:
0100011, 1111101
Extract list
1000000, 0000001, 1010101, 1010110,
1011101, 0011101, 0100011, 1111101
Pass 7
Bucket 0:
0000001, 0011101, 0100011
Bucket 1:
1000000, 1010101, 1010110, 1011101,
1111101
Extract
sorted list
0000001, 0011101, 0100011, 1000000,
1010101, 1010110, 1011101, 1111101
5.15 We prove that RadixSort is correct using induction on the parameter k.
Basis Step: k = 1. In this case, all the strings have length 1, so that Bq is enqueued with all
the elements sq that were in the list L, for q = 0,..., q. Hence, dequeueing them from the
5.16 RadixSort is indeed stable, since if x and y are equal elements in the list, where x occurs
5.17 The code outline for RadixSort2 is somewhat similar to that for QuickSort, except, for
example, that a straightforward partitioning is done using a simplification of BingoSort.
procedure RadixSort2(S[0:n – 1], k, low, high, j) recursive
Input: S[0:n – 1], k (a list of size n of binary strings of length k), low,high (integers)
Algorithms: Sequential, Parallel and Distributed 5-7
for i ← low to high do
if Substr(S[i], j, 1) = 0 then
interchange(S[i],S[NextAvail])
NextAvail ← NextAvail + 1
endif
5.23 a. Proof by induction on the number n of pancakes.
Basis Step: n = 1. Trivial.
Induction Step: Assume there exists a set of flips that sorts any stack of n – 1 pancakes.
Given any stack of n pancakes, select the pile on the top of the stack that contains the largest
pancake in the stack at the bottom of the pile. If this largest pancake is already at the bottom of
b. In a loop indexed by i running from n down to 2, during each iteration of the loop, a linear
scan is made to find the index of a maximum element in the first i elements, and then performs
1)/2 comparisons to find the potential flip positions (although, again, no flips would be made
5.24 When a (currently) largest pancake is brought to the top of the stack by a flip as in the
