Algorithms Chapter 5 Algorithms Sequential Parallel And Distributed More Sorting Algorithms Glance Table Contents

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