Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
--- Array sotieren (http://www.informatikerboard.de/board/thread.php?threadid=2288)
Geschrieben von Batista am 15.05.2015 um 17:38:
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.
Geschrieben von eulerscheZahl am 15.05.2015 um 18:21:
| 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.
Geschrieben von Batista am 15.05.2015 um 18:38:
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++;
}
|
|
Geschrieben von eulerscheZahl am 15.05.2015 um 19:01:
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.
Geschrieben von Batista am 15.05.2015 um 19:25:
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
Geschrieben von eulerscheZahl am 15.05.2015 um 19:35:
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));
}
} |
|
Geschrieben von Batista am 17.05.2015 um 12:27:
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?
Geschrieben von eulerscheZahl am 17.05.2015 um 17:38:
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.
Geschrieben von Batista am 17.05.2015 um 18:39:
Was meint der Prof mit
" balancierte Unterteilung "?
Geschrieben von eulerscheZahl am 17.05.2015 um 18:41:
Dass du das Intervall in zwei gleichgroße Unterintervalle teilst.
Geschrieben von Batista am 17.05.2015 um 18:55:
QuickSort
Wieso ist die Zahl der Elemente, die kleiner als k sind , k-1 ??
Geschrieben von as_string am 19.05.2015 um 15:23:
| 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
Forensoftware: Burning Board, entwickelt von WoltLab GmbH