LECTURE 21
Sorting
Introduction
- General problem: Have
an array of n data items (records) to be sorted on some key (field).
- e.g. n integers to be
sorted in increasing order from smallest to largest:
- Want algorithms (methods,
paradigms,
) to do this efficiently - compact and fast.
- Compact : little extra
space needed
- Speed : running time
of the algorithm [ Best Case? Worst Case? Average Case? ]
Order notation
- Allows description of
the "running time" of the algorithm as a function of
the size, n, of the input
- Algorithm is O(f(n))
if running time is bounded by c f(n) (where c is a positive constant)
for all inputs of size n.
- Note: For large n, 0.001
n3 >> 1E6 n2 , so c "doesn't matter".
- e.g: A sorting algorithm
technique is O(n^2) if its "running time" is proportional
to n^2 for input arrays of length n.
- Algorithm is if running
time is greater than d g(n) (where d is a positive constant) for
some input of size n. O provides an upper bound on running time,
while provides a lower bound.
For sorting:
- Running time can measure
the number of swaps (exchanges of array elements) or the number
of comparisons.
- Theoretical result:
sorting problem is (n log n) (i.e. cannot do better)
- Practical result: There
exist algorithms that work in O(n log n) time
- For small n, (e.g. n<100),
some simple O(n^2) algorithms are faster than the elegant O(n log
n) ones.
Bubble sort
- Imagine a vertical array,
where smaller elements are "lighter" and bubble up to
the top during sorting.
- Make repeated, bottom-to-top
passes, exchanging adjacent elements as we go.
- On the first pass, the
lightest element bubbles up to the top, etc.
A(1) small
A(2) .
A(3) .
.
A(n) big
Bubble sort Algorithm
for i = 1 to n do
for j = n downto i + 1 do
if A[j] < A[j-1] then
Swap(A[j] , A[j-1])
- Note that, after i passes, the array elements A[1], A[2],
A[i] are in their final, sorted order.
- Need a total of n-1
passes, because if n-1 smallest elements are sorted, then so is
the nth, largest one.
- This process requires
O(n^2) swaps, O(n^2) comparisons, and only 1 extra record in the
swap procedure.
Insertion Sort
- On pass i, the array
element A[i] assumes its rightful position among the A[1], A[2],
, A[i-1], which were already sorted on previous passes.
- Basic Idea : For each
I from 2 to n, move A[i] to position j <= i such that A[i]
< A[k} for j k < i, and either A[i] A[j-1] or j = 1.
- Convenient to set A[0]
= - to avoid checking j=1.
Algorithm for Insertion
Sort
A[0] = -MaxInt
for i = 2 to n do begin
j = i
while A[j] < A[j-1] do
begin
Swap(A[j], A[j-1])
j = j - 1
end
end
- Note that the partial
results are not useful (element A[i may take any place amongst
the elements A[1], A[2],
, A[i1] on pass i)
- Again requires O(n^2)
swaps, O(n^2) comparisons, little extra space.
Selection sort
- On pass I, select the smallest array element A[j] amongst
A[i], A[i + 1],
, A[n]
- Then, swap A[i] and
A[j]
- This leaves elements
A[1], A[2],
,A[i] in their final, sorted order.
- Running time is still
O(n2), but there are only n-1 swaps; may be useful if records
are large and swaps are "expensive"
Algorithm for Selection
Sort
for i = 1 to n - 1 do begin
j = i
Min = A[i]
for k = i + 1 to n do
if A[k] < Min then begin
Min = A[k]
j = k
end
end
Swap( A[i], A[j])
end
Shell Sort
- On pass 1 sort n/2 pairs
of elements (A[i], A[n/2 + i]), for 1 i n/2
- On pass 2 sort n/4 4-tuples
of elements (A[I], A[n/4 + i], A[n/2 + i], A[3n/4 + i]), for 1
i n/4
- On pass j, sort n/2j
2j-tuples of elemts (A[i + kn/2j]), 0 k 2j - 1, for 1 i n/2j
- Use insertion sort on
the tuples in each pass, stopping once 2 elements in the proper
order are encountered
- Analysis shows O(n^1.5)
running time
Better algorithms
- Shell sort is reasonably
fast and easy to implement
- Quicksort is O(n log
n) in average case, but O(n2) in worst
- Heapsort is O(n log
n) in average and worst case, but the constant is big, so worse
algorithms better for "small" problems.
Go back to lecture menu
Go back to main page
Copyright © 1996 McGill University. All rights reserved.