import java.io.*;
import java.util.Date;
/** Übungen zu Grundlagen der Informatik
* Kapitel 10 Aufgabe 1
* @author Thomas Walter
*/
public class Uebung101 {
/** Vertauschung von zwei Elementen */
private static void swapInt (int[] container, int von, int wohin) {
int temp;
temp = container[wohin];
container[wohin] = container[von];
container[von] = temp;
} // swapInt
/** findet Index des Maximums in Teilarray */
private static int max (int[] container, int von, int bis) {
int max = von;
for (int i = von + 1; i <= bis; i++)
if (! (container[i] <= container[max]))
max = i;
return max;
} // max
/** BubbleSort-Algorithmus */
public static void bubbleSort(int[] container) {
int grenze = container.length - 1, t;
do {
t = 0;
for (int j = 0; j <= grenze - 1; j++)
if (! (container[j] <= container[j+1])) {
swapInt (container, j, j+1);
t = j;
}
grenze = t;
} while (t != 0);
} // bubbleSort
/** SelectionSort-Algorithmus */
public static void selectionSort(int[] container) {
int i;
for (int j = container.length -1; j >= 1; j--) {
i = max(container, 0, j);
swapInt (container, i, j);
}
} //selectionSort
/** InertionSort-Algorithmus */
public static void insertionSort(int[] container) {
int i, k;
for (int j = 1; j <= container.length - 1; j++) {
i = j -1;
k = container[j];
while (i >= 0 && !(container[i] <= k)) { // Reihenfolge des Vergleichs beachten
container[i+1] = container[i];
i--;
}
container[i+1] = k;
}
} // insertionSort
/** Liest int-Array mit Namen name ein */
private static int [] lesen (String name) throws java.io.IOException {
FileInputStream fin = new FileInputStream (name);
DataInputStream in = new DataInputStream (fin);
int [] zufall = new int [in.available() / 4];
int pos = 0;
while (in.available() > 0) {
zufall [pos] = in.readInt();
pos++;
}
in.close();
fin.close();
return zufall;
} // lesen
public static void main (String args []) throws java.io.IOException {
//////////// BubbleSort ////////////////
int [] zufall1 = lesen ("zufall1");
int [] zufall2 = lesen ("zufall2");
Date t1 = new Date();
bubbleSort(zufall1);
Date t2 = new Date();
bubbleSort (zufall2);
Date t3 = new Date();
long dauer1 = t2.getTime() - t1.getTime();
long dauer2 = t3.getTime() - t2.getTime();
System.out.println("\n Dauer Sortieren von zufall1 mit BubbleSort: "+dauer1+" ms");
System.out.println(" Dauer Sortieren von zufall2 mit BubbleSort: "+dauer2+" ms\n");
//////////// SelectionSort ////////////////
zufall1 = lesen ("zufall1");
zufall2 = lesen ("zufall2");
t1 = new Date();
selectionSort(zufall1);
t2 = new Date();
selectionSort (zufall2);
t3 = new Date();
dauer1 = t2.getTime() - t1.getTime();
dauer2 = t3.getTime() - t2.getTime();
System.out.println(" Dauer Sortieren von zufall1 mit SelectionSort: "+dauer1+" ms");
System.out.println(" Dauer Sortieren von zufall2 mit SelectionSort: "+dauer2+" ms\n");
//////////// InsertionSort ////////////////
zufall1 = lesen ("zufall1");
zufall2 = lesen ("zufall2");
t1 = new Date();
insertionSort(zufall1);
t2 = new Date();
insertionSort (zufall2);
t3 = new Date();
dauer1 = t2.getTime() - t1.getTime();
dauer2 = t3.getTime() - t2.getTime();
System.out.println(" Dauer Sortieren von zufall1 mit InsertionSort: "+dauer1+" ms");
System.out.println(" Dauer Sortieren von zufall2 mit InsertionSort: "+dauer2+" ms\n");
} // main
} // Uebung101