/*

    The Sorters class may be used to demonstrate the algorithms.

    It includes the definitions of selectionSort and quickSort

    methods, plus the declaration and initialization of sample arrays,

    and a main method that calls the sorting methods. The

    program also includes a swap method to accomplish the

    exchanges of array element values in the selectionSort and

    quickSort methods. Finally, there is a simple method for

    displaying the elements of an array.



    Record of revisions:

    Date                Programmer          Description of change

    ====                ==========          =====================

    11 February 2003    J. Rodger           adapt from web notes

    30 May 2003         J. Rodger           revised for Spring 101

*/

import hsa.*;

public class Sorters

{

    // exchanges elements i and j of the array, no error testing

    public static void swap (int i, int j, int [] sortArray)

    {

	int temp = sortArray [i];

	sortArray [i] = sortArray [j];

	sortArray [j] = temp;

    } // end method swap





    // method for sorting an array of int values

    // into increasing numerical order

    public static void selectionSort (int [] sortArray)

    {

	int i = 0, j = 0, minLocn = 0;



	//  repeatedly locate correct value for position i

	for (i = 0 ; i < sortArray.length - 1 ; i++)

	{

	    minLocn = i;

	    // check elements from i to end for smallest

	    for (j = i + 1 ; j < sortArray.length ; j++)

	    {

		if (sortArray [j] < sortArray [minLocn])

		{

		    // record index of smallest value

		    minLocn = j;

		} // end if

	    } // end for j

	    // swap smallest of remaining values into i<sup>th</sup> position

	    swap (minLocn, i, sortArray);

	} // end for i

    } // end method selectionSort





    // a recursive method implementing quicksort

    // parameters are the left (lower) and right (upper)

    // bounds of the part of the array to sort, plus the array itself

    public static void quickSort (int l, int r, int [] sortArray)

    {

	int i = l, j = r, partitionVal;

	// use middle value of current partition to split it

	partitionVal = sortArray [(l + r) / 2];

	do

	{

	    // move index markers towards middle

	    // so long as values conform to partition

	    while (sortArray [i] < partitionVal)

		i++;

	    while (sortArray [j] > partitionVal)

		j--;

	    // swap "out of partition" elements

	    if (i <= j)

	    {

		swap (i, j, sortArray);

		i++;

		j--;

	    } // end if

	}

	while (i <= j);

	// call quicksort with resulting partitions

	if (l < j)

	    quickSort (l, j, sortArray);

	if (i < r)

	    quickSort (i, r, sortArray);

    } // end quickSort method







    // prints the values in an array of integers, no error checks

    public static void printArray (int [] sortArray)

    {

	for (int i = 0 ; i < sortArray.length ; i++)

	{

	    Stdout.print (sortArray [i] + "  ");

	} // end for

	Stdout.println ();

    } // end method printArray





    public static void main (String [] args)

    {

	int [] testArray1 = {3, 9, 6, 1, 2};

	int [] testArray2 = {3, 9, 6, 1, 2};



	Stdout.println ("Demonstrate Selection Sort");

	printArray (testArray1);

	selectionSort (testArray1);

	printArray (testArray1);



	Stdout.println ("Demonstrate Quick Sort");

	printArray (testArray2);

	quickSort (0, 4, testArray2);

	printArray (testArray2);



    } // end method main

} // end Class Sorters