Merge Sort - Array Sortieren

N

Nico1989

Mitglied
Hi !
meine gestriges Problem mit der Wurzelberechnung habe ich gelöst!
Nun habe ich in meinem C Buch weitergelesen und bin vor meinem nächsten Beispiel.

Ich soll mit Merge Sort ein Array Sortieren. Soweit ja nicht tragisch aaaber sämtliche Algorithmen die ich dazu durch Google suchen gefunden habe werde oft oder meißtens in 3 oder gar 4 Funktionen aufgeteilt und das versteh ich absolut nicht.

Ich möchte bei meinen Merge sort einfach ein Array und die Array länge mitgeben, also etwa so:
Code: 
void MergeSort(int[], int n)
{
}

Diese eine Funktion müsste doch ausreichen um Merge Sort verfassen zu können oder nicht ?
Hat vielleicht jemand ein Beispiel das meinen Wünschen nahe kommt um das ganze Nachvollziehen zu können ?

Bin wie immer für jede Helfende Hand Dankbar!

Mfg
Nico
 
Die Aufteilung in mehrere Funktionen ist vA. dazu da,
um Schreibarbeit zu sparen und die Funktion etwas übersichtlicher zu halten.
Du kannst auch den Code einer Nebenfunktion statt dem Aufruf reinkopieren
und die Parameter übertragen...
 
Alles klar erstmal danke ! hat mir geholfen!

Ich habe den Mergesort von Jennesta erstmal so hergenommen wie in Jennesta gepostet hat.
Zustätzlich habe ich noch eine funktionalität die ein Array als parameter einließt unsortiert ausgibt dann sortiert und wieder sortiert ausgibt...doch zur sortierten Ausgabe kommt es leider nicht.

Ich bekomme als Fehler: Segmentation fault (core dumped)
Compiler: Gcc unter Ubuntu

Wenn jemand die Zeit hat bin ich wie immer für jeden Helfer seeeehr dankbar!

Code: 
#include <stdio.h>

void MergeSort(int liste[], int groesse){
 
     if(groesse > 1){
 
         int haelfte1[groesse/2];
         int haelfte2[(groesse + 1)/2];
         int i;
         for(i = 0; i < groesse/2; ++i)
             haelfte1[i] = liste[i];
         for(i = groesse/2; i < groesse; ++i)
             haelfte2[i - groesse/2] = liste[i];
 
         MergeSort(haelfte1,groesse/2);
         MergeSort(haelfte2,(groesse + 1)/2);
 
         int *pos1 = &haelfte1[0];
         int *pos2 = &haelfte2[0];
         for(i = 0; i < groesse; ++i){
             if(*pos1 <= *pos2){
                 liste[i] = *pos1;
                 if (pos1 != &haelfte2[(groesse+1)/2 - 1]) { // pos1 nicht verändern, wenn der größte Wert mehrmals vorkommt
                     if(pos1 == &haelfte1[groesse/2 - 1]){
                         pos1 = &haelfte2[(groesse+1)/2 - 1];
                     }
                     else{
                         ++pos1;
                     }
                 }
             }
             else{
                 liste[i] = *pos2;
                 if(pos2 == &haelfte2[(groesse + 1)/2 - 1]){
                     pos2 = &haelfte1[groesse/2 - 1];
                 }
                 else{
                     ++pos2;
                 }
             }
         }
     }
 }
 
int main(int argc, char* argv[])
{
  int i;
  int j;
  int k;
  k=6;
  int array1[] = {0,0,0,0,0,0};	
  
  for (i=0; i <= 6; i++)
  {
    array1[i] = atoi(argv[i+1]);
    printf("Unsorted Array :%d\n", array1[i]);
  }
  
  MergeSort(array1, k);
  
  for (j=0; j <= 6; j++)
  {
    printf("Sorted Array :%d\n", array1[j]);
  }
  
  return(0);
}
 
a)
Das
C++: 
int array1[] = {0,0,0,0,0,0};
kann man schon so machen, aber wenn du statt 6 lieber 10000 hättest schreibst du sehr viele Nuller.
Warum nicht einfach
C++: 
int array1[6];
?
Die Werte mit 0 vorbelegen ist hier nicht nötig, sie werden danach sowieso vom atoi erst gefüllt.
Wenn nötig könnte man ja dafür eine Schleife machen, aber wie gesagt hier nicht nötig.

b)
Dein Array hat 6 Elemente.
[0], [1], [2], [3], [4], [5]
sind 6 Stück.
Der höchste Index ist also 5.
In deinen zwei Schleifen willst du aber jeweils auch [6] noch haben.
Mach <6 statt <=6
Das wäre einer der zwei Gründe für den Segfault
(eine mögliche Reaktion auf Arrayüberläufe.
Wahrscheinlich die Beste, weil so merkt man wenigstens, dass man einen Fehler hat.
Es könnte auch ganz still und heimlich irgendwas Falsches tun, dass man nicht sofort bemerkt.)

c)
Die zweite Möglichkeit für Arrayüberlauf:
Was ist, wenn dein argv nicht genug Elemente hat?
Die Anzahl ist in argc.
Zuerst prüfen und ggf. Fehlermeldung und Programm beenden.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück