Transcript CSC 2500 Computer Organization

CSC 2300
Data Structures & Algorithms
March 16, 2007
Chapter 7. Sorting
Today – Sorting

Insertion sort –




Algorithm
Analysis
Lower bound
Shellsort –


Algorithm
Worst case
Insertion Sort – Algorithm



We want to sort N integers.
There are N – 1 passes.
For pass p = 1 through N – 1, insertion sort ensures that the
elements in positions 0 through p are in sorted order.
Insert Sort Routine
Insertion Sort – Analysis





How many element comparisons are there in the inner loop?
At most p for each value of p.
Total number of comparisons =
1+2+3+…+(N – 1) = N(N – 1)/2 = Θ(N2).
Can you give an input sequence that achieves this bound?
Can you give an input sequence that requires Θ(N) time?
Average Case


Defining the average case is always difficult.
What do you think the average-case running time is?
Θ(N2) or Θ(N)?
Inversion

An inversion is an array of numbers is any ordered pair (i,j) having the property
that i < j but a[i] > a[j].

The input list has nine inversions: (34,8), (34,32), (34,21), (64,51), (64,32),
(64,21), (51,32), (51,21), and (32,21).
This is exactly the number of swaps that need to be performed by insertion sort.
Since there is O(N) other work involved in the algorithm, the running time of
insertion sort is O(I+N), where I is the number of inversions in the original array.


Theorem 7.1

Statement:


The average number of inversions in an array of N distinct
elements is N(N – 1)/4.
Proof:





For any list L of elements, consider Lr, the list in reverse
order.
Consider any pair of two elements (x,y) in the list.
In exactly one of L and Lr, the ordered pair represents an
inversion.
The total number of ordered pairs in L and Lr is N(N – 1)/2.
Thus, an average list has half this amount, or N(N – 1)/4
inversions.
Theorem 7.2

Statement:


Any algorithm that sorts by exchanging adjacent elements
requires Ω(N2) time on average.
Proof:



The average number of inversions is initially N(N – 1)/4.
Each swap removes only one inversion.
So Ω(N2) swaps are required.
An Idea



Theorem 7.2 is valid for an entire class of sorting
algorithms that performs only adjacent exchanges.
If a sorting algorithm is to run in sub-quadratic, or
o(N2), time, what must it do?
It must do comparisons and exchanges between
elements that are far apart.
Shellsort




Named after Donald Shell.
It works by comparing elements that are distant.
The distance between comparisons decreases as the
algorithm runs until its last phase, in which adjacent
elements are compared.
Also called diminishing increment sort.
Shellsort – Increment Sequence







Shellsort uses a sequence h1, h2, …,ht, called the increment
sequence.
Any increment sequence will do, as long as h1=1.
Some choices are better than others.
After using the increment hk, for every i, we have
a[i] ≤ a[i+hk];
that is, all elements spaced hk apart are sorted.
The file is said to be hk-sorted.
What is an important property that should be valid?
An hk-sorted file that is then hk–1-sorted remains hk-sorted.
Shellsort – Example
Shellsort – Original sequence

Increment sequence: ht= [N/2], and hk = [hk+1/2].
Theorem 7.3

Statement:


The worst-case running time of Shellsort, using Shell’s
increments, is Θ(N2).
Proof:



The proof requires showing not only an upper bound on the
worst-case running time, but also showing that there exists
some input that actually takes Ω(N2) time to run.
We will prove the lower bound by constructing a bad case.
You should read the textbook for the upper bound.
Bad Case








Choose N to be a power of 2.
This makes all the increments even, except for the last increment.
Choose as input an array with the N/2 largest numbers in the even
positions and the N/2 smallest numbers in the odd positions.
For this example, the first position is position 1.
So, when we come to the last pass, the N/2 largest numbers are still in
even positions and the N/2 smallest numbers are still in odd positions.
The ith smallest number (i ≤ N/2) is thus in position 2i – 1 before the
beginning of the last pass.
Restoring the ith element to its correct place requires moving it i – 1
spaces in the array.
Thus, to merely place the N/2 smallest elements in the correct places
requires at least 1 + 2 + 3 + (N/2 – 1) = Ω(N2) work.
Bad Case – Example




Choose N to be a power of 2.
This makes all the increments even, except for the last increment.
Choose as input an array with the N/2 largest numbers in the even
positions and the N/2 smallest numbers in the odd positions.
Can you suggest a better sequence?
Hibbert’s Increments



1, 3, 7, 15, 31, …, 2k – 1.
Theorem 7.4. The worst case running time of Shell sort
using Hibbard’s increments is what?
Θ( N3/2 ).