M
MiNeeMAL
Gast
PHP:
import java.util.Random;
import java.io.*;
@author amadeus p.
public class mSort {
/*sort wird überladen, damit beim späteren testen
* nur ein Array als Eingabe übergeben werden muss.
* */
public static void sort(int[] a){
sort(a,0, a.length-1);
}
//Eigentliche Implementation der Sortiermethode
public static void sort(int[]a, int m, int n){
int left = m;
int right = n;
int mid = (left+right)/2;
int eleft = mid;
int sright = mid+1;
//Behandelt den Fall, dass es sich um ein 1-elementiges Array handelt
if (left >= right){
return;
}
/*rekursiv-nebenläufiger Schritt!
*/
final int [] fa = a;
final int fleft = left;
final int fright = right;
final int fmid = mid;
Runnable lside = new Runnable(){
public void run() {
sort(fa, fleft, fmid);
}
};
Runnable rside = new Runnable(){
public void run() {
sort(fa, fmid+1, fright);
}
};
new Thread(lside).start();
new Thread(rside).start();
while ((left <= eleft) && (sright <= right)){
if (a[left] < a[sright]){
left++;
} else {
int tmp = a[sright];
for (int k = sright - 1; k >= left; k--){
a[k+1] = a[k];
}
a[left] = tmp;
left++;
eleft++;
sright++;
}
}
}
public static int[] fillArray (int n){
int[] a = new int[n];
Random r = new Random();
for (int k = 0; k<n; k++ ){
a[k] = r.nextInt(1000);
}
return a;
}
public static void printArray (int[] a){
for (int k = 0; k<a.length; k++){
System.out.print(a[k]+" ");
}
System.out.println();
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader (
new InputStreamReader(System.in));
System.out.println("Bitte Größe des zu generierenden Arrays eingeben: ");
String gr = in.readLine();
int gr2 = Integer.parseInt(gr);
int [] test = fillArray(gr2);
System.out.println();
System.out.println("Unsortiertes Array");
printArray(test);
Long t1 = System.nanoTime();
sort (test);
Long t2 = (System.nanoTime()-t1);
Long t3 = t2/(1000*1000);
Long t4 = t3/1000;
System.out.println("Sortiertes Array");
printArray(test);
System.out.println("Für den Sortiervorgang wurden " + t2 + " ns, " + t3 + " ms, bzw. ca. " + t4 + " s benötigt.");
}
}Nabend,
sitze im Moment an einer Aufgabe, bei der mittels nebenläufiger Rekursion der Mergesort-Algorithmus implementiert werden soll.
Soweit klappt auch alles, nur schaue ich beim Messen der Laufzeit etwas blöde in die Röhre. In der main-Methode wird ja die Laufzeit von sort() gemessen und die erstellt ja nur die zwei Threads und das war's. Danach spuckt mir die Konsole die Laufzeit aus und der Rechner ackert aber immernoch wie verrückt.
Anzumerken ist noch, dass die gemessene Laufzeit (fast) mit der sequenziell-rekursiven Variante übereinstimmt, was ja nicht stimmen kann.
Wie schaffe ich es denn, dass mir die korrekte Laufzeit ausgegeben wird?
Gruß
