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


Log in to reply