// Note: this file is also available as sortDemos.java
// pacs, 3/27 and 3/28
// in-class code for hw14 and hw15
// warning: this code was developed in class and MAY HAVE ERRORS.
// you are responsible for the correct versions of this code,
// regardless of any small errors which may be in the code below.
class HW14
{
///////////////////////////////////////////////
/// swap
///////////////////////////////////////////////
// swap a[i] with a[j]
public static void swap(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
///////////////////////////////////////////////
/// quicksort
///////////////////////////////////////////////
// lo and hi are INDEXES, and we are going to sort
// a from a[lo] to a[hi]
public static void quicksort(int[] a, int lo, int hi)
{
// BASE CASE
if (lo >= hi)
// lo has equalled (or crossed) hi, so we have
// either a singleton or an empty array, either
// way, it is sorted
return;
// first, set the pivot to the first element
int pivot = a[lo];
// now, keep pivoting until the left and right indexes cross
int leftIndex = lo + 1;
int rightIndex = hi;
while (rightIndex > leftIndex)
{
// 1. if the element on the right is in the right place,
// move the rightIndex one to the left
if (a[rightIndex] > pivot)
rightIndex--;
// 2. else if the element on the left is in the right place,
// move the leftIndex one to the right
else if (a[leftIndex] <= pivot)
leftIndex++;
// 3. otherwise, both sides are wrong, so SWAP them
else
swap(a,leftIndex,rightIndex);
}
// at this point, leftIndex and rightIndex equal each
// other, and the pivot is stored in a[lo].
// We now want to swap the pivot (a[0]) with the last
// element on the left. This will either be the element
// where the two indexes met, or the one just to its left.
int newPivotIndex;
if (a[leftIndex] > pivot)
newPivotIndex = leftIndex - 1;
else
newPivotIndex = leftIndex;
// now just swap the pivot into its new location
swap(a,lo,newPivotIndex);
// now recursively sort the left and right sides, being
// sure not to sort the pivot again!
quicksort(a,lo,newPivotIndex-1);
quicksort(a,newPivotIndex+1,hi);
}
public static void quicksort(int[] a)
{
quicksort(a,0,a.length-1);
}
///////////////////////////////////////////////
/// mergesort
///////////////////////////////////////////////
// lo and hi are INDEXES, and we are going to sort
// a from a[lo] to a[hi]
public static void mergesort(int[] a, int lo, int hi, int[] copy)
{
int mid = (lo + hi)/2;
// step 0 -- BASE CASE
if (lo >= hi)
// lo has equalled (or crossed) hi, so we have
// either a singleton or an empty array, either
// way, it is sorted
return;
// step 1 -- sort the left half
mergesort(a,lo,mid,copy);
// step 2 -- sort the right half
mergesort(a,mid+1,hi,copy);
// step 3 -- merge the two sorted halves
int leftIndex, rightIndex, copyIndex;
leftIndex = lo;
rightIndex = mid+1;
for (copyIndex = lo; copyIndex <= hi; copyIndex++)
{
// if there are no more elements on the left, use
// the right side. Or, if there are elements on
// the right and the right is smaller, still use
// the right side.
if ((leftIndex > mid) ||
((rightIndex <= hi) && (a[rightIndex] < a[leftIndex])))
{
// use the right
copy[copyIndex] = a[rightIndex];
rightIndex++;
}
else
{
// use the left
copy[copyIndex] = a[leftIndex];
leftIndex++;
}
}
// step 4 -- put the copy back into a
for (copyIndex = lo; copyIndex <= hi; copyIndex++)
a[copyIndex] = copy[copyIndex];
}
public static void mergesort(int[] a)
{
int[] copy = new int[a.length];
mergesort(a,0,a.length-1,copy);
}
///////////////////////////////////////////////
/// insertionsort
///////////////////////////////////////////////
public static void insertionsort(int[] a)
{
for (int i = 0; i < a.length; i++)
for (int j = 0; j < i; j++)
if(a[i] < a[j])
swap(a,i,j);
}
///////////////////////////////////////////////
/// selectionsort
///////////////////////////////////////////////
public static void selectionsort(int[] a)
{
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++)
if (a[i] > a[j])
swap(a,i,j);
}
///////////////////////////////////////////////
/// bubblesort
///////////////////////////////////////////////
public static void bubblesort(int[]a)
{
boolean didSwap = true;
while (didSwap == true)
{
didSwap = false;
for (int i = 0; i < a.length - 1; i++)
{
if (a[i] > a[i + 1])
{
swap(a,i,i + 1);
didSwap = true;
}
}
}
}
///////////////////////////////////////////////
/// sortArray, randomArray, printArray
///////////////////////////////////////////////
public static void sortArray(int[] a, String sort)
{
if (sort.equals("bubble"))
bubblesort(a);
else if (sort.equals("insertion"))
insertionsort(a);
else if (sort.equals("selection"))
selectionsort(a);
else if (sort.equals("merge"))
mergesort(a);
else if (sort.equals("quick"))
quicksort(a);
else
System.out.println("**** UNKNOWN SORT: " + sort + " ****");
}
public static int[] makeRandomArray(int arraySize)
{
int[] a = new int[arraySize];
for (int i = 0; i < arraySize; i++)
a[i] = (int)(100000 * Math.random());
return a;
}
// prints in integer right-justified in an 6-character-wide field
public static void printInteger(int x)
{
// first, convert x to a String
String output = new Integer(x).toString();
// next, print out as many leading spaces as necessary
for (int i=output.length();i<6;i++)
System.out.print(" ");
// finally, print out the number
System.out.print(output);
}
// prints the array, 10 elements per line
public static void printArray(int[] a)
{
for (int i = 0; i<a.length; i++)
{
if (i % 11 == 10)
System.out.println();
printInteger(a[i]);
}
System.out.println();
}
///////////////////////////////////////////////
/// getCommand and main
///////////////////////////////////////////////
public static int getCommand(String[] sorts, int currentSort,
boolean doPrint)
{
int command, sort;
System.out.println("--------------------");
System.out.println("Now using: " + sorts[currentSort] + "sort");
System.out.println("Printing is " + (doPrint ? "on" : "off"));
System.out.println("Commands:");
System.out.println(" <0: exit");
for (sort=0;sort<sorts.length;sort++)
System.out.println(" " + sort + ": " + sorts[sort] + "sort");
System.out.println(" " + sorts.length + ": toggle printing");
System.out.println(" >" + sorts.length + ": set array size and sort");
System.out.print("Enter command: ");
command = readInt();
System.out.println("--------------------");
return command;
}
public static void main(String[] args)
{
int arraySize, currentSort = 0;
long time1, time2;
boolean doPrint = true;
String[] sorts = {"bubble","insertion","selection","merge","quick"};
while (true)
{
int command = getCommand(sorts,currentSort,doPrint);
if (command < 0)
// command = exit
break;
else if (command < sorts.length)
// command = new sort, command is the index into sorts array
currentSort = command;
else if (command == sorts.length)
// command = toggle printing
doPrint = !doPrint;
else
{
// command = create and sort array, command is array size
arraySize = command;
int[] array = makeRandomArray(arraySize);
if (doPrint)
{
System.out.println("before:");
printArray(array);
}
time1 = System.currentTimeMillis();
sortArray(array,sorts[currentSort]);
time2 = System.currentTimeMillis();
if (doPrint)
{
System.out.println("after:");
printArray(array);
}
System.out.println("Total sort time: "
+ (time2 - time1) + " milliseconds");
}
}
System.out.println("Goodbye!");
}
///////////////////////////////////////////////
/// readString, readInt, readDouble
///////////////////////////////////////////////
public static String readString()
{
String result="";
char c;
try
{
while(true)
{
c = (char)System.in.read();
if(!Character.isWhitespace(c))
break;
}
while(true)
{
result += c;
c = (char)System.in.read();
if(Character.isWhitespace(c))
break;
}
}
catch (java.io.IOException e)
{
System.out.println("Error while reading string.");
result += "_ERROR_";
}
return result;
}
public static int readInt()
{
return Integer.parseInt(readString());
}
public static double readDouble()
{
return Double.valueOf(readString()).doubleValue();
}
}