| 15.05.2015, 17:38 |
Auf diesen Beitrag antworten » |
| Batista |
Array sotieren
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
|
}
/** Teilarray of int sortieren mittels MergeSort */
public static void mergesort(int[] daten, int[] tmp, int start, int ende) {
if (start >= ende) { return; } // Max 1 Element: fertig!
// Divide:
final int half = (start + ende) / 2;
// Conquer:
mergesort(daten, tmp, start, half);
mergesort(daten, tmp, half + 1, ende);
// Merge:
int i = start, j = half + 1, k = start;
while (i <= half && j <= ende) {
if (daten[i]<daten[i+1]){
tmp[i]= daten[i];
tmp[i+1]=daten[i+1];
}else {
tmp[i+1]= daten[i];
tmp[i]=daten[i+1];
}
if (daten[j-1]<daten[j]){
tmp[j-1]= daten[j-1];
tmp[j]=daten[j];
}else {
tmp[j]= daten[j-1];
tmp[j-1]=daten[j];
}
i++;
j++;
}
while (i <= half) {
if (daten[i]<daten[i+1]){
tmp[i]= daten[i];
tmp[i+1]=daten[i+1];
}else {
tmp[i+1]= daten[i];
tmp[i]=daten[i+1];
}
i++;
}
while (j <= ende) {
if (daten[j]<daten[j+1]){
tmp[j]= daten[j];
tmp[j+1]=daten[j+1];
}else {
tmp[j+1]= daten[j];
tmp[j]=daten[j+1];
}
j++;
}
// aus tmp zurueck kopieren:
for (int l = start; l < k; l++) {
daten[l] = tmp[l];
}
}
public static void main (String[] args){
int [] testarray= {-2,-3};
sort(testarray);
for (int i =0; i<testarray.length;i++){
System.out.print(testarray[i]+",");
}
}
}
|
|
Die Aufgabe dazu ist
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
|
public class MergeSort {
/** Array of int sortieren mittels MergeSort */
public static void sort(int[] daten) {
mergesort(daten, new int[daten.length], 0, daten.length - 1);
}
/** Teilarray of int sortieren mittels MergeSort */
public static void mergesort(int[] daten, int[] tmp, int start, int ende) {
if (start >= ende) { return; } // Max 1 Element: fertig!
// Divide:
final int half = (start + ende) / 2;
// Conquer:
mergesort(daten, tmp, start, half);
mergesort(daten, tmp, half + 1, ende);
// Merge:
int i = start, j = half + 1, k = start;
while (i <= half && j <= ende) {
// TODO: Implementieren
}
while (i <= half) { // Rechter Teil schon leer!
// TODO: Implementieren
}
while (j <= ende) { // Linker Teil schon leer!
// TODO: Implementieren
}
// aus tmp zurueck kopieren:
for (int l = start; l < k; l++) {
daten[l] = tmp[l];
}
}
}
|
|
Der code macht nichts? Habe es divers mal geändert, aber es tut sich nichts. |
| |
| |
|
| 15.05.2015, 18:21 |
Auf diesen Beitrag antworten » |
| eulerscheZahl |
| code: |
1:
|
if (daten[i]<daten[i+1]) |
|
was soll das bringen, du hast zwei teilsortierte Listen bei i und j und musst die jeweils vergleichen.
Ich habe genau eine if Abfrage: if (daten[i] < daten[j])
Und die Zahl der insgesamt zu ergänzenden Zeilen ist bei mir 7, 5 davon im ersten Block. |
| 15.05.2015, 18:38 |
Auf diesen Beitrag antworten » |
| Batista |
Die Merge habe nun verändert, aber es tut es nichts
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
|
// Merge:
int i = start, j = half + 1, k = start;
while (i <= half && j <= ende) {
if (daten[i]<daten[j]){
tmp[i]= daten[i];
tmp[j]=daten[j];
}else {
tmp[i]= daten[j];
tmp[j]=daten[i];
}
i++;
j++;
}
|
|
|
| 15.05.2015, 19:01 |
Auf diesen Beitrag antworten » |
| eulerscheZahl |
Ist ja auch falsch.
Es wird immer in tmp[k++] geschrieben.
Und zwar das Minimum von daten[i] und daten[j]. Und nur ein Index wird erhöht, und zwar von der Teilliste, wo der Wert übernommen wurde. |
| Anzeige |
| |
|
| 15.05.2015, 19:25 |
Auf diesen Beitrag antworten » |
| Batista |
Erst läuft er, supii.
Dankeschön^^
Wie ist es wenn, man ein zufällig erstellt printen möchte?
public static void main (String[] args){
int [] testarray= new int [10];
for (int i =0; i<testarray.length;i++){
testarray[i]=random(testarray.length);
System.out.print(testarray[i]+",");
}
}
Es wird die Funktion random nicht erkannt |
| 15.05.2015, 19:35 |
Auf diesen Beitrag antworten » |
| eulerscheZahl |
Die Funktion heißt Math.random() und liefert ein double. Alternativ kannst du auch die Random Klasse bemühen.
Hier der komplette Code, damit spätere Leser auch noch etwas davon haben:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
|
import java.util.Arrays;
public class Main {
public static void sort(int[] daten) {
mergesort(daten, new int[daten.length], 0, daten.length - 1);
}
/** Teilarray of int sortieren mittels MergeSort */
public static void mergesort(int[] daten, int[] tmp, int start, int ende) {
if (start >= ende) {
return;
} // Max 1 Element: fertig!
// Divide:
final int half = (start + ende) / 2;
// Conquer:
mergesort(daten, tmp, start, half);
mergesort(daten, tmp, half + 1, ende);
// Merge:
int i = start, j = half + 1, k = start;
while (i <= half && j <= ende) {
if (daten[i] < daten[j]) {
tmp[k++] = daten[i++];
} else {
tmp[k++] = daten[j++];
}
}
while (i <= half) { // Rechter Teil schon leer!
tmp[k++] = daten[i++];
}
while (j <= ende) { // Linker Teil schon leer!
tmp[k++] = daten[j++];
}
// aus tmp zurueck kopieren:
for (int l = start; l < k; l++) {
daten[l] = tmp[l];
}
}
public static void main(String[] args) {
int[] testarray = new int[10];
for (int i = 0; i < testarray.length; i++) {
testarray[i] = (int) (Math.random() * testarray.length);
}
sort(testarray);
System.out.println(Arrays.toString(testarray));
}
} |
|
|
| 17.05.2015, 12:27 |
Auf diesen Beitrag antworten » |
| Batista |
directupload.net/file/d/3990/jwqeyi96_jpg.htm
Wieso erfolgt die Aufteilung des Array in O(1)? Das müsste doch von Anzahl der Elemente im Array abhängen?
Laufzeit des Conquer-Schrittes:
ist 2* T(n)-> Wieso die 2, ich verstehe die Erklärung nicht
aufzeit des Merge-Schrittes ist O(n), verstehe ich auch nicht.
Denn im dem Merge Schritt werden doch 2 Teilarray immer betrachtet und wächst damit es gegen ende gegen n? |
| 17.05.2015, 17:38 |
Auf diesen Beitrag antworten » |
| eulerscheZahl |
Beim Aufteilen rechnest du nur int half = (start + ende) / 2;, um dann die Funktion rekursiv für beide Hälften aufzurufen. Das hat nichts mit der Anzahl der Daten zu tun, also O(1).
Du zerlegst das Array in zwei (daher der Faktor 2) teile mit jeweils halber Größe (n/2), um diese zu sortieren.
Und du musst jeden Wert von tmp in daten kopieren, also O(n)
Es wird hier nur ein Durchlauf betrachtet, nicht die rekursiven Untersortierungen.
Dieser eine Durchlauf geht in O(n). Da es log(n) rekursive Aufrufe gibt, hast du O(n*log(n)).
Und lade die Bilder bitte künftig hier hoch. Dann sind sie nicht in einem halben Jahr gelöscht und andere Leser haben auch noch etwas davon. |
| 17.05.2015, 18:39 |
Auf diesen Beitrag antworten » |
| Batista |
Was meint der Prof mit
" balancierte Unterteilung "? |
| 17.05.2015, 18:41 |
Auf diesen Beitrag antworten » |
| eulerscheZahl |
Dass du das Intervall in zwei gleichgroße Unterintervalle teilst. |
| 17.05.2015, 18:55 |
Auf diesen Beitrag antworten » |
| Batista |
QuickSort
Wieso ist die Zahl der Elemente, die kleiner als k sind , k-1 ?? |
| 19.05.2015, 15:23 |
Auf diesen Beitrag antworten » |
| as_string |
| Zitat: |
Original von Batista
QuickSort
Wieso ist die Zahl der Elemente, die kleiner als k sind , k-1 ?? |
Nicht die Element(-Werte) sind kleiner k, sondern die Elemente mit einer Position kleiner k sind gemeint.
Du hast n Elemente und teilst bei Position k (Wobei die Elemente mit Positionsnummern quasi durchnummeriert sind). Dann sind doch logischerweise links von k noch k-1 Elemente übrig.
Gruß
Marco |
