S
So, die MergeSort Funktion hab ich jetzt geschafft richtig ins das vorgegebene Programm zu implementieren. Als nächstes sollen wir jetzt aber den Natural Mergesort Algorithmus anwenden, also er gucken, ob es schon runs gibt. Meine Idee war bisher folgendes:
void merge_sort_mod( int numbers[], const int zahlen_anzahl) {
if(zahlen_anzahl > 1){
/* ------------ Aufspalten der Zahlen ----------- */
/* Schnittstelle finden */
int cut=0;
int j;
for (j=0; j < zahlen_anzahl/2; j++) {
if (cut==0) { /* Wenn cut einen Wert erhalten hat, wurde schon eine Schnittstelle gefunden */
if (cut==0){
if (numbers[zahlen_anzahl/2 + j] > numbers[zahlen_anzahl/2 + j + 1])
cut = (zahlen_anzahl/2 + j);
}
if (cut==0) {
if (numbers[zahlen_anzahl/2 - j] < numbers[zahlen_anzahl/2 - j - 1])
cut = (zahlen_anzahl/2 - j - 1);
}
}
else break;
}
int haelfte1[cut];
int haelfte2[(zahlen_anzahl - cut)];
int i;
for(i = 0; i < cut; i++) /*In die erste Hälfte werden die ersten Zahlen reingeschrieben */
haelfte1[i] = numbers[i];
for(i = cut; i < zahlen_anzahl; i++) /*In die zweite Hälfte werden die übrigen Zahlen reingeschrieben */
haelfte2[i - cut] = numbers[i];
/*--------- Funktion wird in sich selber aufgerufen -------------*/
merge_sort_mod(haelfte1, cut); /*Die Funktion ruft sich selber auf, die Anzahl der Zahlen und die
die Zahlen in jedem "Abschnitt" verändern sich dabei jedes mal, bis zahlen_anzahl = 1) */
merge_sort_mod(haelfte2,(zahlen_anzahl - cut));
/* --------- Sortieren der Zahlen ------------ */
int *pointer1 = &haelfte1[0];
int *pointer2 = &haelfte2[0];
for(i = 0; i < zahlen_anzahl; i++){
if(*pointer1 <= *pointer2){
numbers[i] = *pointer1;
if (pointer1 != &haelfte2[(zahlen_anzahl - cut) - 1]) { // pointer1 nicht verändern, wenn der größte Wert mehrmals vorkommt
if(pointer1 == &haelfte1[cut - 1]){
pointer1 = &haelfte2[(zahlen_anzahl - cut) - 1];
}
else{
pointer1++; //Der Pointer zeigt auf die nächste Zahl
}
}
}
else{
numbers[i] = *pointer2;
if(pointer2 == &haelfte2[(zahlen_anzahl -cut ) - 1]){
pointer2 = &haelfte1[cut - 1];
}
else{
pointer2++;
}
}
}
}
}
Vielleicht noch zur Ergänzung: numbers[] sind Zahlen von 0 - zahlen_anzahl die vorher schon gemischt wurden.
Hab ich da irgendwo einen Denkfehler drin?
Wie immer, danke schon mal für die Antworten
