Quelqu'un a déjà vu cette amélioration à quicksort?

Manipulation des éléments répétés dans les précédents quicksorts

j'ai trouvé un moyen de gérer les éléments répétés plus efficacement à quicksort et je voudrais savoir si quelqu'un a déjà vu Cela fait avant.

cette méthode réduit considérablement les frais généraux liés au contrôle des éléments répétés, ce qui améliore les performances avec et sans éléments répétés. En général, les éléments répétés sont traités de plusieurs façons différentes que je vais d'abord énumérer.

tout d'abord, il y a la méthode du drapeau national néerlandais qui trie le tableau comme [ < pivot | == pivot | unsorted | > pivot] .

deuxièmement, il y a la méthode de placer les éléments égaux à l'extrême gauche pendant le tri et ensuite les déplacer au centre le tri est [ == pivot | < pivot | unsorted | > pivot] et puis après le tri les éléments == sont déplacés au centre.

Troisièmement, le partitionnement Bentley-McIlroy met les éléments == à la fois côtés de sorte que le tri est [ == pivot | < pivot | unsorted | > pivot | == pivot] et puis les éléments == sont déplacés au milieu.

les deux dernières méthodes sont faites dans une tentative de réduire la tête.

Ma Méthode

maintenant, permettez-moi d'expliquer comment ma méthode améliore le quicksort en réduisant le nombre de comparaisons. J'utilise deux quicksort fonctions d'ensemble plutôt qu'une.

la première fonction que j'appellerai q1 et il trie un tableau comme [ < pivot | unsorted | >= pivot] .

la deuxième fonction que j'appellerai q2 et elle trie le tableau comme [ <= pivot | unsorted | > pivot] .

regardons maintenant l'utilisation de ces en tandem afin d'améliorer le traitement des éléments répétés.

tout d'Abord, nous appelons q1 pour trier tout le tableau. Il choisit un pivot que nous appellerons pivot1 et trie ensuite autour de pivot1 . Ainsi, notre tableau est classé à ce point comme [ < pivot1 | >= pivot1 ] .

ensuite, pour la partition [ < pivot1] , nous l'envoyons à q1 à nouveau, et cette partie est assez normale, alors trions d'abord l'autre partition.

pour la partition [ >= pivot1] , nous l'envoyons à q2 . q2 choisit un pivot, que nous appellerons pivot2 à partir de ce sous-ensemble et le trie en [ <= pivot2 | > pivot2] .

si nous regardez maintenant le tableau entier, notre tri ressemble à [ < pivot1 | >= pivot1 and <= pivot2 | > pivot2] . Cela ressemble beaucoup à un double pivot quicksort.

maintenant, retournons au subarray à l'intérieur de q2 ( [ <= pivot2 | > pivot2] ).

pour la partition [ > pivot2] , nous la renvoyons simplement à q1 ce qui n'est pas très intéressant.

pour la partition [ <= pivot2] , nous vérifions d'abord si pivot1 == pivot2 . S'ils sont égaux, alors cette partition est déjà trié parce qu'ils sont tous des éléments égaux! Si les pivots ne sont pas égaux, alors nous envoyons juste cette partition à q2 encore une fois qui pioche un pivot (plus loin pivot3 ), tries, et si pivot3 == pivot1 , alors il n'a pas à trier le [ <= pivot 3] et ainsi de suite.

J'espère que vous avez compris. L'amélioration avec cette technique est que les éléments égaux sont manipulés sans avoir à vérifier si chaque élément est également égale aux pivots. En d'autres termes, il utilise moins de comparaisons.

il y a une autre amélioration possible que je n'ai pas encore essayé qui est de vérifier dans qs2 si la taille de la partition [ <= pivot2] est assez grande (ou la partition [> pivot2] est très petite) par rapport à la taille de son sous-ensemble total et puis de faire un contrôle plus standard pour les éléments répétés dans ce cas (une des méthodes énumérées ci-dessus).

Code Source

ici sont deux fonctions très simplifiées qs1 et qs2 . Ils utilisent la méthode de tri des pointes convergentes de Sedgewick. Ils peuvent évidemment être très optimisés (ils choisissent pivots extrêmement mal par exemple), mais c'est juste pour montrer l'idée. Mon propre implémentation est plus longue, plus rapide et beaucoup plus difficile à lire donc commençons par ceci:

// qs sorts into [ < p | >= p ]
void qs1(int a[], long left, long right){
    // Pick a pivot and set up some indicies
    int pivot = a[right], temp;
    long i = left - 1, j = right;
    // do the sort
    for(;;){
        while(a[++i] < pivot);
        while(a[--j] >= pivot) if(i == j) break;
        if(i >= j) break;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    // Put the pivot in the correct spot
    temp = a[i];
    a[i] = a[right];
    a[right] = temp;

    // send the [ < p ] partition to qs1
    if(left < i - 1)
        qs1(a, left, i - 1);
    // send the [ >= p] partition to qs2
    if( right > i + 1)
        qs2(a, i + 1, right);
}

void qs2(int a[], long left, long right){
    // Pick a pivot and set up some indicies
    int pivot = a[left], temp;
    long i = left, j = right + 1;
    // do the sort
    for(;;){
        while(a[--j] > pivot);
        while(a[++i] <= pivot) if(i == j) break;
        if(i >= j) break;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    // Put the pivot in the correct spot
    temp = a[j];
    a[j] = a[left];
    a[left] = temp;

    // Send the [ > p ] partition to qs1
    if( right > j + 1)
        qs1(a, j + 1, right);
    // Here is where we check the pivots.
    // a[left-1] is the other pivot we need to compare with.
    // This handles the repeated elements.
    if(pivot != a[left-1])
            // since the pivots don't match, we pass [ <= p ] on to qs2
        if(left < j - 1)
            qs2(a, left, j - 1);
}

je sais que c'est une idée assez simple, mais il donne une amélioration assez significative dans l'exécution quand je ajoutez les améliorations standard de quicksort (choix du pivot médian de-3, et tri d'insertion pour un petit tableau pour un démarrage). Si vous allez tester en utilisant ce code, ne le faites que sur des données aléatoires en raison du mauvais choix du pivot (ou améliorer le choix du pivot). Pour utiliser cette sorte vous appelleriez:

qs1(array,0,indexofendofarray);

Quelques Repères

si vous voulez savoir à quelle vitesse il est, voici un peu de données pour commencer. Cela utilise ma version optimisée, pas la raison donnée ci-dessus. Cependant, celui ci-dessus est encore beaucoup plus proche dans le temps du quicksort à double pivot que le temps std::sort .

sur des données hautement aléatoires avec 2.000.000 d'éléments, j'obtiens ces temps (à partir du tri de plusieurs ensembles de données consécutives):

std::sort - 1.609 seconds  
dual-pivot quicksort - 1.25 seconds  
qs1/qs2 - 1.172 seconds

où std::sort est le C++ Standard Library sort, le quicksort à double pivot est celui qui est sorti il ya plusieurs mois par Vladimir Yaroslavskiy, et qs1/qs2 est mon implémentation rapide.

sur des données beaucoup moins aléatoires. avec 2 000 000 d'éléments et généré avec rand() % 1000 (ce qui signifie que chaque élément a environ 2000 copies) les temps sont:

std::sort - 0.468 seconds  
dual-pivot quicksort - 0.438 seconds  
qs1/qs2 - 0.407 seconds

il y a des cas où le quicksort à double pivot gagne et je me rends compte que le quicksort à double pivot pourrait être optimisé davantage, mais la même chose pourrait être énoncée en toute sécurité pour mon quicksort.

est-ce que quelqu'un a vu ceci avant?

je sais que c'est une longue question/explication, mais n'avez-vous vu cette amélioration? Si oui, alors pourquoi n'est-il pas être utilisé?