// File: Quicksort.java
// A Java application to illustrate the use of a quicksort. Part of this work
// is left as an exercise for students using "Data Structures and Other
// Objects with Java" by Michael Main.
/******************************************************************************
* The Quicksort
Java application illustrates a quicksort.
* Part of the implementation (the partition
method) is left
* as a student exercise.
*
* Note:
* This file contains only blank implementations ("stubs")
* because this is a Programming Project for my students.
*
*
Java Source Code for this class (without
* partition
:
*
* http://www.cs.colorado.edu/~main/applications/Quicksort.java
*
*
* @version Feb 10, 2016
******************************************************************************/
public class Quicksort
{
/**
* The main method illustrates the use of a quicksort to sort a
* small array.
* @param args
* not used in this implementations
**/
public static void main(String[ ] args)
{
final String BLANKS = " "; // A String of two blanks
int i; // Array index
int[ ] data = { 1000, 80, 10, 50, 70, 60, 90, 20, 30, 40, 0, -1000 };
// Print the array before sorting:
System.out.println("Here is the entire original array:");
for (i = 0; i < data.length; i++)
System.out.print(data[i] + BLANKS);
System.out.println( );
// Sort the numbers, and print the result with two blanks after each number.
quicksort(data, 1, data.length-2);
System.out.println("I have sorted all but the first and last numbers.");
System.out.println("The numbers are now:");
for (i = 0; i < data.length; i++)
System.out.print(data[i] + BLANKS);
System.out.println( );
}
/**
* This method cannot be used until the student implements
* partition
.
* Sort an array of integers from smallest to largest, using a quicksort
* algorithm.
* @param data
* the array to be sorted
* @param first
* the start index for the portion of the array that will be sorted
* @param n
* the number of elements to sort
* Precondition:
* data[first]
through data[first+n-1]
are valid
* parts of the array.
* Postcondition:
* If n
is zero or negative then no work is done. Otherwise,
* the elements of data
have been rearranged so that
* data[first] <= data[first+1] <= ... <= data[first+n-1]
.
* @exception ArrayIndexOutOfBoundsException
* Indicates that first+n-1
is an index beyond the end of the
* array.
* */
public static void quicksort(int[ ] data, int first, int n)
{
int pivotIndex; // Array index for the pivot element
int n1; // Number of elements before the pivot element
int n2; // Number of elements after the pivot element
if (n > 1)
{
// Partition the array, and set the pivot index.
pivotIndex = partition(data, first, n);
// Compute the sizes of the two pieces.
n1 = pivotIndex - first;
n2 = n - n1 - 1;
// Recursive calls will now sort the two pieces.
quicksort(data, first, n1);
quicksort(data, pivotIndex + 1, n2);
}
}
private static int partition(int[ ] data, int first, int n)
// Precondition: n > 1, and data has at least n elements starting at
// data[first].
// Postcondition: The method has selected some "pivot value" that occurs
// in data[first]. . .data[first+n-1]. The elements of data have then been
// rearranged and the method returns a pivot index so that
// -- data[pivot index] is equal to the pivot;
// -- each element before data[pivot index] is <= the pivot;
// -- each element after data[pivot index] is > the pivot.
{
System.err.println("The student needs to implement the partition method");
System.err.println("before the quicksort can be used.");
System.exit(0);
return 0;
}
}