Sorting algorithms

An ALGORITHM is a precise set of instructions, which, if followed correctly, enables anyone to solve the problem.

Given the set of numbers 6, 1 ,2 7, 9, 4 , 3 and you’re asked to arrange them in order. What a silly question! Anyone could do that in their head! True, but ignoring the issue of time, what if you were stuck with only your pen, paper, and a thousand numbers to sort?

Method 1 –
1) Go through the whole list, and find the smallest number in the list.
2) Take out that number.
3) Repeat steps 1 & 2 until you have arranged all the numbers.

Now, I don’t think that’s very wise. That would take a long time, because for a list of 7 numbers, you would have to go through the entire list 7 times, which would be looking through 49 numbers! So we have to come up with some better algorithm.

[Edit : Sorry, I meant ’28 times’ since when you take a number out it becomes one shorter]

Introducing the “Bubble Sort” algorithm.

1) Compare the 1st & 2nd; swap if necessary.
2) Compare the 2nd & 3rd, swap if necessary.
3) Continue comparing until you reach the end of the list.
4) If no swaps have occured, stop. Otherwise, repeat from top; finish one less from the bottom.

We finish one less from the bottom because you can be sure that the bottom number will be in the correct place. Here is the example :

origin-|1st  |2nd |3rd |4th |5th |
al list|pass |pass|pass|pass|pass|
----------------------------------
   6   |  1  | 1  | 1  | 1  | 1  |
   1   |  2  | 2  | 2  | 2  | 2  |
   2   |  6  | 6  | 4  | 3  | 3. |
   7   |  7  | 4  | 3  | 4. | 4. |
   9   |  4  | 3  | 6. | 6. | 6. |
   4   |  3  | 7. | 7. | 7. | 7. |------
   3   |  9. | 9. | 9. | 9. | 9. | Total
----------------------------------------
Compar-|  6  | 5  | 4  | 3  | 2  | 20
isons  |     |    |    |    |    |  
----------------------------------------
Swaps  |  4  | 2  | 2  | 1  | 0  | 9
----------------------------------------
* dots (.) mark numbers which are definitely correct.

As you can see, this bubble sort method is better than the previous method. (20 comparisons, in contrast to the earlier 49 comparisons).

Next method, the SHUTTLE SORT

1) Compare 1st & 2nd; swap if necessary.
2) Compare next two; swap if necessary.
3) If swap occurs, move back and compare the previous two.
4) Repeat step 3 until no swap occurs or reached beginning of list.
5) Continue from last position until end of list.

eg.

 Set of numbers : 5,2,1,3
 
1) Compare 1st two numbers   2) Compare next two,  
   and swap if necessary        swap if necessary     
                                                      
        5   2                     2                    
          X                                           
        2   5                     5   1               
                                    X
        1                         1   5              
 
        3                         3                  
        
3) Since swap occured,
   move back and compare previous two
             
              2   1
                x
              1   2
              
              5   5
              
              3   3
              
4) Since at beginning of list,  5) Since swap occurs,
   move back and compare next      move back and compare
   two     
   
       1                              1
   
       2                              2   2
                                        X 
       5   3                          3   3
         X
       3   5                          5
       
 Since no swap occurs, and we are at end of list, stop. 
 
 Final list of numbers -  1, 2, 3, 5.
 

Now doing it for our previous example,

Square brackets indicate numbers being compared

origin-|
al list|
-------------------------------------------|
  [6]  |  1  |  1  |  1  |  1  |  1  |  1  |
  [1]  | [6] |  2  |  2  |  2  |  2  |  2  |
   2   | [2] | [6] |  6  |  6  |  4  |  3  |
   7   |  7  | [7] | [7] |  7  |  6  |  4  |
   9   |  9  |  9  | [9] | [9] |  7  |  6  |
   4   |  4  |  4  |  4  | [4] | [9] |  7  |------    
   3   |  3  |  3  |  3  |  3  | [3] |  9  |TOTAL 
--------------------------------------------------
Compar-|  1  |  2  |  1  |  1  |  4  |  5  |  14
isons  |     |     |     |     |     |     |
--------------------------------------------------
Swaps  |  1  |  1  |  0  |  0  |  3  |  4  |  9
--------------------------------------------------

You can see that for this case, the shuttle sort requires less comparisons than the bubble sort, although, it is a bit more ‘complicated’ to shuttle backwards and forwards. Up to you which method you like. But in most cases, the shuttle sort requires less comparisons than its counterpart.

About max no. of comparisons and swaps :

For a list of ‘n’ numbers, max number of comparisons in bubble sort is :

(n-1) + (n-2) + (n-3) + ... + 1 = (1/2)*(n-1)*n

while the shuttle sort is

1 + 2 + ... + (n-1) = (1/2)*(n-1)*n

So they do have the same ‘max comparison’ values, although the shuttle swap normally finishes with fewer comparisons.

Looking at the max comparison values, the highest power of ‘n’ is n^2, so these algorithms are defined to have order n^2 / 2 / quadratic. An ‘order’ of an algorithm is a measure of how many steps are required as a function of the size of a problem. In other words, algorithm with higher orders would not be prefered if there were lower order algorithms available.

2 thoughts on “Sorting algorithms”

  1. Oh yes. You “Sort Circuit” by taking an “ionstorm”, blasting it into the 4th dimension, arrange the pieces of dimension together, poke in a few resistors, wires, so on, and voila, you get “Ewe Jin”, a.k.a “Sort Circuit”

Leave a Reply

Your email address will not be published. Required fields are marked *