quicksort mit zwei Kriterien sortieren?
-
Also ich möchte qsort so implementieren, dass erstens meine Zahlen ganz normal sortiert werden, ich mir dabei aber speichere, wo welche Zahl gelandet ist, also wenn ich diese Liste habe:
4 3 7 2
[0] [1] [2] [3],Dann habe ich nach dem sortiereN:
2 3 4 7
[3] [1] [0] [2] <== so weiss ich wo welches Element ist.void qsort_my(int *a, int l, int r, int *array_order) { int j; if( l < r ) { j = split( a, l, r, array_order); qsort_my( a, l, j-1, array_order); qsort_my( a, j+1, r, array_order); } } int split(int *a, int l, int r, int *array_order) { int pivot, i, j, t; pivot = a[l]; i = l; j = r+1; int switch_pos_temp; while (1) { do ++i; while (a[i] >= pivot && i < r); do --j; while (a[j] < pivot); if (i >= j) break; switch_pos(&a[i], &a[j]); switch_pos(&array_order[i], &array_order[j]); } switch_pos(&a[l], &a[j]); switch_pos(&array_order[l], &array_order[j]); return j; } void switch_pos(int *one, int *two) { int temp = *one; *one = *two; *two = temp; }
So jetzt möchte ich aber noch hinzufügen, wenn es zwei gleiche Elemente sind, dass sie dann nach auftreten in der Liste sortiert werden, also wenn sowas auftritt:
9 9
[0] [5]Dann bleiben die Elemente, aber in diesem Beispiel:
9 9
[5] [0]würde ich die zwei 9en tauschen (hat Sinn in meinem Programm :)). Hat jemand vllt irgendeine Idee, wie man das machen könnte? Ich habe versucht dieses Kriterium in Zeile 24 und 21 einzubauen:
if (a[i] != a[j] || (a[i] == a[j] && array_order[i] > array_order[j]))
Aber das funktioniert natürlich nicht, weil durch qsort ja passieren kann, das z.B. diese Teilliste entsteht:
11 9 15 9 <= wo 11 und 15 getauscht werden, aber dadurch die zwei 9en nie verglichen werden.
Ein zweiter Lauf von qsort kommt hier nicht in frage, weil meine Laufzeit dadurch zu langsam wird.
-
Packe Index und Wert in eine struct(Liste), und sortiere diese dann mit normalem qsort. Deine Bastelei sieht schlimm aus.
-
Das was du möchtest, nennt sich zum einen indirektes Sortieren. Die andere Anforderung die du hast nennt sich Stabilität. Du suchst also ein indirektes, stabiles Sortierverfahren (Google). Da Quick-Sort nicht stabil ist, solltest du vielleicht lieber Mergesort verwenden. Dies hat selbst im Worst-Case den Aufwand .