Quel est l'algorithme de tri à espace constant le plus efficace?

Je recherche un algorithme de tri pour les tableaux int qui n'alloue aucun octet autre que la taille du tableau et est limité à deux instructions:

1. SWAP: échange le prochain index avec celui en cours;

2. MOVE: déplace le curseur sur un index +1 ou -1;

Autrement dit, vous ne pouvez pas échanger des index non voisins, ni échanger l'index 100, après avoir simplement échangé l'index 10. Quel est l'algorithme le plus efficace - c'est-à-dire celui qui utilise le moins de mouvements totaux?

Considérez le tri du shaker à cocktail , qui est une version bidirectionnelle du tri à bulles. Vous faites des bulles de bas en haut, puis (c'est la partie ajoutée) vous faites des bulles de haut en bas, répétez jusqu'à ce que cela soit fait. C'est toujours , mais cela fait beaucoup moins de passes en moyenne, car les petits éléments près de l'extrémité supérieure du tableau seront déplacés vers leur position finale en une seule passe plutôt que N passes. De plus, vous pouvez garder une trace des positions les plus basses et les plus hautes où un swap s'est produit; les passes suivantes n'ont pas besoin de balayer au-delà de ces points.$O(n^2)$

Le nombre de swaps d'éléments adjacents nécessaires pour commander un tableau est égal au nombre d'inversions dans le tableau. Avec n éléments au total, il y a au plus n * (n-1) / 2 inversions, donc le tri par bulles donne le nombre asymptotiquement optimal de swaps dans ce modèle.

$O(n^2)$

$-\infty$$+\infty$

L'algorithme qui n'utilise pas d'indicateur booléen pour savoir si nous avons échangé un élément ou non, est donné ci-dessous (l'astuce pour conserver les informations dans l'état de la machine, plutôt que dans la mémoire):

Start:
    Do until we are not at the leftmost position (Op 4)
        move left (Op 2b)

Check:
    If we are at rightmost position (Op 3)
        goto Finished:
    If current value is larger than next value (Op 5)
        goto Unfinished:
    move right (Op 2a)
    Repeat Check:

Unfinished:
    If we are at rightmost position (Op 3)
        goto Start:
    If current value is larger than next value (Op 5)
        swap the elements (Op 1) and move right (Op 2a)
    Repeat Unfinished:

Finished:
    The list is sorted now, output it.

La solution d'Eric Lippert, le tri gnome fonctionne également, car il s'agit essentiellement d'un tri à bulles bidirectionnel.