Sorting

Sorting means putting things in order.  For example, if you drop a stack of paper on the floor, and the pages are all mixed up, you need to put them in order again.

There are a variety of algorithms (methods) for accomplishing this task.  We'll start with typical human algorithms, written in human terms (pseudo-code).  

You'll only really understand this problem if you do it once.  Maybe you can get your teacher to throw some papers on the floor.  Otherwise, try some of these "real world" problems:

• Take a shuffled deck of 52 cards.  Put them in order - all 4 two's first, then the threes, etc finishing with jacks, queens, kings, aces
• Write the words of this sentence in alphabetical order without leaving anything out, and don't make any duplicates.
• Write the names of all the students in a classroom.  Write the list once sorted by last name.  Then write the list sorted by first name.

Do you use the same (or similar) methods for each problem?  Or is there a best method for each problem?

Simple Sort Algorithm

In a computer (program), things aren't written on pieces of paper.  And you can't "look" at all the data at once.  Computers must look at just one or two things at a time and compare them.  Here is an example program implementing an algorithm called a Simple Sort.  That name is used because the program is very simple.  A human being probably would not sort anything this way.

Psuedocode

    Compare each item to every other item
    Swap them if they are out of order
    Keep going until you compared every position to every other position

Java Code for Simple Sort

Start with the array {6,8,4,5} and trace the code above (on paper).  You will need a lot of paper, and you need to write down the array each time it changes.  The following table will help:

Now you can download the following program and run it, to see whether you were correct:   SimpleSort.java
Try some longer arrays, like with 10 numbers, and see whether it "always" works correctly.

This Simple Sort algorithm does seem to work, but there is probably no proof that it ALWAYS works.  It is easy to write, but it does a lot of extra comparisons.  That is both inefficient and perhaps unreliable.  There are several better algorithms, as listed below.

REAL Sorting Algorithms

We will look at 4 standard sorting algorithms

• Bubble Sort - compares neighbors only
• Selection Sort - find largest, swap into position 1, then repeat at position 2, etc
• Insertion Sort - starting with a sorted list, add an item by inserting it in the correct place
• Merge Sort - Divide the list in half, then again in half, etc until there are only pairs, then sort the pairs
                           Then merge the pairs, then the quads, etc.
• Quick Sort  -  read the explanation here

The first three are written with doubly nested loops, so they are about equally fast.

The Quick Sort is a lot more complex, but much faster.  IB SL students don't need to be able to program this, but we will have a look at how it works.

ACTION!

The following demonstration Applet shows the different algorithms in action:  http://math.hws.edu/TMCM/java/xSortLab/  

You need to watch each algorithm enough times until you can predict what will happen next at each step.  Spend some time on this.  Start with the Bubble Sort, then move on to the tasks below.  Then come back and watch the Selection Sort in action and do the tasks below.  Then do the Insertion Sort.

READING

Look at the IBO standard algorithms here :  http://ibcomp.fis.edu/ibo/Algorithms.htm  

Bubble Sort

1. Watch the demo Applet until you KNOW how the Bubble Sort works.  
2. Starting with the array  {3 , 4 , 1 , 5 , 2}, assume the Bubble Sort swaps larger values toward the right.
   Write down EXACTLY what changes will occur, in the correct order.
3. Take the Simple Sort as a starting point.  Change the if... command so that it compares  nums[x] > nums[x + 1] .
   Then it is always comparing neighbors.  Get it to work correctly to produce a sorted list at the end.
   You need to write the loops a bit differently to make it work.
4. Once you get it working, try a few different sized lists - 10 items, 20 items, 30 itmes.

Selection Sort

1. Watch the demo Applet until you KNOW how the Selection Sort works.  
2. Starting with the array  {3 , 4 , 1 , 5 , 2}, assume the Selection Sort swaps larger values toward the right.
   Write down EXACTLY what changes will occur, in the correct order.
3. Take the Simple Sort as a starting point.  The x loop needs to search for the LARGEST (or smallest)
   item in the list.  Make it do that.  Then it needs to SWAP with the first (or second or third).
   Get it to work correctly to produce a sorted list at the end.
   
4. Once you get it working, try a few different sized lists - 10 items, 20 items, 30 itmes.

Insertion Sort

1. Watch the demo Applet until you KNOW how the Insertion Sort works.  
2. Starting with the array  {3 , 4 , 1 , 5 , 2}, assume the Insertion Sort swaps larger values toward the right.
   Write down EXACTLY what changes will occur, in the correct order.
3. Find a "correct" Insertion Sort algorithm as Java code - search the web.  Put it into your program
   and get it working correctly.

Merge Sort

• Watch the demo - you will probably be confused.  Discuss it with the teacher.