///////
//
// Student: Russell Lowke
//     T.F: Francis Crick
// Unit Seven, pencil-and-paper - question 3 [worth 2pts],  7/30/2002
//
//
// Both quicksort and heapsort are unstable lagorithms.  For each algorithm,
// construct an example of an input array containing two elements with
// equal keys whose order is reversed during sorting.


In the case of QUICKSORT, with the following number group:

data = { 15A,  15B,  8,  12,  1,  2  }

with quicksort partitioning around 8.

after the first pass, the positions of 15B and 15A will be
perminately interchanged, proving quicksort to be unstable.

data = { 2, 1,  8,  15B, 15A }


____

In the case of HEAPSORT, with the following number group:


data = { 50 40 30 15A 15B 25 7 }

                                      50
                  40                                      30
        15A                 15B                  25                  7
        
        
 when swappig out the 50 and sifting in the 7...
 
 
                                       7
                  40                                      30
        15A                 15B                  25         
        
        
 after two sifts the 7 will have disrupted the 15s proving Heapsort to be unstable.
 
 
 1st sift                             40
                  7                                        30
        15A                 15B                  25  
        
        
        
        
 2nd sift                            40
                  15A                                        30
        7                 15B                  25  
        
        
 Heapsort sifting is an unstable sort.