quicksort mit zwei Kriterien sortieren?

tinchi

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.

Wutz

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 $\mathcal{O}(n \log n)$ .