Trier 10 millions d'objets en temps O (n) et O (1) en mémoire supplémentaire

Question

J'essaie de trouver une réponse à une question d'entrevue que j'ai reçue récemment mais que je n'ai pas pu résoudre. On m'a demandé de trier 10 millions d'objets (chacun contient un entier de 10 bits et une valeur de chaîne unique) par l'entier de 10 bits en place en utilisant l'espace O (1) et le temps O (n). Dans tous les cas intensifs, la valeur de la chaîne rend le problème plus difficile, mais vous ne le faites pas trier.

Je pensais utiliser le tri par comptage, mais cela ne fonctionnerait que si je ne faisais que trier les entiers de 10 bits. Le tri des objets rend les choses un peu plus compliquées, car j'ai besoin de garder une trace de leurs valeurs de chaînes uniques. J'ai regardé le tri radix, mais il semble utiliser O (n) comme le pire des cas.

Y at-il un type de tri qui me manque?

Answer 1

There's an in-place (MSB) radix sort.

Il va quelque chose comme ceci:

• Commencez avec le premier bit.

• Déplacez tous les éléments dont le bit est égal à 0 vers la gauche
  et tous ceux dont le bit est égal à 1 sur la droite.

  Vous faites cela de la même manière que le quicksort en vous déplaçant des deux côtés vers le milieu, en échangeant les 1 sur la gauche avec les 0 sur la droite.

• Recourber à la fois du côté gauche et du côté droit en tenant compte du bit suivant.

Le processus ressemble à ceci:

 ↓    ↓ 
     0...    1... 
--------------- --------------- 
    ↓  ↓  ↓  ↓ 
00... 01... 10... 11... 
------- ------- ------- ------- 
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 
000 001 010 011 101 110 110 111 
--- --- --- --- --- --- --- --- 
... 

La complexité du temps est O(bits*n) et la complexité de l'espace est O(bits). Donc, avec un nombre constant de bits, la complexité temporelle est de O(n) et la complexité de l'espace est de O(1)

---

---

Il est également possible de le faire en utilisant comptage sorte (avec en même temps et de la complexité de l'espace).

• Compter le nombre de chaque élément. En utilisant ceci, vous pouvez déterminer où placer ces éléments dans le tableau.

• Créer une table de correspondance (index de mappage à décalage, peut être un tableau) contenant tous les points de départ ci-dessus, qui seront utilisés pour déterminer où l'élément suivant doit aller.

• Maintenant, vous faites une boucle sur la matrice et permutez chaque élément qui n'a pas sa place à la première place, puis faites de même avec chaque élément que nous avons échangé, jusqu'à ce que l'élément actuel soit à sa place.

  Augmentez le décalage de l'élément concerné dans la table de recherche à chaque étape. Notez qu'il est impossible d'échanger deux fois le même élément, donc ce sera le temps linéaire.

Tout cela semble très confus, alors voici un exemple:

4 5 3 1 2 3 4 4 1 5 4 3 2 3 

// counts: 
1: 2, 2: 2, 3: 4, 4: 4, 5: 2 

// the starting points (offsets) based on the counts: 
1 at position 0 
2 at position (offset of 1)+(count of 1) = 0+2 = 2 
3 at position (offset of 2)+(count of 2) = 2+2 = 4 
4 at position (offset of 3)+(count of 3) = 4+4 = 8 
5 at position (offset of 4)+(count of 4) = 8+4 = 12 

// sorting: 
4 5 3 1 2 3 4 4 1 5 4 3 2 3 // out of place, swap with offsets[4] = 8 (offsets[4]++) 
^ 

1 5 3 1 2 3 4 4 4 5 4 3 2 3 // in correct position, moving on   (offsets[1]++) 
^ 

1 5 3 1 2 3 4 4 4 5 4 3 2 3 // swap with offsets[5] = 12    (offsets[5]++) 
^

1 2 3 1 2 3 4 4 4 5 4 3 5 3 // swap with offsets[2] = 2    (offsets[2]++) 
^

1 3 2 1 2 3 4 4 4 5 4 3 5 3 // swap with offsets[3] = 4    (offsets[3]++) 
^

1 2 2 1 3 3 4 4 4 5 4 3 5 3 // swap with offsets[2] = 3    (offsets[2]++) 
^

1 1 2 2 3 3 4 4 4 5 4 3 5 3 // in correct position, moving on   (offsets[1]++) 
^

1 1 2 2 3 3 4 4 4 5 4 3 5 3 // in correct position, moving on   (offsets[2]++) 
    ^

Vous avez l'idée ...

Notez que la taille de la table de comptage et la table de consultation sont O(max value) , qui est O(1) si chaque nombre contient un nombre fixe de bits.

Et vous faites une quantité constante de travail pour chaque élément, donc c'est O(n) temps.

Answer 2

Vous pouvez utiliser le code de pivotement standard de quicksort pour déplacer tous les éléments avec un entier de 0 au début de la matrice. Continuez avec 1, 2, 3, et ainsi de suite, sur les éléments restants, en vous arrêtant une fois que vous avez pivoté sur 1023.

Ceci itére à travers le tableau 1024 fois, et chaque pivot prend le temps O (n), ainsi Sur).

Une approche très similaire qui sera plus efficace dans la pratique consiste simplement à utiliser un algorithme standard de tri rapide à trois voies. Normalement, on considère que ceci prend un temps O (n log n) et utilise un espace O (log n) dans le pire des cas. Mais ici, le domaine des entiers est limité à 1024 valeurs, il est donc garanti de finir en temps O (n) et d'utiliser l'espace O (1), puisque dans chaque appel récursif à quicksort, une valeur de pivot ne sera jamais utilisée deux fois.

[Cette réponse fait une hypothèse - que "10 millions" dans la question est n, et que "10 bits" reste fixe].