Look at the sorting algorithm demonstrations here : http://www.solidware.com/sort/
Here is an algorithm description for a bubble sort
Start with a list of N numbers in an array
Go through the entire list, one item at a time
At each item, compare it to the next item in the list
If these neighbors are out of order, then swap them
Go through the entire list again and again, making N passes
(1) Explain why this description does NOT correctly describe the algorithm in the demo.
(2) Write a similar description for a selection sort.
(3) Which of the 4 demo algorithms have efficiency O(N^2) ?
If
a O(N^2) algorithm requires 1000 iterations to sort N numbers,
how
many iterations will be required to sort 5N numbers (5 times as many numbers)?
(4) Use a Java IDE to write a program that does the following:
Input N, the number of items to be placed in a list - it must be even
Create an array for N integers
Fill this array with the numbers: 2, 4, 6, .. N-2, N , N-1, N-3, .. ,3,1
so it starts with even numbers in ascending order,
followed by odd numbers in descending order.
For example, N = 10 --> 2, 4, 6, 8, 10, 9, 7, 5, 3, 1
Execute either an insertion sort or a quick sort method to arrange
the numbers in descending order (largest first, smallest last)
Write both methods, and let the user choose which one to use.
Print the first 4 numbers and the last 4 numbers in the array.
(5) Using a clock and your program, compare the efficiency of the
two sorting methods on
longer
and longer lists.
(6) State the Big O efficiency of the quick-sort.
Answers
(1) The demo does not go through the entire list each time. Each pass is 1 item shorter, as the biggest items build up at the sorted end (red). So the last statement is not correct.
(2) Start at position 1
Find
the smallest item in the list
Swap the
smallest item with the item in position 1
Now
start at position 2
Find the smallest item
in the list from position 2 to N
Swap this smallest
item with the item in position 2
repeat at position 3,
4, ... to N-1
(3) Bubble sort, insertion sort, and selection sort all have O(n^2)
efficiency.
They all make N passes through the list,
doing N (or N/2) comparisons per pass
So they do N^2 or
N^2/2 iterations, but the /2 doesn't help much
(4) Check your own work here
(5) The quick sort is a LOT faster
(6) Quick sort efficiency is O( n log n)
That's because it breaks the list
into 2 sections, then works on each section.
The
breaking in 2 means it is log2n passes (sort of ... it's complicated)
Just
MEMORIZE it - quick-sort is O(n log n)
For some brief desctiptions of sorting algorithms and efficiency, read:
http://people.cs.uct.ac.za/~bmerry/manual/algorithms/sorting.html
If the middle element in the array is very large or very small, the sort becomes slower. To reduce the chances of this, you can take median of the first, middle and last elements and put it in the middle.
In a degenerate case, Quick sort could also recurse to a very deep level and cause a stack overflow. One way to avoid this is to keep track of the level of recursion (e.g. by passing it as a parameter) and switch to a simpler sort (like selection sort) if the recursion is too deep.