Indirektes Sortieren

[rohamis7]

Hallo zusammen ,

ich habe leider ein Verständnis-Problem, nicht unbedingt beim Einfuege-Sortieren (Insertionsort) sondern mehr beim indirekten Insertionsort.

Ich habe eine Reihe von Datensätzen a...a[n] und die sollen schon beim Einfügen "indirekt" sortiert werden.

Dieses "indirekt" bereitet mir Probleme.

Ich weiß dass indirekt einen Index auf die Tabelle sortiert, bzw. die Indiezes statt die Datensätze an sich vertauscht während des Algorithmuses.

Ich komme aber nicht dahinter wie das im Code gemeint sein soll.

Wenn also "Sortieren durch Einfügen" so aussieht (in C, das habe ich ja schon gemacht):

void insert_sort(ds a[], int n)

{

  ds v;                    //Hilfsdatensatz

  int i,j;                  // Laufindizes

  for(i=0;i<n;i++)

  {

    if(a[i-1].daten < a[i].daten)   // wenn aktueller Datensatz kleiner als der davor

    {

      v = a[i];                         //aktuellen Datensatz in Hilfsdatensatz speichern

      j = i;

      do                              //solange j>0 und aktueller Datensatz kleiner als der davor

      {

        a[j] = a[j-1];                  // dann Datensätze vertauschen

        j--;

      }while((j>0) && (v.daten < a[j-1.daten]));


      a[j] = v;

    }

  }

}

wie müsste dann das "indirekte" aussehen?

Sollte ich nicht statt den Datensätzen einfach nur die Indizes umtauschen? Weil ich das ja gemacht habe, aber da nichts sortiert wird.

Danke euch schon mal

[Klotzkopp]

Sollte ich nicht statt den Datensätzen einfach nur die Indizes umtauschen? Weil ich das ja gemacht habe, aber da nichts sortiert wird.

Zeig doch mal, was du da gemacht hast.

Es bringt nichts, wenn du funktionierenden Code fürs falsche Problem zeigst, statt den nicht funktionierenden Code fürs richtige Problem.

[rohamis7]

Danke dir für die Antwort.

Ja du hast Recht aber ich hab ja nicht viel das ist das Problem, weil ich halt nicht so richtig weiß wie ich das mit den Indizes machen soll.

Also es heißt: "Funktion soll eine Permutaion pi[0...n-1] der Zahlen 0...n-1 bestimmten, so dass die Datensätze nach aufsteigenden Daten / Schluessel sortiert sind: a[pi[0]].daten <= a[pi[1]].daten <= ..... <= a[pi[n-1]].daten"

Laut ein bisschen Theorie die ich im Internet finden konnte, habe ich soweit das hier gemacht:

void insert_sort_indirect(ds a[], int pi, int n)

{

  int i,j;                  // Laufindex


  for(i=0;i<n-1;i++)

    pi[i] = i;


  a[0] = -0;


  for(i=1;i<n-1;i++)

  {

    j = i;

    pi[j] = j-1;

  }

  j--;

}

Ich müsste erstmal wissen, besser gesagt verstehen, wie genau das laufen soll (Theorie) dann würde ich das schon in C umsetzen können.

Danke.

[Klotzkopp]

Du sortierst pi, benutzt aber nicht pi[x] für die Vergleiche, sondern a[pi[x]].daten.

Bearbeitet 14. Juni 2011 von Klotzkopp