Ordenamiento

Quick Sort

Biostatistics 615/815 Lecture 8

Notes on Problem Set 2
Union Find algorithms Results were very positive! You should be getting comfortable compiling, debugging and executing C codeQuestion 1
How many random pairs of connections are required to connect 1,000 objects?

• Answer: ~3,740
Useful notes:

• Number of non-redundant links to controls loop • Repeat simulationto get a better estimates

Question 2
Path lengths in the saturated tree…

• • •

~1.8 nodes on average ~5 nodes for maximum path

Random data is far from worst case
Worst case would bepaths of log2 N (10) nodes

Path lengths can be calculated using weights[]

Question 3
Tree height or weight for optimal quick union operations?

• •

Using height ensures that longest path isshorter. Pointing the root of a tree with X nodes to the root of a tree with Y nodes, increases the average length of all paths by X/N.

• Smallest average length and faster Find operationscorrespond to choosing X < Y.

• Easiest to check if you use the same sequence of
random numbers for both problems.

Last Lecture: Shell Sort
Gradually bring order to array by:

• •

Sortingsub-arrays including every kth element Using a series of step sizes k, ending with k = 1

Each pass handles nearly sorted arrays where insertion sort is efficient Theoretically, N (log N)2 complexity ispossible

Pictorial Representation

Array gradually gains order Eventually, we approach the ideal case where insertion sort is O(N)

Today: Quick Sort
Most widely used sorting algorithm

•Possibly excluding those bubble sorts that
should be banished!

Extremely efficient

• O(N log N)
Divide-and-conquer algorithm

The Inventor of Quicksort
Sir Charles A. R. Hoare

• 1980ACM Turing Award
British computer scientist

• Studied statistics as a graduate student
Made major contributions to developing computer languages

C. A. R. Hoare Quote
“I conclude that there...