Types of sorts  
	- internal and external
	- stable
Assume:  Index and list elements are integers. (In practice, we sort lists. of records, not just lists of numbers.)

Sort3 B P 95
 IDEA:	 Compare the first element to each of the others
	 Compare the last two

Ex 	LIST =  62  	53  	14

Exchange 62 and 53		53 	62 	14
Exchange 53 and 14		14	62 	53
Exchange 62 and 53		14	53	62

DONE!

(********************************************************************)

procedure sort3 (var LIST: LIST_TYPE);

{PURPOSE: This algorithm uses SORT3 to sort a list of 3 elements.}

{INPUT PARAMETERS:	LIST - a list to be sorted		}

{OUTPUT PARAMETERS:	LIST - a sorted list			}


begin
	if LIST [1] > LIST [2] then  exchange  (LIST[1], LIST [2]);
	if LIST [1] > LIST [3] then  exchange  (LIST[1], LIST [3]);
	if LIST [2] > LIST [3] then  exchange  (LIST[2], LIST [3]);
end;	

(********************************************************************)

begin {main}
	read the  list;  
	SORT3 (LIST);
	print the list;  
end.

NOTE: 	- interchanges are written out (rather than placed into a procedure) to save time
		- an extra variable is needed for exchanges




SELECTIONSORT

IDEA: 	do the appropriate number of times
		exchange  the smallest element and the first element;
		exchange  the second smallest element and the second element;
			.
			.
			.

Ex 		LIST = 	17	15	11	13	18	12

Pass 1
Index of first 		1
Index of smallest  	3
Exchange 11, 17	11 * * 	15	17	13	18	12
Pass 1 complete

Pass 2
Index of first 		2
Index of smallest 	6
Exchange 12, 15	11	12 * * 	17	13	18	15
Pass 2 complete 

Pass 3
Index of first 		3
Index of smallest 	4
Exchange 13, 17	11	12   	13 * * 	17	18	15
Pass 3 complete

Pass 4
Index of first 		4
Index of smallest 	6
Exchange 17, 15	11	12   	13  	15 * *	18	17
Pass 4 complete

Pass 5
Index of first 	 	5
Index of smallest 	6
Exchange 17, 18	11	12   	13  	15 	17 * *	18
Pass 5 complete

DONE!

SELECTIONSORT is good for files with large records, because there are always exactly n - 1 interchanges. 

(********************************************************************)

procedure selectionsort (var LIST: LIST_TYPE; SIZE: integer);

{PURPOSE: This algorithm uses SELECTIONSORT to sort a list of elements.}

{INPUT PARAMETERS:	LIST 	- a list to be sorted		
				SIZE	- the size of the list		}

{OUTPUT PARAMETERS:	LIST - a sorted list			}

{DICTIONARY OF LOCAL VARIABLES:
	I	- index to the first element on the list
	MIN	- index to the smallest element found so far		
	J	- index to the list 					}

var	I, J, MIN: integer; 

begin
	for I := 1 to SIZE - 1 do begin			{Find the index of the smallest element}
		MIN := I;
		for J := I + 1 to SIZE do
			if LIST [J] < LIST [MIN] then MIN := J;
	interchange (LIST[I], LIST [MIN);		{Switch the first and the smallest element}	
end;	

(********************************************************************)

INSERTIONSORT 

IDEA:  for each element do
		move the element toward the front of the list until it is in its proper position

Ex 		LIST = 	17	15	11	13	18	12

Roughly			17
				15	17
				11	15	17
				11	13	15	17
				11	13	15	17	18
				11	12	12	15	17	18
In detail				

PASS 1
CURRENT INDEX 	 	2	
CURRENT ELEMENT  	15
Exchange 15 and 17		15	17 **	11	13	18	12
PASS 1 complete. 

PASS 2 
CURRENT INDEX  		3	
CURRENT ELEMENT 	11
Exchange  11 and 17		15	11	17	13	18	12
Exchange 11 and 15		11	15	17 **	13	18	12
Pass 2 complete 

PASS 3 
CURRENT INDEX 		4	
CURRENT ELEMENT 	13
Exchange 13 and 17		11	15	13	17	18	12
Exchange 13 and 15		11	13	15	17 **	18	12
PASS 3 complete

PASS 4
CURRENT INDEX 		 5	
CURRENT ELEMENT is 	18
No exchange			11	13	15	17 	18 **	12
PASS 4 complete 

PASS 5 
CURRENT INDEX 		6
CURRENT ELEMENT 	12
Exchange 12 and 18		11	13	15	17 	12 	18
Exchange 12 and 17		11	13	15	12 	17	18
Exchange 12 and 15		11	13	12	15 	17	18
Exchange 12 and 13		11	12	13	15 	17	18
PASS 5 complete 

DONE!

IMPLEMENTATION: Put MAXINT before the first element of the list to ensure that we do not
"run off" the front of the list

(********************************************************************)

procedure insertionsort (var LIST: LIST_TYPE; SIZE: integer);

{PURPOSE: This algorithm uses INSERTIONSORT to sort a list of elements.}

{INPUT PARAMETERS:	LIST 	- a list to be sorted		
				SIZE	- the size of the list		}

{OUTPUT PARAMETERS:	LIST - a sorted list			}

{DICTIONARY OF LOCAL VARIABLES:
	I	- index to the first element on the list
	J	- loop control variables				}

var	CURRENT_INDEX: integer;

begin
	LIST [0] := MAXINT;
	for CURRENT_INDEX := 2 to SIZE do
		move  LIST [CURRENT_INDEX] to its proper position  ;	
end;	

(********************************************************************)

The moving is done as follows:
	- save   LIST [CURRENT_INDEX] 
	- while LIST [CURRENT_INDEX]  is not in its correct position  do 
		- move the next element on the list to the right
		- compare  LIST [CURRENT_INDEX]  to the next element to the left

The code is:

	TEMP := LIST [CURRENT_INDEX];
	J := CURRENT_INDEX - 1;
	while TEMP < LIST [J] do begin
		LIST [J + 1] := LIST [J];
		J := J - 1
	end;

Ex (above)	LIST = 	11	13	15	17 	18 	12

PASS 5 
CURRENT INDEX 		6
CURRENT ELEMENT 	12
TEMP 				12

J	5
Compare 12, 18; copy 18		11	13	15	17 	18	18

J	4
Compare 12, 17; copy 17		11	13	15	17	17	18

J	3
Compare 12, 15; copy 15		11	13	15	15 	17	18

J	2
Compare 12, 13; copy 13		11	13	13	15 	17	18

J 	1
Compare 12, 11; copy 12		11	12	13	15	17	18
PASS 5 complete 

DONE!


BUBBLESORT 

IDEA:	for the appropriate number of times do
		if consecutive elements are out of order then 
			exchange the elements;

In the standard BUBBLESORT, we start at the front of the list. In this version, we start at the end. 

Ex 		LIST = 	17	15	11	13	18	12

PASS 1
Exchange 18, 12	17	15	11	13	12	18
Exchange 13, 12	17	15	11	12	13	18
No exchange 		17	15	11	12	13	18
Exchange 15, 11	17	11	15	12	12	18
Exchange 15, 11	11	17	15	12	12	18
PASS 1 complete 

After each pass, the smallest element is at the end. Therefore, BUBBLESORT acts like SELECTIONSORT, but is much more inefficient; BUBBLESORT performs 5 exchanges in this pass, while SELECTIONSORT performs only 1.

Performance characteristics

Proposition 1 SELECTIONSORT 
WORST CASE	C(N) = N(N-1)/2	AVERAGE CASE	C(N) = N(N-1)/2
			E(N) = N - 1					E(N) = N - 1

Proof WORST CASE
COMPARISONS. SELECTIONSORT performs N - 1 passes. In each pass, the number of comparisons is:

	PASS 1	N - 1
	PASS 2	N - 2
	PASS 3	N  3

	PASS N - 1	1

The total number of comparisons is C(N) = 1 + 2 + . . . + (N - 1) 	= (N - 1)N/2

EXCHANGES  There is one exchange in each pass, so E(N) = N - 1. 	

AVERAGE CASE 	Same! 				QED


Proposition 2 INSERTIONSORT 
		WORST CASE	C(N) is about N2/2
					E(N) is about N2/4

		AVERAGE CASE	C(N) is about N2/4
					E(N) is about N2/8

Proposition 3 BUBBLESORT uses about N2/2 comparisons and about N2/2 exchanges in both the average and worst cases. 

Proposition 4 INSERTIONSORT is "almost linear" for sorted files. 
Proof Inserting an element into a sorted file is linear. 


Files w/ Large Records 
	Indirect Operation
		Array of elements			- denoted A
		Array of Indexes for first file		- denoted P

The idea is to change the index of each element to what it would be when the list is sorted.

Ex
    LIST	1	7	5	3	8	2
    INDEX	1	2	3	4	5	6

    Any Sort
   
   LIST		1	7	5	3	8	2
   INDEX	1	5	4	3	6	2

This can be done modifying any sorting algorithm; in comparisons, replace LIST[I] by LIST [INDEX[I]], and in data movement replace LIST [I] by INDEX[I]. 

We can also physically move the records to the correct place if mecessary. 


(********************************************************************)
procedure insitu (var A: LIST_TYPE; N: integer; var B; INDEXES);

{PURPOSE: 	This algorithm rearranges a list of large records. }

{INPUT:	LIST - the list of records  to be rearranged
		SIZE - the size of the list 
		INDEX - the list of indexes to the list}

{OUTPUT:	LIST - the rearranged list }

{DICTIONARY OF LOCAL VARIABLES
		J - 	index to INDEX
		I - 	loop control variable
		K - 	index
		TEMP - temporary variable used for exchanges}

begin		
	for I :=1 to N do
		if INDEX [I]  <> I then begin 
			TEMP := LIST[I]; 
			K := I;
			repeat			
				J := K;
				LIST[J] := LIST [INDEX [J] ];
				K := INDEX[J];
				INDEX[J] := J;
			until K = I;
			LIST[J] := TEMP;
		end 
end;
(********************************************************************)

  	
SHELLSORT  p 108

Ex 	
List	7	19	24	13	31	8	82	18	44	63	5	29
Index	1	2	3	4	5	6	7	8	9	10	11	12

Pass 1
Let h=9. Then sort the sublists whose indexes are

Sublist		7	63
Index		1	10

Sublist		19	5
Index		2	11     switch

Sublist		24	29
Index		3	12


List	7	5	24	13	31	8	82	18	44	63	19	29
Index	1	2	3	4	5	6	7	8	9	10	11	12
Pass 1 complete 

Pass 2
Let h=3. Again, sort the following sublists.

Sublist		7	13	82	63
Index		1	4	7 	10
	
Sublist		5	31	18	19
Index		2	5	8	11
	
Sublist		24	8	44	29
Index		3	6	9	12

List	7	5	8	13	18	24	63	19	29	82	31	44
Index	1	2	3	4	5	6	7	8	9	10	11	12
Pass 2 complete 

Pass 3 
Let h=1. In this case, we simple perform INSERTIONSORT on the list. 
Pass 3 complete. 
There is no complete analysis for Shellsort. However, we do have results for some special cases.

Proposition Shellsort does no more than  N3/2 comparisons  for the sequence 
h = 1,	4, 13,	40, . . . (Each element differs from the previous by the next highest power of 3.)


DISTRIBUTION CONTING 

This method applies to lists where the numbers are integers in a given range, say 0 to M - 1 for some M. Here we count the number of records with each key value on the first pass through the list, and then move the elements to their correct position in the second pass.