Sorting Examples
/**
* Sorting examples below.
*
* Code copied from author's file (Walls and Mirrors)
*
* @author (your name)
* @version (a version number or a date)
*/
public class SortExamples
{
public static final int ITEMS = 100000;
public static void main(String [] args) {
IntegerArray a = new IntegerArray(ITEMS);
//printArray(a);
shellSort(a.getArray(), a.size());
//printArray(a);
//a = new IntegerArray(ITEMS);
//bubbleSort(a.getArray(), a.size());
//a = new IntegerArray(ITEMS);
//insertionSort(a.getArray(), a.size());
//printArray(a);
a = new IntegerArray(ITEMS);
quickSort(a.getArray());
//printArray(a);
}
public static void printArray(IntegerArray a) {
int [] tmp = a.getInts();
for (int i = 0; i < tmp.length; i++) {
System.out.println( "a[" + i + "] = " + tmp[i] );
}
}
public static void shellSort(Comparable[] theArray, int n) {
// ---------------------------------------------------
// Rearrange the data, taking every hth element. Element
// exchange is done with elements far apart.
// ---------------------------------------------------
int loc;
Comparable nextItem;
System.out.println("Shell sort starting, " + n + " items.");
long time = System.currentTimeMillis();
for (int h = n/2; h > 0; h = h/2) {
for (int unsorted = h; unsorted < n; ++unsorted) {
nextItem = theArray[unsorted];
loc = unsorted;
while ((loc >= h) &&
(theArray[loc-h].compareTo(nextItem) > 0)) {
theArray[loc] = theArray[loc-h];
loc = loc - h;
}
theArray[loc] = nextItem;
}
}
System.out.println("Shell sort done, time: " +
(System.currentTimeMillis() - time));
}
public static void bubbleSort(Comparable[] theArray, int n) {
// ---------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: theArray is an array of n items.
// Postcondition: theArray is sorted into ascending
// order.
// ---------------------------------------------------
boolean sorted = false; // false when swaps occur
System.out.println("Bubble sort starting, " + n + " items.");
long time = System.currentTimeMillis();
for (int pass = 1; (pass < n) && !sorted; ++pass) {
// Invariant: theArray[n+1-pass..n-1] is sorted
// and > theArray[0..n-pass]
sorted = true; // assume sorted
for (int index = 0; index < n-pass; ++index) {
// Invariant: theArray[0..index-1] <= theArray[index]
int nextIndex = index + 1;
if (theArray[index].compareTo(theArray[nextIndex]) > 0) {
// exchange items
Comparable temp = theArray[index];
theArray[index] = theArray[nextIndex];
theArray[nextIndex] = temp;
sorted = false; // signal exchange
}
}
// Assertion: theArray[0..n-pass-1] < theArray[n-pass]
}
System.out.println("Bubble sort done, time: " +
(System.currentTimeMillis() - time));
}
public static void insertionSort(Comparable[] theArray, int n) {
// ---------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: theArray is an array of n items.
// Postcondition: theArray is sorted into ascending
// order.
// ---------------------------------------------------
// unsorted = first index of the unsorted region,
// loc = index of insertion in the sorted region,
// nextItem = next item in the unsorted region
// initially, sorted region is theArray[0],
// unsorted region is theArray[1..n-1];
System.out.println("Insertion sort starting, " + n + " items.");
long time = System.currentTimeMillis();
for (int unsorted = 1; unsorted < n; ++unsorted) {
// Invariant: theArray[0..unsorted-1] is sorted
// find the right position (loc) in
// theArray[0..unsorted] for theArray[unsorted],
// which is the first item in the unsorted
// region; shift, if necessary, to make room
Comparable nextItem = theArray[unsorted];
int loc = unsorted;
while ((loc > 0) && (theArray[loc-1].compareTo(nextItem) > 0)) {
// shift theArray[loc-1] to the right
//theArray[loc--] = theArray[loc-1]; ERROR!!
theArray[loc] = theArray[loc-1];
loc--;
}
// insert nextItem into sorted region
theArray[loc] = nextItem;
}
System.out.println("Insertion sort done, time: " +
(System.currentTimeMillis() - time));
}
//==============================================================================
public static void quickSort(Comparable[] theArray) {
System.out.println("Quick sort starting, " + theArray.length + " items.");
long time = System.currentTimeMillis();
quickSort(theArray, 0, theArray.length - 1);
System.out.println("Quick sort done, time: " +
(System.currentTimeMillis() - time));
}
public static void quickSort(Comparable[] theArray,
int first, int last) {
// ---------------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: theArray[first..last] is an array.
// Postcondition: theArray[first..last] is sorted.
// Calls: partition.
// ---------------------------------------------------------
int pivotIndex;
if (first < last) {
// create the partition: S1, Pivot, S2
pivotIndex = partition(theArray, first, last);
// sort regions S1 and S2
quickSort(theArray, first, pivotIndex-1);
quickSort(theArray, pivotIndex+1, last);
}
}
private static void choosePivot(Comparable[] theArray,
int first, int last) {
// ---------------------------------------------------------
// Chooses a pivot for quicksort's partition algorithm and
// swaps it with the first item in an array.
// Precondition: theArray[first..last] is an array;
// first <= last.
// Postcondition: theArray[first] is the pivot.
// ---------------------------------------------------------
// Implementation left as an exercise.
} // end choosePivot
private static int partition(Comparable[] theArray,
int first, int last) {
// ---------------------------------------------------------
// Partitions an array for quicksort.
// Precondition: theArray[first..last] is an array;
// first <= last.
// Postcondition: Returns the index of the pivot element of
// theArray[first..last]. Upon completion of the method,
// this will be the index value lastS1 such that
// S1 = theArray[first..lastS1-1] < pivot
// theArray[lastS1] == pivot
// S2 = theArray[lastS1+1..last] >= pivot
// Calls: choosePivot.
// ---------------------------------------------------------
// tempItem is used to swap elements in the array
Comparable tempItem;
// place pivot in theArray[first]
choosePivot(theArray, first, last);
Comparable pivot = theArray[first]; // reference pivot
// initially, everything but pivot is in unknown
int lastS1 = first; // index of last item in S1
// move one item at a time until unknown region is empty
for (int firstUnknown = first + 1; firstUnknown <= last; ++firstUnknown) {
// Invariant: theArray[first+1..lastS1] < pivot
// theArray[lastS1+1..firstUnknown-1] >= pivot
// move item from unknown to proper region
if (theArray[firstUnknown].compareTo(pivot) < 0) {
// item from unknown belongs in S1
++lastS1;
tempItem = theArray[firstUnknown];
theArray[firstUnknown] = theArray[lastS1];
theArray[lastS1] = tempItem;
}
// else item from unknown belongs in S2
}
// place pivot in proper position and mark its location
tempItem = theArray[first];
theArray[first] = theArray[lastS1];
theArray[lastS1] = tempItem;
return lastS1;
}
}
/**
* Simple IntegerArray
*
* @author (your name)
* @version (a version number or a date)
*/
import java.util.Random;
public class IntegerArray
{
Integer [] nums;
public static final int D_SIZE = 20;
public static final int INT_MAX = 1000;
public IntegerArray() {
this(D_SIZE);
}
public IntegerArray(int size) {
if (size < 1)
size = D_SIZE;
makeArray(size);
}
private void makeArray(int size) {
nums = new Integer[size];
Random rnd = new Random();
for (int i = 0; i < size; i++) {
nums[i] = new Integer(rnd.nextInt(INT_MAX) + 1);
}
}
public int [] getInts() {
int [] tmp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
tmp[i] = nums[i].intValue();
}
return tmp;
}
public Integer [] getArray() {
// Integers are immutable, this is safe
return nums;
}
public int size() {
return nums.length;
}
}