///////
//
// Student: Russell Lowke
//     T.F: Francis Crick
// Unit Seven, pencil-and-paper - question 1 [worth 2pts],  7/30/2002
//
//  Write out successive steps in the sorting process for all six algorithms in short.hpp
// (insertion, selection, bubble, zshell, heap, quick), applied to the following array.
//
//  { 29 48 13 96 35 67 23 }
//


//
// Insertion sort
//
Start:		{ 29 48 13 96 35 67 23 }

Remove the second element (i = 2) and place it in position [0],
the first element is considered already sorted.
[0] = 48,	{ 29  13 96 35 67 23 }


Compare element [0] with all elements in the sorted
potion of the array - in this case just the 29.
			{ 29 48  13 96 35 67 23 }


Remove the third element (i = 3) and place it in [0].
[0] = 13,	{ 29 48  96 35 67 23 }


Compare element [0] with the sorted portion, and insert.
			{ 13 29 48  96 35 67 23 }
			
repaet until sorted...
			{ 13 29 48 96  35 67 23 }
			{ 13 29 35 48 96  67 23 }
			{ 13 29 35 48 67 96  23 }
			{ 13 23 29 35 48 67 96  }
			done!
			
			
			
//
// Selection sort
//
Find the element to the right of [index] with the smallest value, and swap with [index],
[Index] starts at 1. After swapping, increment [index].

Start:		{ 29 48 13 96 35 67 23 }

			{ 13 48 29 96 35 67 23 }  1st swap
			{ 13 23 48 29 96 35 67 }
			{ 13 23 29 48 96 35 67 }
			{ 13 23 29 35 48 96 67 }
			{ 13 23 29 35 48 67 96 }  5th swap
			done!


//
// Bubble sort
//
Proceed from left to right, swapping adjacent elements if out of order,
keep iterating until all elements are in order.

Start:		{ 29 48 13 96 35 67 23 }
			{ 29 13 48 96 35 67 23 }
			{ 29 13 48 35 96 67 23 }
			{ 29 13 48 35 67 96 23 }
			{ 29 13 48 35 67 23 96 }
start again from first element.
			{ 13 29 48 35 67 23 96 }
			{ 13 29 35 48 67 23 96 }
			{ 13 29 35 48 23 67 96 }
start again from first element.
			{ 13 29 35 23 48 67 96 }
start again from first element.
			{ 13 29 23 35 48 67 96 }
start again from first element.
			{ 13 23 29 35 48 67 96 }
			done!


//
// Shell Sort
//
Start:		{ 29 48 13 96 35 67 23 }

Use insertion sort on sub arrays that contain elements
separated by an increment.

Increment = 3

			{ 29 48 13 96 35 67 23 }
			{ 29 35 13 96 48 67 23 }
			{ 23 35 13 29 48 67 96 }
			
Increment = 1

			{ 23 35 13 29 48 67 96 }
			{ 13 23 35 29 48 67 96 }
			{ 13 23 29 35 48 67 96 }
			done!


//
// heap Sort
//

Start:		{ 29 48 13 96 35 67 23 }

Construct a heap from the unsorted array
			{ 96 48 67 29 35 13 23 }
			
                                      96
                  48                                      67
        29                  35                  13                  23

Sift: 1    { 67 48 23 29 35 13 96 }
Sift: 2    { 48 35 23 29 13 67 96 }
Sift: 3    { 35 29 23 13 48 67 96 }
Sift: 4    { 29 13 23 35 48 67 96 }
Sift: 5    { 23 13 29 35 48 67 96 }
Sift: 6    { 13 23 29 35 48 67 96 }
        	done!


//
// quick Sort
//

Start:		{ 29 48 13 96 35 67 23 }
take a partition, in this case 35, and partition array
			{ 23 29 13 35 67 48 96 }
Now, recursivly partitoin each side using a new key, in this case 29 and 48
			{ 13 23 29 35 48 96 67 }
Keep, recursivly partitoining each side using a new key
			{ 13 23 29 35 48 67 96 }
			done!