Schreibe gerade an einem Programm, dass die verschiedenen Sortierverfahren vergleicht. Nun möchte ich aber auch die benötigte Zeit ausgeben. Habe aber dazu noch keinen Plan.
Code:
package Übung5;
import InOut.*;
public class TestSortingIncQuick {
private static Count selection;
public static void main (String[] args) {
int num; // length of array
char[]original; // for same sorting-conditions
char choice;
printHeader();
do {
mqu = 0;
cqu = 0;
num = readSize();
original = initializeArray(num);
computeResult(original);
do{ //start do while 2
Out.println();
Out.print(" Weitere Berechnung(j/n)?");
choice = In.readChar();
} while(!In.done()||(choice !='j')&&(choice !='n'));// end do while2
} while (choice == 'j');
}
// reads desired length of array
static int readSize() {
int num; // length of array
do {
Out.println();
Out.print(" Anzahl der Elemente eingeben: ( >1! ) ");
num = In.readInt();
Out.println();
} while (num<2);
return num;
}
// declares, creates and initializes the array
static char[] initializeArray(int num) {
char[] original = new char[num]; // creates array with desired length
for (int i = 0; i < original.length; i++) { // every field of array
// array gets random values of type char
original[i] = (char)(Math.random() * 26 + 'a');
} // i==original.length
return original;
}
// computes and prints result
static void computeResult(char[] original) {
Count shell;
char[] copy = (char[]) original.clone();
copy = (char[]) original.clone();
selection = selectionSort(copy);
copy = (char[]) original.clone();
shell = shellSort(copy);
copy = (char[]) original.clone();
quickSort(copy, 0, copy.length-1);
// prints all results
printResult(selection, shell);
}
static Count selectionSort(char[] a) {
Count sel = new Count();
int m=0; // number of moves
int c=0; // number of comparisons
char temp; // temporary
int min;
for (int i=0; i<a.length-1; i++) {
min = i;
for (int j=i+1; j<a.length; j++) {
c++;
if (a[j]<a[min]) {
min = j;
} // else a[j] >= a[min]
} // j >= a.length
temp = a[min]; // swap min and i
a[min] = a[i];
a[i] = temp;
m = m+3; // last three moves
}
sel.move = m;
sel.comp = c;
return sel;
}
// sorts array and returns count-results
static Count shellSort(char[] a) {
Count shell = new Count();
int m=0; // number of moves
int c=0; // number of comparisons
int outIndex, inIndex;
char temp; // temporary
int h=1; // jumping distance
while (h<=a.length/3) {
h = h*3+1;
} // h > a.length/3
while (h>0) {
for (outIndex = h; outIndex<a.length; outIndex++) {
temp = a[outIndex]; // move:
m++;
inIndex = outIndex;
c++; // first comparison in while-loop:
while ((inIndex>h-1) && (a[inIndex-h]>=temp)) {
a[inIndex] = a[inIndex-h];
m++;
inIndex = inIndex-h;
c++; // comparison in next while-loop
} // inIndex <= h-1 && a[inIndex-h] < temp
if(inIndex<=h-1) { // no comparison cause of first condition
c--;
}
a[inIndex] = temp; // move:
m++;
} // outIndex >= a.length
h=(h-1)/3;
} // h<=0
shell.move = m;
shell.comp = c;
return shell;
}
static int mqu; // number of moves
static int cqu; // number of comparisons
// sorts array the quickest way
static void quickSort(char[] array, int leftBound, int rightBound) {
int size = rightBound-leftBound+1;
if (size > 10) {
char median = medianOf3(array, leftBound, rightBound);
int pivotIndex = partitionIt(array, leftBound, rightBound, median);
quickSort(array, leftBound, pivotIndex- 1);
quickSort(array, pivotIndex+ 1, rightBound);
}
}
static int partitionIt(char[] array, int leftBound, int rightBound, char pivot) {
int leftIndex = leftBound + 1;
int rightIndex = rightBound - 2;
while (true) {
cqu++; // at least one comparison in while-condition
while (array[leftIndex] < pivot) {
leftIndex++;
cqu++; // another comparison when entering loop
}
cqu++; // at least one comparison in while-condition
while (array[rightIndex] > pivot) {
rightIndex--;
cqu++; // another comparison when entering loop
}
if (leftIndex >= rightIndex) { // finish
break;
} else { // swap
swap(array, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
}
swap(array, leftIndex, rightBound- 1); // restore pivot value
return leftIndex;
}
// sorts values on lowest, highest and position in middle
static char medianOf3(char[] array, int leftBound, int rightBound) {
int center = (leftBound + rightBound) / 2;
if (array[leftBound] > array[center]) {
swap(array, leftBound, center);
}
if (array[leftBound] > array[rightBound]) {
swap(array, leftBound, rightBound);
}
if (array[center] > array[rightBound]) {
swap(array, center, rightBound);
}
cqu = cqu+3; // if-condition is checked anyway
swap(array, center, rightBound-1);
// put pivot on right
return array[rightBound-1];
}
// swaps values of two different positions
static void swap(char[] array, int first, int second) {
char temp = array[first];
array[first] = array[second];
array[second] = temp;
mqu = mqu+3; // three moves per each swap
}
// prints all results of counting
static void printResult(Count se, Count sh) {
Out.println();
Out.println(" ------------------------ ");
Out.println(" Selection Sort:");
Out.println();
Out.println(" "+se.move+" Zuweisungen");
Out.println(" "+se.comp+" Vergleiche");
Out.println(" ------------------------ ");
Out.println(" Shell Sort:");
Out.println(" ------------------------ ");
Out.println(" "+sh.move+" Zuweisungen");
Out.println(" "+sh.comp+" Vergleiche");
Out.println();
Out.println(" Quick Sort:");
Out.println(" ------------------------ ");
Out.println(" "+mqu+" Zuweisungen");
Out.println(" "+cqu+" Vergleiche");
}
static void printHeader(){
Out.println();
Out.println("********************************************");
Out.println("**** Vergleich von Sortierverfahren ****");
Out.println("********************************************");
}// end Header
}
Code:
package Übung5;
public class Count {
int move; // number of assignments
int comp; // number of comparisons
}
