QUICKSORT 
This algorithm works by dividing the list into two parts and then sorting each part separately. One element is chosen, called the pivot. Elements smaller than the pivot are sent to the front of the list, and elements smaller than the pivot are sent to the back of the list. The pivot is then placed into its correct position. This is called partitioning the list. We can write the algorithm as follows.

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

procedure quicksort (var LIST: LIST_TYPE; LEFT, RIGHT: INDEX_TYPE);

{PURPOSE: This algorithm sorts a list using QUICKSORT.}

{INPUT: 	LIST - the list to be sorted
		LEFT, RIGHT - indexes to the first and last element, respectively, of the list}

{OUTPUT:	LIST - the sorted list}

{DICTIONARY OF LOCAL VARIABLES
		PIVOT_POS - the final position of the pivot element}

var	PIVOT_POS: INDEX_TYPE;

begin 
	if (RIGHT > LEFT) then begin
		PARTITION (LIST, LEFT, RIGHT, PIVOT_POS);
		QUICKSORT (LIST, LEFT, PIVOT_POS - 1);
		QUICKSORT (LIST, PIVOT_POS + 1, RIGHT);
	end;
end;

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

The difficulty comes in the partitioning of the list. We have two pointers, I and J, starting at the left and right sides of the list respectively. We advance the pointers and switch LIST[I] and LIST [J] when LIST [I] > PIVOT and LIST [J] < PIVOT. 

Ex 	

1	19	15	20	9	5	24	1	13	16	12	5



	I						J

Exchange these elements and advance the pointers.


1	1	15	20	9	5	24	19	13	16	12	5


		I			J

Exchange these elements and advance the pointers. 

1	1	5	20	9	15	24	19	13	16	12	5


		 J	I

Again, we exchange these elements. 

1	1	20	5	9	15	24	19	13	16	12	5

Note that this last exchange actually moves these elements into the wrong relative position. However, since now J <= I, we correct this last action and also put the PIVOT into its correct position.  Move LIST [I] to LIST [J], move PIVOT to LIST [I], and move the original LIST [J] to LIST [RIGHT]. 

1	1	5	5	9	15	24	19	13	16	12	20

The partition algorithm is implemeneted in the following procedure. 

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

procedure partition (var LIST: LIST_TYPE; LEFT, RIGHT, PIVOT_POS: INDEX_TYPE);

{PURPOSE: 	This procedure partitions the list.}

{INPUT:	LIST - the list to be partitioned
		LEFT, RIGHT - indexes to the first and last element, respectively, of the list}

{OUTPUT:	LIST - the partitioned list
		PIVOT_POS - the index of the pivot element}

{DICTIONARY OF LOCAL VARIABLES
		PIVOT - the pivot element
		I, J - indexes to the list
		TEMP - temporary variable used for interchanges}

var 	PIVOT, TEMP: ELEMENT_TYPE;
	I, J: INDEX_TYPE;
begin
	PIVOT := LIST [RIGHT];
	I := LEFT - 1;
	J := RIGHT;

	repeat
		repeat				{Find a large element near the beginning of the list}
			I := I + 1
		until LIST [I] >= PIVOT;
		repeat				{Find a small element near the end of the list}
			I :=J - 1
		until LIST [J] <= PIVOT;
		TEMP := LIST [I]; 		{Exchange these elements}
		LIST [I] := LIST [J]; 
		LIST [J] := TEMP;
	until J <= I;
	LIST [J] := LIST [I];			{Put the PIVOT into its correct position}
	LIST [I] := LIST [RIGHT]; 
	LIST [RIGHT] := TEMP;

	PIVOT_POS := I;			{Set PIVOT_POS}

end;

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

This algorithm can be made more efficient by placing the code for the partition into QUICKSORT instead of using a procedure call. 

Analysis 	

Proposition The number of comparisons which Quicksort performs is about 2 N ln  N.
Proof 
	
	CN = N-1 + 1/N        ·	(Ch-1 + CN-h)	N>=1   Co=1
			  1 <= h <= N

				=N-1 + 2/N ·  Ch-1	

Multiply by N:
				     N
	NCN      =    N(N-1) + 2 · Ch-1
				      1

Multiply the original equation by N-1:

				           N-1
	(N-1)CN-1    =(N-1)(N-2)   +· Ch-1
				            1

Subtract the bottom expression from the top.


	NCN -(N-1)CN-1      =    N(N-1) +(N-1)(N-2)  + 2CN-1


		NCN =    (N+1)CN-1  + 2N

		NCN      =     CN-1     +       2   
		---------        ------------   -----------
		N+1                   N	        N+1

			   = ........

			  	  N	          
			   =   2   · 1/k     
				  1           
     
This last expression is approximately the integral of 1/k, which is approximately ln N. 


Improvements
(1) Remove recursion by using stacks. We need only place onto the stack the left and right indexes of the current sublist. Don not push any sublist of size 1.
(2) Run quicksort until the sublist is "small" (have the students determine the value of "small" in a homework exercise) and then run insertionsort on the sublist. 

Median-of-Three partitioning 
Quicksort is slow for files which are "almost sorted". To avoid this case, take as the PIVOT elemenet the median of three elements of the list. 

Selection 
We can find the k-th smallest element in a list without sorting the list. For small k, run selectionsort k times. This algorithm requires time proportional to Nk, which is linear for small k. For larger k, run partition until PIVOT_POS = K. 

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

procedure select  (var LIST: LIST_TYPE;  LEFT, RIGHT, K: integer);					
{PURPOSE: 	This procedure finds the K-th smallest element of a list.}

{INPUT:	LIST - the list of elements
		LEFT, RIGHT - indexes to the list (we assume they are integer)
		K  	- the number of the element we want to find}

{OUTPUT:	LIST - the list with the K-th smallest element in the K-th position}

{DICTIONARY OF LOCAL VARIABLES
	PIVOT_POS - final index of the pivot after partitioning}

var	PIVOT_POS: :integer;

begin
   If   RIGHT > LEFT then begin
	    PARTITION (LEFT, RIGHT, PIVOT_POS);
	    if PIVOT_POS > (LEFT+ K- 1)	
		then SELECT (LEFT, PIVOT_POS - 1, K);
	    if PIVOT_POS < (LEFT +K -1) 
		then select (PIVOT_POS + 1, RIGHT , K -PIVOT_POS);
	end   {If-then}
end  

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


Non recursive	version							
	- remove tail recursion
	- include code for the non-recursive PARTITION i


In the following example we use the identifirer I rather than PIVOT_POS. 

Ex	Find the 5-th smallest element in 

17	19	13	11	18	16	12	14

In this case K = 5. The pivot is 14. 

Pass 1

	17	19	13	11	18	16	12	14	

	I						J	

Exchange these elements and advance the pointers.

	12	19	13	11	18	16	17	14

		I		J

Exchange these elements and advance the pointers.

	12	11	13	19	18	16	17	14

			J	I

Exchange these elements and put the pivot into the correct position. 

	12	11	13	14	18	16	17	19

Now PIVOT_POS = 4 and K = 5 so LEFT := I + 1 = 5.

Pass 1 complete 

Pass 2 

 We then consider the right sublist.

	18	16	17	19

After advancing the pointers we have 

	18	16	17	19

			J	I

After exchanging all elements we have the same list. Now I = 8 and K = 5 so RIGHT := I - 1 = 7.

Pass 2 complete 


Pass 3 

		18	16	17

		I	J

Exchange the elements and advance the pointers.

		16 	18	17

		J	I

Exchange and move the pivot into the correct position. 
Now I = 6 and K = 5 so RIGHT := I - 1 = 5.


Since RIGHT  >  LEFT  is false, we are done. The K-th largest element is LIST [K] = LIST [5].


Proposition 	QUICKSORT- based SELECT is linear.

Proof The number of comparisons is N + N/2 + . . . which is approximately 2N.