package net.datastructures;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Comparator;
import java.util.Random;
import java.util.Arrays;
/**
* Class containing various sorting algorithms.
*
* @author Michael Goodrich, Roberto Tamassia, Eric Zamore
*/
public class Sort {
/**
* Sort the elements of list L in nondecreasing order according
* to comparator c, using the merge-sort algorithm.
**/
public static void mergeSort (List L, Comparator c) {
int n = L.size();
if (n < 2)
return; // the list L is already sorted in this case
// divide
List L1 = new NodeList(); // first list used in recursion
List L2 = new NodeList(); // second list used in recursion
int i = 0;
while (i < n/2) {
L1.insertLast(L.remove(L.first())); // move the first n/2 elements to L1
i++;
}
while (!L.isEmpty())
L2.insertLast(L.remove(L.first())); // move the rest to L2
// recurse
mergeSort(L1,c);
mergeSort(L2,c);
//conquer
merge(L1,L2,c,L);
}
/**
* Merge two sorted lists, L1 and L2, into a sorted list L.
**/
public static void merge(List L1, List L2, Comparator c, List L) {
while (!L1.isEmpty() && !L2.isEmpty())
if (c.compare(L1.first().element(), L2.first().element()) <= 0)
L.insertLast(L1.remove(L1.first()));
else
L.insertLast(L2.remove(L2.first()));
while(!L1.isEmpty()) // move the remaining elements of L1
L.insertLast(L1.remove(L1.first()));
while(!L2.isEmpty()) // move the remaining elements of L2
L.insertLast(L2.remove(L2.first()));
}
/**
* Sort an array of objects with a comparator using nonrecursive merge sort.
*/
public static void mergeSort(Object[] orig, Comparator c) { // nonrecursive
Object[] in = new Object[orig.length]; // make a new temporary array
//System.arraycopy(orig,0,in,0,in.length); // copy the input
arraycopy(orig,0,in,0,in.length); // pet
Object[] out = new Object[in.length]; // output array
Object[] temp; // temp array reference used for swapping
int n = in.length;
for (int i=1; i < n; i*=2) { // each iteration sorts all length-2*i runs
for (int j=0; j < n; j+=2*i) // each iteration merges two length-i pairs
merge(in,out,c,j,i); // merge from in to out two length-i runs at j
temp = in; in = out; out = temp; // swap arrays for next iteration
}
// the "in" array contains the sorted array, so re-copy it
//System.arraycopy(in,0,orig,0,in.length);
arraycopy(in,0,orig,0,in.length); //pet
}
protected static void merge(Object[] in, Object[] out, Comparator c, int start,
int inc) { // merge in[start..start+inc-1] and in[start+inc..start+2*inc-1]
int x = start; // index into run #1
//int end1 = Math.min(start+inc, in.length); // boundary for run #1
//int end2 = Math.min(start+2*inc, in.length); // boundary for run #2
int end1 = min(start+inc, in.length); // pet
int end2 = min(start+2*inc, in.length); // pet
int y = start+inc; // index into run #2 (could be beyond array boundary)
int z = start; // index into the out array
while ((x < end1) && (y < end2))
if (c.compare(in[x],in[y]) <= 0) out[z++] = in[x++];
else out[z++] = in[y++];
if (x < end1) // first run didn't finish
//System.arraycopy(in, x, out, z, end1 - x);
arraycopy(in, x, out, z, end1 - x); // pet
else if (y < end2) // second run didn't finish
//System.arraycopy(in, y, out, z, end2 - y);
arraycopy(in, y, out, z, end2 - y); // pet
}
/**
* Sort the elements of list L in nondecreasing order according to
* comparator c, using a list-based implementation of the quicksort
* algorithm.
**/
public static void quickSort(List L, Comparator c) {
if (L.size() <= 1)
return;
Object pivot = L.remove(L.last());
List lesser = new NodeList();
List equal = new NodeList();
List greater = new NodeList();
Object cur;
while (!L.isEmpty()) {
cur = L.remove(L.first());
if (c.compare(cur,pivot) < 0)
lesser.insertFirst(cur);
else if(c.compare(cur,pivot) == 0)
equal.insertFirst(cur);
else
greater.insertFirst(cur);
}
quickSort(lesser,c);
quickSort(greater,c);
while(!lesser.isEmpty())
L.insertLast(lesser.remove(lesser.first()));
while(!equal.isEmpty())
L.insertLast(equal.remove(equal.first()));
L.insertLast(pivot);
while(!greater.isEmpty())
L.insertLast(greater.remove(greater.first()));
}
/**
* Sort the elements of array S in nondecreasing order according
* to comparator c, using the quick-sort algorithm. Most of the work
* is done by the auxiliary recursive method quickSortStep.
**/
public static void quickSort (Object[] S, Comparator c) {
if (S.length < 2) return; // the array is already sorted in this case
quickSortStep(S, c, 0, S.length-1); // recursive sort method
}
/**
* Sort in nondecreasing order the elements of sequence S between
* ranks leftBound and rightBound, using a recursive, in-place,
* implementation of the quick-sort algorithm.
**/
private static void quickSortStep (Object[] S, Comparator c,
int leftBound, int rightBound ) {
if (leftBound >= rightBound) return; // the indices have crossed
Object temp; // temp object used for swapping
Object pivot = S[rightBound];
int leftIndex = leftBound; // will scan rightward
int rightIndex = rightBound-1; // will scan leftward
while (leftIndex <= rightIndex) { // scan right until larger than the pivot
while ( (leftIndex <= rightIndex) && (c.compare(S[leftIndex], pivot)<=0) )
leftIndex++;
// scan leftward to find an element smaller than the pivot
while ( (rightIndex >= leftIndex) && (c.compare(S[rightIndex], pivot)>=0))
rightIndex--;
if (leftIndex < rightIndex) { // both elements were found
temp = S[rightIndex];
S[rightIndex] = S[leftIndex]; // swap these elements
S[leftIndex] = temp;
}
} // the loop continues until the indices cross
temp = S[rightBound]; // swap pivot with the element at leftIndex
S[rightBound] = S[leftIndex];
S[leftIndex] = temp; // the pivot is now at leftIndex, so recurse
quickSortStep(S, c, leftBound, leftIndex-1);
quickSortStep(S, c, leftIndex+1, rightBound);
}
public static void main (String[] argv) throws IOException {
out("Start your engines...");
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Random r = new Random();
Comparator c = new DefaultComparator();
out("Enter number of elements:");
String num = in.readLine();
int n = (new Integer(num)).intValue();
String cont;
Object[] A = new Integer[n];
Object[] B = new Integer[n];
float msin=0f,qsin=0f,msout=0f,qsout=0f;
long t;
do {
List C = new NodeList();
List D = new NodeList();
for (int i = 0; i < n; i++) {
int x = r.nextInt() % 100;
A[i] = new Integer(x);
B[i] = new Integer(x);
C.insertLast(new Integer(x));
D.insertLast(new Integer(x));
}
out("Array-Based Sorting");
out("Before: " + Arrays.asList(A));
//array-based mergesort
t = System.currentTimeMillis();
mergeSort(A, c);
msin = (System.currentTimeMillis()-t)/1000f;
out("MSort: " + Arrays.asList(A));
String correct = Arrays.asList(A).toString();
//array-based quicksort
t = System.currentTimeMillis();
quickSort(B, c);
qsin = (System.currentTimeMillis()-t)/1000f;
out("QSort: " + Arrays.asList(B));
if(!correct.equals(Arrays.asList(B).toString())) {
System.out.println("sorts produced different results!");
System.exit(1);
}
out("List-Based Sorting");
//list-based mergesort
t = System.currentTimeMillis();
mergeSort(C, c);
out("MSort: " + C);
msout = (System.currentTimeMillis()-t)/1000f;
if(!correct.equals(C.toString())) {
System.out.println("sorts produced different results!");
System.exit(1);
}
//list-based quicksort
t = System.currentTimeMillis();
quickSort(D, c);
out("QSort: " + D);
qsout = (System.currentTimeMillis()-t)/1000f;
if(!correct.equals(D.toString())) {
System.out.println("sorts produced different results!");
System.exit(1);
}
out("Times (in seconds)");
out("Array-Based");
out("MSort: "+msin);
out("QSort: "+qsin);
out("List-Based");
out("MSort: "+msout);
out("QSort: "+qsout);
out("Type 'e' to end ...");
cont = in.readLine();
} while (cont.equals(""));
}
private static void out (String s) {
System.out.println(s);
}
private static int min(int x,int y){
if (x <= y) return x;
else return y;
}
private static void arraycopy(Object[] src,int srcPos,Object[] dest,int destPos,int length){
for (int i = 0; i < length; i++)
dest[destPos+i] = src[srcPos+i];
}
}
|