Tri efficace de mots de N bits tournés

Question

Étant donné un tableau arr qui contient des mots de N bits dans un ordre trié, existe-t-il un algorithme efficace pour trier le résultat de la rotation de tous les éléments du tableau vers la gauche d'un bit - de préférence avec un facteur constant plus petit qu'en utilisant le tri radix/american flag.

sortRotated(arr : Array<Word32>)
  for(I in indices arr)
    arr[i] = rotateLeft(arr[i],1) // 0bXn..n => 0bn..nX
  efficientSort(arr)

Il semble que cela devrait être possible en temps linéaire, nous savons quelque chose sur l'ordre des éléments dans les groupes qui correspondent. 0b0..0 , 0b0..1 , 0b1..0 y 0b1..1 .

Answer 1

Considérez le tableau d'entrée comme deux partitions. La première est une liste triée de tous les mots avec le bit de tête 0. La seconde est la même chose avec le bit de tête 1. Ces bits sont tournés vers la position la plus à droite. Ce qui reste est deux listes triées. Une seule passe de fusion les trie.

#include <stdio.h>
#include <stdlib.h>

void rotate_and_resort(unsigned *a, int n) {
  // rotate
  for (int i = 0; i < n; ++i) a[i] = (a[i] << 1) | (a[i] >> 31);

  // resort; find the first word with rightmost bit 1
  int rm1;
  for (rm1 = 0; rm1 < n && (a[rm1] & 1) == 0; ++rm1) /* skip */;

  // If all the words end with the same bit, we're done.
  if (rm1 == 0 || rm1 == n) return;

  // make a temp copy for merging
  unsigned t[n];
  for (int i = 0; i < n; ++i) t[i] = a[i];

  // merge
  int i = 0, j = rm1, k = 0;
  while (k < n)
    a[k++] = i < rm1 && t[i] < t[j] ? t[i++] : t[j++];
}

int cmp_unsigned(const void *va, const void *vb) {
  unsigned a = *(unsigned*)va, b = *(unsigned*)vb;
  return a > b ? 1 : a < b ? -1 : 0;
}

int main(void) {
  unsigned n = 100, a[n];
  for (int i = 0; i < n; ++i) a[i] = rand() ^ (rand() << 16);
  qsort(a, n, sizeof *a, cmp_unsigned);
  rotate_and_resort(a, n);
  for (int i = 0; i < n; ++i) printf("%u\n", a[i]);
  return 0;
}

Il existe un algorithme de fusion plus sophistiqué où l'espace temporaire est au plus égal à la moitié de la taille de l'entrée. Ici j'ai utilisé l'algorithme le plus simple, qui fait une copie complète.

Answer 2

Ma première idée serait d'identifier les quatre blocs de vos données :

• 0b00... (devient 0b0...0 ),
• 0b01... (devient 0b1...0 ),
• 0b10... (devient 0b0...1 ),
• 0b11... (devient 0b1...1 ),

Notez que dans les quatre blocs, les données sont toujours triées, sauf pour le dernier bit. Nous pouvons donc corriger cela en une seule passe. (Il peut s'agir de la même passe qui identifie l'étendue des quatre blocs). Si vous n'avez pas d'éléments répétitifs, il suffit de trouver tout K impair qui est suivi de K-1 et de les échanger. Si vous avez des répétitions, alors vous devrez avoir des mini-sorts de K y K-1 des régions, donc c'est un peu plus compliqué, mais pas de beaucoup.

Vous vous retrouvez alors avec quatre tableaux triés, où tous les éléments de 1st et 3rd ( 0b0... ) sera toujours plus petit que tous les éléments des 2ème et 4ème ( 0b1... ). Ainsi, en appliquant le tri par fusion aux 1er et 3e, puis en concaténant le résultat avec le tri par fusion des 2e et 4e, vous obtiendrez le résultat correct.

EDIT : désolé pour les nombreuses réécritures, j'ai juste trouvé une erreur dans ma logique après l'autre pendant que j'écrivais :)