Sorting Practice

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 log₂n 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

Bubble sort

Algorithm

Scan through the array from left to right, comparing adjacent elements. Whenever two adjacent elements are out of order, swap them. Repeat this until the array is sorted.

Efficiency

O(n²)

Pros

Simple to implement and understand, but not much more so than several more efficient sorts
Will be very quick on an already sorted list

Cons

Probably the slowest sort ever invented

Notes

Don't bother learning this sort. There are other sorts which are just as easy to implement and much faster. Although there are some time saving modifications that can be made (e.g. keeping track of the last swap in the previous pass, and only going up to there in the current pass), they aren't worth it.

Selection sort

Algorithm

Search the array for the largest element, and swap it with the element at the end. Then repeat for just the first n - 1 elements, then for the first n - 2 etc. This extracts the elements individually in reverse order.

Efficiency

O(n²)

Pros

Easy to implement

Cons

Is no faster on a partially sorted array

Notes

This is a reasonable sort to use for sorting a fairly small number of items, and my personal favourite of the O(n²) sorts.

Insertion sort

Algorithm

The first part of the list is sorted and the remainder is unsorted. To begin with, all elements are in the unsorted part. Go through the elements in the unsorted part sequencially and insert each into the sorted part by searching for it's correct position with a linear search or a binary search.

Efficiency

O(n²)

Pros

Fairly easy to implement with a linear search
If a backwards linear search is used, it is much faster on an partially sorted array

Cons

On an array, insertion is slow because all the elements after it have to be moved up.

Notes

This sort isn't especially useful by itself (although it is a respectable O(n²) sort), but forms the basis of Shell sort.

Quicksort

Algorithm

Save the value of the middle element of the array. Have a "left" pointer that starts at the first element and moves right and a "right" pointer that starts at the last element and moves left. Repeat the following operation until the pointers cross:

Scan with the left pointer until an element larger or equal to the saved value is found.
Scan with the right pointer until an element smaller or equal to the saved value is found.
If the pointers haven't crossed yet, swap the values they point to and manually advance both pointers one position.

Then recursively sort the elements in the ranges [start, right] and [left, end].

Efficiency

O(n.log n) on average

Pros

Extremely fast on average

Cons

Fairly tricky to implement and debug
Very slow in the worst case (but see notes)
In the worst case, could cause a stack overflow

Notes

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.