Sorting
insertion sort
...
shell sort
increment sequence (decreasing, minimum
1) h_1, h_2, ... h_t
one phase: a[i] <= a[i +
h_k] became h_k
sorted
Hibbard increment sequence : 1, 3, 7,.. 2^k -1
consecutive increments have no common factors
worst case running time Big_theta(n^3/2)
some sequence {1, 5, 19, 41, 109 ... } is very
efficient O(n^7/6)
Sedgewick increment sequence
the minimum case is h_k = 1. It has a special
name, bubbleSort
pseudo code
bubbleSort( Comparable [ ]
a )
for int i = 0;
i < a.length-1; i++
for int j = 0; j < a.length-1; j++
if a[j] > a[j+1]
swap a[j] a[j+1]
Advantage
The code is very simple and obviously correct.
Disadvantage
It is most inefficient. The worst case running time is
quadratic O(n^2).
heap sort
1 build BinaryHeap O(n)
2 deleteMin n times, each time O(
log n)
therefore the worst case running time of
heapSort is O( n log n)
but it needs two arrays. To avoid that
put the recently deleteMin into the just emptied hole. However,
the order of the sorted data will be reversed (from low index to high
index will be decreasing order). We can amend that by using
(max)heap (parent is larger than children).
pseudo code
heapSort( Comparable [ ] a
)
// build heap
for int
i=a.length/2; i>=0; i++
percolateDown(a, i, a.length)
// sort by
deleteMax and put it at the end
for int
i=a.length-1; i>0, i++
swap(a, 0, i)
percolateDown(a, 0, i)
merge sort
use divide and conquer (the result is a beautiful
recursive program)
pseudo code
mergeSort( Comparable [ ]
a, Comparable [ ] tmp, int left, int right )
if left
< right
int center = (left + right) / 2
mergeSort( a, tmp, left, center )
mergeSort( a, tmp, center+1, right )
merge( a, tmp, left, center+1, right )
It is based on "merge" which merges two sorted arrays into one
in linear time.
Analysis of the worst case running time
T(1) = 1
T(n) = 2T(n/2) +
n (the last term is the time
to merge)
Solving this recurrence using Master method
(read the note how to solve
recurrence )
T(n) = O(n log n)
Disadvantage
must use an extra array (tmp) and waste time to copy tmp back to
the original array.
quick sort
....
last update 12 Nov 2008