T
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.
