//import trees.*;
//import queues.*;
public class SortRoutines
{
// Finds the largest item in an array.
// Precondition: theArray is an array of size items;
// size >= 1.
// Postcondition: Returns the index of the largest
// item in the array.
private static int indexOfLargest(Comparable[] theArray, int size)
{
int indexSoFar = 0; // index of largest item found so far
// Invariant: theArray[indexSoFar]>=theArray[0..currIndex-1]
for (int currIndex = 1; currIndex < size; ++currIndex)
{
if (theArray[currIndex].compareTo(theArray[indexSoFar])>0)
{
indexSoFar = currIndex;
} // end if
} // end for
return indexSoFar; // index of largest item
} // end indexOfLargest
// Sorts the items in an array into ascending order.
// Precondition: theArray is an array of n items.
// Postcondition: theArray is sorted into
// ascending order.
// Calls: indexOfLargest.
public static void selectionSort(Comparable[] theArray, int n)
{
// last = index of the last item in the subarray of
// items yet to be sorted
// largest = index of the largest item found
Comparable temp;
for (int last = n-1; last >= 1; last--) //all but
{
// Invariant: theArray[last+1..n-1] is sorted
// and > theArray[0..last]
// select largest item in theArray[0..last]
int largest = indexOfLargest(theArray, last+1);
// swap largest item theArray[largest] with
// theArray[last]
temp = theArray[largest];
theArray[largest] = theArray[last];
theArray[last] = temp;
} // end for
} // end selectionSort
// Sorts the items in an array into ascending order.
// Precondition: theArray is an array of n items.
// Postcondition: theArray is sorted into ascending
// order.
public static void insertionSort(Comparable[] theArray, int n)
{
// 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];
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];
loc--;
} // end while
// insert nextItem into sorted region
theArray[loc] = nextItem;
} // end for
} // end insertionSort
// Sorts the items in an array into ascending order.
// Precondition: theArray is an array of n items.
// Postcondition: theArray is sorted into ascending
// order.
public static void bubbleSort(Comparable[] theArray, int n)
{
boolean sorted = false; // false when swaps occur
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
} // end if
} // end for
// Assertion: theArray[0..n-pass-1] < theArray[n-pass]
} // end for
} // end bubbleSort
// Merges two sorted array segments theArray[first..mid] and
// theArray[mid+1..last] into one sorted array.
// Precondition: first <= mid <= last. The subarrays
// theArray[first..mid] and theArray[mid+1..last] are
// each sorted in increasing order.
// Postcondition: theArray[first..last] is sorted.
// Implementation note: This method merges the two
// subarrays into a temporary array and copies the result
// into the original array anArray.
private static void merge(Comparable[] theArray, int first, int mid, int last)
{
int maxSize = theArray.length;
// temporary array
Comparable[] tempArray = new Comparable[maxSize];
// initialize the local indexes to indicate the subarrays
int first1 = first; // beginning of first subarray
int last1 = mid; // end of first subarray
int first2 = mid + 1; // beginning of second subarray
int last2 = last; // end of second subarray
// while both subarrays are not empty, copy the
// smaller item into the temporary array
int index = first1; // next available location in
// tempArray
while ((first1 <= last1) && (first2 <= last2))
{
// Invariant: tempArray[first1..index-1] is in order
if (theArray[first1].compareTo(theArray[first2])<=0) //careful here for stable sorting
{
tempArray[index] = theArray[first1];
first1++;
}
else
{
tempArray[index] = theArray[first2];
first2++;
} // end if
index++;
} // end while
// finish off the nonempty subarray
// finish off the first subarray, if necessary
while (first1 <= last1)
{
// Invariant: tempArray[first1..index-1] is in order
tempArray[index] = theArray[first1];
first1++;
index++;
} // end while
// finish off the second subarray, if necessary
while (first2 <= last2)
{
// Invariant: tempArray[first1..index-1] is in order
tempArray[index] = theArray[first2];
first2++;
index++;
} // end while
// copy the result back into the original array
for (index = first; index <= last; ++index)
{
theArray[index] = tempArray[index];
} // end for
} // end merge
// Sorts the items in an array into ascending order.
// Precondition: theArray[first..last] is an array.
// Postcondition: theArray[first..last] is sorted in
// ascending order.
// Calls: merge.
public static void mergeSort(Comparable[] theArray, int first, int last)
{
if (first < last)
{
// sort each half
int mid = (first + last)/2; // index of midpoint
// sort left half theArray[first..mid]
mergeSort(theArray, first, mid);
// sort right half theArray[mid+1..last]
mergeSort(theArray, mid+1, last);
// merge the two halves
merge(theArray, first, mid, last);
} // end if
} // end mergesort
// Sorts the items in an array into ascending order.
// Precondition: theArray[first..last] is an array.
// Postcondition: theArray[first..last] is sorted.
// Calls: partition.
public static void quickSort(Comparable[] theArray, int first, int last)
{
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);
} // end if
} // end quickSort
// 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.
private static int partition(Comparable[] theArray, int first, int last)
{
// 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;
} // end if
// else item from unknown belongs in S2
} // end for
// place pivot in proper position and mark its location
tempItem = theArray[first];
theArray[first] = theArray[lastS1];
theArray[lastS1] = tempItem;
return lastS1;
} // end partition
// 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.
private static void choosePivot(Comparable[] theArray, int first, int last)
{
// Implementation left as an exercise.
} // end choosePivot
public static void shellSort(Comparable[] theArray, int n)
{
int loc;
Comparable nextItem;
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;
} // end while
theArray[loc] = nextItem;
} // end for unsorted
} // end for h
} // end shellsort
/**
* Sorts an array of Radixable elements radixably.
* Preconditions: An array of Radixable objects, an integer of the number of keys to sort by, and an integer of the number of elements to sort.
* Postconditions: Returns a new array of the sorted elements.
* @author Andrew Coleman
* @hidden All your base are belong to us.
*/
public static void radixSort(Radixable[] array, int index, int n) {
/* the maximum size of the bin array */
/* 26 letters, 10 digits, 1 extraneous character */
final int MAX_SIZE = 26 + 10 + 1;
/* our array for the sorting bins */
QueueInterface[] bins = new QueueInterface[MAX_SIZE];
/* the array to return */
//Radixable[] result = new Radixable[n];
/* an array to keep the size of each bin at the end of each iteration */
int[] binsize = new int[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++) {binsize[i] = 0;bins[i] = new QueueReferenceBased();}
/* Strings are indexed with an offset of +1 */
//index--;
/* these next two hunks of loopage are basically the same, but this way is a big time saver
instead of dumping the original array into a queue/array, i directly sort it into the bins
here and the elements are not taken out of the bins until i return the result array.
I have tried using one big loop and flags, but i get null for every item when i get done sorting.
Besides, it saves on having to do all that extra logic checks a few hundred thousand times */
for (int iter = 0; iter < n; iter++) {
/* this is the only line that differs between these two loops, here it comes from the array */
Radixable data = array[iter];
/* get an ascii value of the character */
int bin = (int) data.getRadixChar(index);
/* capital letters converted to lowercase */
if (bin >= 65 && bin <= 90)
bin += 32;
/* lowercase letters */
if (bin >= 97 && bin <= 122)
bin -= 86;
/* numbers */
else if (bin >=48 && bin <= 57)
bin -= 47;
/* non alphanumeric characters */
else
bin = 0;
bins[bin].enqueue(data);
}
/* already sorted the first character */
index--;
/* loop through remaining search keys */
for (int loop = index; loop >= 0; loop--) {
/* save the size of each bin */
for (int i = 0; i < MAX_SIZE; i++) {binsize[i] = bins[i].size();}
/* loop through each bin */
for (int iter = 0; iter < MAX_SIZE; iter++) {
/* loop through the number of items saved in binsize
now you don't have to dump the elements into another queue/array */
for (int eachbinitem = 0; eachbinitem < binsize[iter]; eachbinitem++) {
/* get data from the bins rather than the array */
Radixable data = (Radixable) bins[iter].dequeue();
int bin = (int) data.getRadixChar(loop);
if (bin >= 65 && bin <= 90)
bin += 32;
if (bin >= 97 && bin <= 122)
bin -= 86;
else if (bin >=48 && bin <= 57)
bin -= 47;
else
bin = 0;
bins[bin].enqueue(data);
}
}
}
/* keeps up with the total number of elements placed in the array (always < n) */
//int count = 0;
/* loop through each bin */
//for (int i = 0; i < MAX_SIZE; i++)
/* keep dumping the items inside until it's all gone */
// while (!bins[i].isEmpty()) {
// result[count] = (Radixable) bins[i].dequeue();
// count++;
// }
/* bye bye */
//return result;
/* this is sorting 200,000 strings (made by a random word generator in a Tolkien wordset) in
about 1282 milliseconds by my primitive timing methods and by comparison i made a radixsort
earlier that dumps everything into arrays was coming in at > 1600 milliseconds.
*/
}
}