Array sotieren |
Batista unregistriert
|
|
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 17:38 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
15.05.2015 18:21 |
|
|
Batista unregistriert
|
|
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 18:38 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
15.05.2015 19:01 |
|
|
Batista unregistriert
|
|
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:25 |
|
|
|
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));
}
} |
|
__________________ Syntax Highlighting fürs Board (Link)
|
|
15.05.2015 19:35 |
|
|
Batista unregistriert
|
|
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 12:27 |
|
|
Batista unregistriert
|
|
Was meint der Prof mit
" balancierte Unterteilung "?
|
|
17.05.2015 18:39 |
|
|
as_string
Haudegen
Dabei seit: 06.11.2013
Beiträge: 638
Herkunft: Heidelberg
|
|
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
|
|
19.05.2015 15:23 |
|
|
|