Transcript Sorting

Sorting
Gordon College
1
Sorting
• Consider a list
x 1, x 2, x 3, … x n
• We seek to arrange the elements of the
list in order
– Ascending or descending
• Some O(n2) schemes
– easy to understand and implement
– inefficient for large data sets
2
Categories of Sorting Algorithms
1. Selection sort
– Make passes through a list
– On each pass reposition correctly
some element
Look for smallest in list and replace 1st element, now start the
process over with the remainder of the list
3
Selection
Recursive Algorithm
If the list has only 1 element
ANCHOR
stop – list is sorted
Else do the following:
a. Find the smallest element and place in front
b. Sort the rest of the list
4
Categories of Sorting Algorithms
2. Exchange sort
– Systematically interchange pairs of elements
which are out of order
– Bubble sort does this
Out of order, exchange
In order, do not exchange
5
Bubble Sort Algorithm
1. Initialize numCompares to n - 1
2. While numCompares!= 0, do following
a. Set last = 1
// location of last element in a swap
b. For i = 1 to numPairs
if xi > xi + 1
Swap xi and xi + 1 and set last = i
c. Set numCompares = last – 1
End while
6
Bubble Sort Algorithm
1. Initialize numCompares to n - 1
2. While numCompares!= 0, do following
a. Set last = 1
// location of last element in a swap
b. For i = 1 to numPairs
if xi > xi + 1
Swap xi and xi + 1 and set last = i
c. Set numCompares = last – 1
End while
45 67 12 34 25 39
45 12 67 34 25 39
45 12 34 67 25 39
45 12 34 25 67 39
45 12 34 25 39 67
45 12 34 25 39 67
12 45 34 25 39 67
12 34 45 25 39 67
12 34 25 45 39 67
12 34 25 39 45 67
…
Allows it to quit if
In order
Try: 23 12 34 45 67
Also allows us to
Label the highest as
sorted
7
Categories of Sorting Algorithms
3. Insertion sort
– Repeatedly insert a new element into an already
sorted list
– Note this works well with a linked list
implementation
8
Example of Insertion Sort
• Given list to be sorted
67, 33, 21, 84, 49, 50, 75
– Note sequence of steps carried out
9
Improved Schemes
• These 3 sorts - have computing time O(n2)
• We seek improved computing times for sorts of large data
sets
• There are sorting schemes which can be proven to have
average computing time
O( n log2n )
• No universally good sorting scheme
– Results may depend on the order of the list
10
Comparisons of Sorts
• Sort of a randomly generated list of 500 items
– Note: times are on 1970s hardware
Algorithm
•Simple selection
•Heapsort
•Bubble sort
•2 way bubble sort
•Quicksort
•Linear insertion
•Binary insertion
•Shell sort
Type of Sort
Selection
Selection
Exchange
Exchange
Exchange
Insertion
Insertion
Insertion
Time (sec)
69
18
165
141
6
66
37
11
11
Indirect Sorts
• What happens if items being sorted are
large structures (like objects)?
– Data transfer/swapping time unacceptable
• Alternative is indirect sort
– Uses index table to store positions of the objects
– Manipulate the index table for ordering
12
Heaps
A heap is a binary tree with properties:
1. It is complete
A
B
C
D
•
•
H
I
E
G
F
J
Each level of tree completely filled
Except possibly bottom level (nodes in left most
positions)
Complete Tree (Depth 3)
2. It satisfies heap-order property
•
Data in each node >= data in children
13
Heaps
Which of the following are heaps?
A
B
C
14
Maximum and Minimum Heaps Example
55
40
52
50
20
11
10
25
5
10
22
(A) Maximum Heap (9 nodes)
(B) Maximum Heap (4 nodes)
10
5
11
15
50
10
25
30
15
20
52
55
30
40
22
(C) Minimum Heap (9 nodes)
(D) Minimum Heap (4 nodes)
15
Implementing a Heap
• Use an array or vector
• Number the nodes from top to bottom, then
on each row – left to right.
• Store data in ith node in ith location of array
(vector)
16
Implementing a Heap
• Note the placement of the nodes in the
array
41
17
Implementing a Heap
• In an array implementation children of ith
node are at myArray[2*i] and
myArray[2*i+1]
• Parent of the ith node is at
mayArray[i/2]
18
Basic Heap Operations
• Constructor
– Set mySize to 0, allocate array (if dynamic array)
• Empty
– Check value of mySize
• Retrieve max item
– Return root of the binary tree, myArray[1]
19
Basic Heap Operations
• Delete max item (popHeap)
– Max item is the root, replace with last node in
tree
Result called a
semiheap
– Then interchange root with larger of two children
– Continue this with the resulting sub-tree(s) –
result is a new heap.
20
Exchanging elements when
performing a popHeap()
63
18
v[0]
v[0]
30
v[2]
v[1]
25
10
v[4]
v[3]
5
v[7]
3
v[8]
30
40
8
v[5]
Before a deletion
25
10
38
v[4]
v[3]
v[6]
v[7]
v[9]
v[2]
v[1]
5
18
40
3
v[8]
8
v[5]
38
v[6]
63
v[9]
After exchanging the root
and last element in the heap
21
Adjusting the heap for popHeap()
...
40
40
v[0]
v[0]
...
18
38
v[2]
v[2]
8
v[5]
38
v[6]
Step 1: Exchange 18 and 40
8
v[5]
18
v[6]
Step 2: Exchange 18 and 38
22
Percolate Down Algorithm
converts semiheap to heap
r = current root node
1. Set c = 2 * r //location of left child n = number of nodes
2. While r <= n do following // must be child(s) for root
a. If c < n and myArray[c] < myArray[c + 1]
Increment c by 1 //find larger child
b. If myArray[r] < myArray[c]
i. Swap myArray[r] and myArray[c]
ii. set r = c
iii. set c = 2 * r
else
Terminate repetition
End while
23
Basic Heap Operations
• Insert an item (pushHeap)
– Amounts to a percolate up routine
– Place new item at end of array
– Interchange with parent so long as it is greater
than its parent
24
Example of Heap Before and After
Insertion of 50
63
63
v[0]
v[0]
30
40
v[2]
v[1]
25
10
v[4]
v[3]
5
v[7]
3
v[8]
30
18
v[9]
(a)
8
v[5]
40
v[2]
v[1]
38
25
10
v[6]
v[4]
v[3]
5
v[7]
8
3
v[8]
18
v[9]
v[5]
38
v[6]
50
v[10]
(b)
25
Reordering the tree for the insertion
63
63
63
v[0]
...
30
...
v[0]
v[1]
...
50
v[9]
v[0]
30
...
v[1]
30
v[4]
25
v[10]
Step 1 Compare 50 and 25
(Exchange v[10] and v[4])
18
v[9]
...
50
v[1]
v[4]
18
...
50
v[4]
25
v[10]
Step 2 Compare 50 and 30
(Exchange v[4] and v[1])
18
25
v[9]
v[10]
Step 3 Compare 50 and 63
(50 in correct location)
26
Heapsort
• Given a list of numbers in an array
– Stored in a complete binary tree
• Convert to a heap (heapify)
– Begin at last node not a leaf
– Apply “percolated down” to this subtree
– Continue
27
Example of Heapifying a Vector
9
17
12
30
65
50
4
20
60
19
Initial Vector
28
Example of Heapifying a Vector
9
17
12
30
65
50
4
20
60
19
adjustHeap() at 4 causes no changes
(A)
29
Example of Heapifying a Vector
9
17
12
65
30
50
4
20
60
19
adjustHeap() at 3 moves 30 down
(B)
30
Example of Heapifying a Vector
9
60
12
65
30
50
4
20
17
19
adjustHeap() at 2 moves 17 down
(C)
31
Example of Heapifying a Vector
9
60
12
50
65
30
4
20
9
17
19
adjustHeap() at 2 moves 17 down
(C)
60
65
30
12
50
4
20
17
19
adjustHeap() at 1 moves 12 down two levels
(D)
32
Example of Heapifying a Vector
9
60
65
30
12
50
4
20
65
17
19
60
50
adjustHeap() at 1 moves 12 down two levels
(D)
30
12
19
4
20
17
9
adjustHeap() at 0 moves 9 down three levels
(E)
33
Heapsort
• Algorithm for converting a complete binary
tree to a heap – called "heapify"
For r = n/2 down to 1:
Apply percolate_down to the subtree
in myArray[r] , … myArray[n]
End for
• Puts largest element at root
n = index for last node in tree
therefore n/2 is parent
34
Heapsort
• Now swap element 1 (root of tree) with last
element
– This puts largest element in correct location
• Use percolate down on remaining sublist
– Converts from semi-heap to heap
35
Heapsort
• Again swap root with rightmost leaf
60
• Continue this process with shrinking sublist
60
36
Heapsort Algorithm
1. Consider x as a complete binary tree, use
heapify to convert this tree to a heap
2. for i = n down to 2:
a. Interchange x[1] and x[i]
(puts largest element at end)
b. Apply percolate_down to convert binary
tree corresponding to sublist in
x[1] .. x[i-1]
37
Example of Implementing heap sort
int arr[] = {50, 20, 75, 35, 25};
vector<int> v(arr, 5);
75
35
20
50
25
Heapified Tree
38
Example of Implementing heap sort
Calling popHeap() with last = 5
deletes 75 and stores it in h[4]
Calling popHeap() with last = 4
deletes 50 and stores it in h[3]
35
50
35
20
20
25
75
50
25
75
39
Example of Implementing heap sort
Calling popHeap() with last = 3
deletes 35 and stores it in h[2]
Calling popHeap() with last = 2
deletes 25 and stores it in h[1]
25
20
50
20
35
75
25
50
35
75
40
Heap Algorithms in STL
• Found in the <algorithm> library
– make_heap()
heapify
– push_heap()
insert
– pop_heap()
delete
– sort_heap()
heapsort
41
Priority Queue
• A collection of data elements
– Items stored in order by priority
– Higher priority items removed ahead of lower
Implementation ?
42
Implementation possibilities
list (array, vector, linked list)
insert – O(1)
remove max - O(n)
ordered list
insert - linear insertion sort O(n)
remove max - O(1)
– Heap (Best)
Basic operations have O(log2n) time
43
Priority Queue
Basic Operations
– Constructor
– Insert
– Find, remove smallest/largest (priority) element
– Replace
– Change priority
– Delete an item
– Join two priority queues into a larger one
44
Priority Queue
• STL priority queue adapter uses heap
priority_queue<BigNumber, vector<BigNumber> > v;
cout << "BIG NUMBER DEMONSTRATION" << endl;
for(int k=0;k<6;k++)
{
cout << "Enter BigNumber: "; cin >> a;
v.push(a);
}
cout<<"POP IN ORDER"<<endl;
while(!v.empty())
{
cout<<v.top()<<endl;
v.pop();
45
}
Quicksort
• More efficient exchange sorting scheme
– (bubble sort is an exchange sort)
• Typical exchange: involves elements that are far apart
Fewer interchanges are required to correctly position an
element.
• Quicksort uses a divide-and-conquer strategy
A recursive approach:
– The original problem partitioned into simpler
sub problems
– Each sub problem considered independently.
• Subdivision continues until sub problems
obtained are simple enough to be solved directly
46
Quicksort
Basic Algorithm
• Choose an element - pivot
• Perform sequence of exchanges so that
<elements less than P> <P> <elements greater than P>
– All elements that are less than this pivot are to its left and
– All elements that are greater than the pivot are to its right.
• Divides the (sub)list into two smaller sub lists,
• Each of which may then be sorted independently in
the same way.
47
Quicksort
recursive
If the list has 0 or 1 elements,
ANCHOR
return. // the list is sorted
Else do:
Pick an element in the list to use as the pivot.
Split the remaining elements into two disjoint groups:
SmallerThanPivot = {all elements < pivot}
LargerThanPivot = {all elements > pivot}
Return the list rearranged as:
Quicksort(SmallerThanPivot),
pivot,
Quicksort(LargerThanPivot).
48
Quicksort Example
• Given to sort:
75, 70, 65, 84 , 98, 78, 100, 93, 55, 61, 81, 68
• Select arbitrarily pivot: the first element 75
• Search from right for elements <= 75, stop at
first match
• Search from left for elements > 75, stop at first
match
• Swap these two elements, and then repeat this
process. When can you stop?
49
Quicksort Example
75, 70, 65, 68, 61, 55, 100, 93, 78, 98, 81, 84
• When done, swap with pivot
• This SPLIT operation places pivot 75 so
that all elements to the left are <= 75 and
all elements to the right are >75.
• 75 is in place.
• Need to sort sublists on either side of 75
50
Quicksort Example
• Need to sort (independently):
55, 70, 65, 68, 61
and
100, 93, 78, 98, 81, 84
• Let pivot be 55, look from each end for
values larger/smaller than 55, swap
• Same for 2nd list, pivot is 100
• Sort the resulting sublists in the same
manner until sublist is trivial (size 0 or 1)
51
QuickSort Recursive Function
template <typename ElementType>
void quicksort (ElementType x[], int first int last)
{
int pos; // pivot's final position
if (first < last) // list size is > 1
{
split(x, first, last, pos); // Split into 2 sublists
quicksort(x, first, pos - 1); // Sort left sublist
quicksort(x,pos + 1, last); // Sort right sublist
}
}
23 45 12 67 32 56 90 2 15
52
template <typename ElementType>
void split (ElementType x[], int first, int last, int & pos)
{
ElementType pivot = x[first];
// pivot element
int left = first,
// index for left search
right = last;
// index for right search
while (left < right)
{
while (pivot < x[right])
// Search from right for
right--;
// element <= pivot
// Search from left for
while (left < right &&
// element > pivot
x[left] <= pivot)
left++;
if (left < right)
swap (x[left], x[right]);
}
// If searches haven't met
// interchange elements
}
// End of searches; place pivot in correct position
pos = right;
x[first] = x[pos];
x[pos] = pivot;
23 45 12 67 32 56 90 2 15
53
Quicksort
• Visual example of
a quicksort on an array
etc. …
54
QuickSort Example
v = {800, 150, 300, 650, 550, 500, 400, 350, 450, 900}
pivot
500
150
300
650
550
800
400
350
450
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
scanUp
scanDown
Pivot selected at random
55
QuickSort Example
Before the exchange
pivot
500
150
300
650
550
800
400
350
450
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
scanDown
scanUp
After the exchange and updates to scanUp and scanDown
pivot
500
150
300
450
550
800
400
350
650
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
scanUp
scanDown
56
QuickSort Example
Before the exchange
pivot
500
150
300
450
550
800
400
350
650
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
scanDown
scanUp
After the exchange and updates to scanUp and scanDown
pivot
500
150
300
450
350
800
400
550
650
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
scanUp
scanDown
57
QuickSort Example
Before the exchange
pivot
500
150
300
450
350
800
400
550
650
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
scanDown
scanUp
After the exchange and updates to scanUp and scanDown
pivot
500
150
300
450
350
400
800
550
650
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
scanDown scanUp
58
QuickSort Example
Pivot in its final position
400
150
300
450
350
500
800
550
650
900
v[0]
v[1] v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
400
150
300
450
350
500
800
550
650
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
v[0] - v[4]
quicksort(x, 0, 4);
v[6] - v[9]
quicksort(x, 6, 9);
59
QuickSort Example
pivot
pivot
Initial Values
After Scans Stop
300
150
400
450
350
300
150
400
450
350
v[0]
v[1]
v[2]
v[3]
v[4]
v[0]
v[1]
v[2]
v[3]
v[4]
scanDown
scanUp
scanDown
150
300
400
450
350
v[0]
v[1]
v[2]
v[3]
v[4]
quicksort(x, 0, 0);
scanUp
quicksort(x, 2, 4);
60
QuickSort Example
pivot
pivot
Initial Values
After Stops
650
550
800
900
650
550
800
900
v[6]
v[7]
v[8]
v[9]
v[6]
v[7]
v[8]
v[9]
scanDown
scanUp
scanDown scanUp
550
650
800
900
v[6]
v[7]
v[8]
v[9]
quicksort(x, 6, 6);
quicksort(x, 8, 9);
61
QuickSort Example
150
300
400
450
350
500
550
650
800
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
After Partitioning
Before Partitioning
400
450
350
350
400
450
v[2]
v[3]
v[4]
v[2]
v[3]
v[4]
150
300
350
400
450
500
550
650
800
900
v[0]
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
v[7]
v[8]
v[9]
62
Quicksort Performance
• O(n log2n) is the average case computing
time
– If the pivot results in sublists of approximately the
same size.
• O(n2) worst-case
12 34 45 56 78 88 90 100
– List already ordered or elements in reverse.
– When Split() repeatedly creates a sublist
with one element. (when pivot is always smallest or largest value)
99 45 12 67 32 56 90 2 15
What 2 pivots would result in empty sublist?
63
Improvements to Quicksort
12 34 45 56 78 88 90 100
• An arbitrary pivot gives a poor partition for nearly
sorted lists (or lists in reverse)
• Virtually all the elements go into either
SmallerThanPivot or LargerThanPivot
– all through the recursive calls.
• Quicksort takes quadratic time to do essentially
nothing at all.
64
Improvements to Quicksort
• Better method for selecting the pivot is the
median-of-three rule,
– Select the median (middle value) of the first, middle, and
last elements in each sublist as the pivot.
(4 10 6) - median is 6
• Often the list to be sorted is already partially
ordered
• Median-of-three rule will select a pivot closer to the
middle of the sublist than will the “first-element”
rule.
65
Improvements to Quicksort
• Quicksort is a recursive function
– stack of activation records must be maintained
by system to manage recursion.
– The deeper the recursion is, the larger this stack
will become. (major overhead)
• The depth of the recursion and the
corresponding overhead can be reduced
– sort the smaller sublist at each stage
66
Improvements to Quicksort
• Another improvement aimed at reducing the
overhead of recursion is to use an iterative
version of Quicksort()
Implementation: use a stack to store the first
and last positions of the sublists sorted
"recursively". In other words – create your own lowoverhead execution stack.
67
Improvements to Quicksort
• For small files (n <= 20), quicksort is worse
than insertion sort;
– small files occur often because of recursion.
• Use an efficient sort (e.g., insertion sort) for
small files.
• Better yet, use Quicksort() until sublists
are of a small size and then apply an efficient
sort like insertion sort.
68
Mergesort
• Sorting schemes are either …
• internal -- designed for data items stored in
main memory
• external -- designed for data items stored in
secondary memory.
• Previous sorting schemes were all internal
sorting algorithms:
– required direct access to list elements
• not possible for sequential files
– made many passes through the list
• not practical for files
69
Mergesort
• Mergesort can be used both as an internal
and an external sort.
• Basic operation in mergesort is merging,
– combining two lists that have previously been
sorted
– resulting list is also sorted.
70
Merge Algorithm
1. Open File1 and File2 for input, File3 for output
2. Read first element x from File1 and
first element y from File2
3. While neither eof File1 or eof File2
If x < y then
a. Write x to File3
b. Read a new x value from File1
Otherwise
a. Write y to File3
b. Read a new y from File2
End while
4. If eof File1 encountered copy rest of of File2 into File3.
If eof File2 encountered, copy rest of File1 into File3
71
Binary Merge Sort
• Given a single file
• Split into two files (alternatively into each file)
72
Binary Merge Sort
• Merge first one-element "subfile" of F1 with
first one-element subfile of F2
– Gives a sorted two-element subfile of F
• Continue with rest of one-element subfiles
73
Binary Merge Sort
• Split again
• Merge again as before
• Each time, the size of the sorted subgroups
doubles
74
Binary Merge Sort
• Last splitting gives two files each in order
• Last merging yields a
order
Note we always are
limited to subfiles of
single
file,
entirely
some
power
of 2
in
75
Natural Merge Sort
• Allows sorted subfiles of other sizes
– Number of phases can be reduced when file
contains longer "runs" of ordered elements
• Consider file to be sorted, note in order
groups
76
Natural Merge Sort
• Copy alternate groupings into two files
– Use the sub-groupings, not a power of 2
• Look for possible larger groupings
77
Natural Merge Sort
• Merge the corresponding sub files
EOF for F2, Copy
remaining groups from F1
78
Natural Merge Sort
• Split again,
alternating groups
• Merge again, now two subgroups
• One more split, one more merge gives sort
79
Natural Merge Sort
Split algorithm for natural merge sort
1. Open F for input and F1 and F2 for output
2. While the end of F has not been reached:
a. Copy a sorted subfile of F into F1 as follows: repeatedly
read an element of F and write it to F1 until the next
element in F is smaller than this copied item or the end
of F is reached.
b. If the end of F has not been reached, copy the next
sorted subfile of F into F2 using the method above.
End while.
80
Natural Merge Sort
Merge algorithm for natural merge sort
1.
Open F1 and F2 for input, F for output.
2.
Initialize numSubfiles to 0
3.
While not eof F1 or not eof F2
a.
While no end of subfile in F1 or F2 has been reached:
If the next element in F1 is less than the next element in F2
Copy the next element from F1 into F.
Else
Copy the next element from F2 into F.
End While
b.
If the eof F1 has been reached
Copy the rest of subfile F2 to F.
Else
Copy the rest of subfile F1 to F.
c.
Increment numSubfiles by 1.
End While
4.
Copy any remaining subfiles to F, incrementing numSubfiles by 1 for
each.
81
Natural Merge Sort
Mergesort algorithm
Repeat the following until numSubfiles is equal to 1:
1. Call the Split algorithm to split F into files F1 and
F2.
2. Call the Merge algorithm to merge corresponding
subfiles in F1 and F2 back into F.
Worst case for natural merge sort O(n log2n)
82
Natural MergeSort Example
sublist A
7
first
10
19
sublist B
25
12
mid
17
21
30
48
last
83
Natural MergeSort Review
tempVector
7
sublist A
7
10
sublist B
19
25
12
17
21
30
48
indexB
indexA
temp Vector
7
10
sublist A
7
indexA
10
19
sublist B
25
12
17
21
30
48
indexrB
84
Natural MergeSort Review
tempVector
7
10
12
sublist A
7
10
19
indexA
sublist B
25
12
17
21
30
48
indexB
So forth and so on…
temp Vector
7
10
12
17
19
sublist A
7
10
19
21
25
sublist B
25
indexA
12
17
21
30
48
indexB
85
Natural MergeSort Review
tempVector
7
10
12
17
19
21
sublist A
7
10
19
25
30
48
sublist B
25
12
17
21
30
48
last
indexB
indexA
tempVector
7
7
first
10
10
12
12
17
17
19
19
21
21
25
25
30
30
48
48
last
86
Recursive Natural MergeSort
(25 10 7 19 3 48 12 17 56 30 21)
[3 7 10 12 17 19 21 25 30 48 56]
(25 )
(25 10 7 19 3 )
(48 12 17 56 30 21 )
[3 7 10 19 25]
[12 17 21 30 48 56]
(25 10 )
(7 19 3 )
(48 12 17 )
(56 30 21 )
[10 25]
[3 7 19]
[12 17 48]
[21 30 56]
(10 )
(7 )
(19 3 )
(48 )
(12 17 )
(30 21 )
[21 30]
[12 17]
[3 19]
(19 )
(56 )
(3 )
(12 )
(17 )
(30 )
(21 )
87
Recursive Natural MergeSort
Call msort()
- recusive call1 to msort()
- recusive call2 to msort()
- call1 merge()
Level 0:
Level 1:
msort() : n/2
Level 2:
Level 3:
msort(): n/4
msort(): n/8
msort(): n/8
msort(): n/2
msort (): n/4
msort(): n/8
msort(): n/8
msort(): n/4
msort(): n/8
msort(): n/8
msort(): n/4
msort(): n/8
msort(): n/8
...
Level i:
88
Sorting Fact
• any algorithm which performs sorting using
comparisons cannot have a worst-case
performance better than O(n log n)
– a sorting algorithm based on comparisons
cannot be O(n) - even for its average runtime.
89
Radix Sort
• Based on examining digits in some base-b
numeric representation of items
• Least significant digit radix sort
– Processes digits from right to left
• Create groupings of items with same value in
specified digit
– Collect in order and create grouping with next significant
digit
90
Radix Sort
Order ten 2 digit numbers in 10 bins from
smallest number to largest number. Requires 2
calls to the sort Algorithm.
Initial Sequence:
Pass 0:
91 6 85 15 92 35 30 22 39
Distribute the cards into bins according
to the 1's digit (100).
30
91
22
92
0
1
2
3
4
35
15
85
6
5
6
39
7
8
9
91
Radix Sort
Final Sequence:
Pass 1:
91 6 85 15 92 35 30 22 39
Take the new sequence and distribute
the cards into bins determined by the
10's digit (101).
6
15
22
39
35
30
0
1
2
3
4
5
6
7
85
92
91
8
9
92
Sort Algorithm Analysis
• Selection Sort (uses a swap)
– Worst and average case O(n^2)
– can be used with linked-list (doesn’t require
random-access data)
– Can be done in place
– not at all fast for nearly sorted data
93
Sort Algorithm Analysis
• Bubble Sort (uses an exchange)
– Worst and average case O(n^2)
– Since it is using localized exchanges - can be
used with linked-list
– Can be done in place
– O(n^2) - even if only one item is out of place
94
Sort Algorithm Analysis
sorts actually used
• Insertion Sort (uses an insert)
– Worst and average case O(n^2)
– Does not require random-access data
– Can be done in place
– It is fast (linear time) for nearly sorted data
– It is fast for small lists
Most good sorting methods call Insertion Sort for
small lists
95
Sort Algorithm Analysis
sorts actually used
• Merge Sort
– Worst and average case O(n log n)
– Does not require random-access data
– For linked-list - can be done in place
– For an array - need to use a buffer
– It is not significantly faster on nearly sorted data
(but it is still log-linear time)
96
Sort Algorithm Analysis
sorts actually used
• QuickSort
– Worst O(n^2)
– Average case O(n log n) [good time]
– can be done in place
– Additional space for recursion O(log n)
– Can be slow O(n^2) for nearly sorted or reverse
data.
– Sort used for STL sort()
97
End of sorting
98