Veröffentlicht 14. Juni 201114 j 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
14. Juni 201114 j 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.
14. Juni 201114 j 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.
14. Juni 201114 j Du sortierst pi, benutzt aber nicht pi[x] für die Vergleiche, sondern a[pi[x]].daten. Bearbeitet 14. Juni 201114 j von Klotzkopp
Archiv
Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.