Est-ce que qsort exige des comparaisons cohérentes ou puis-je l’utiliser pour le armsage?

Mise à jour : Veuillez classer ceci sous de mauvaises idées. Vous n’obtenez rien gratuitement dans la vie et voici une preuve. Une idée simple qui a mal tourné. Cependant, c’est certainement quelque chose à apprendre.

Défi de programmation paresseux. Si je passe une fonction qui 50-50 renvoie true ou false pour la fonction de comparaison du qsort, je pense que je peux effectivement annuler le sorting d’un tableau de structures écrivant 3 lignes de code.

int main ( int argc, char **argv) { srand( time(NULL) ); /* 1 */ ... /* qsort(....) */ /* 2 */ } 

 int comp_nums(const int *num1, const int *num2) { float frand = (float) (rand()) / ((float) (RAND_MAX+1.0)); /* 3 */ if (frand >= 0.5f) return GREATER_THAN; return LESS_THAN; } 

Des pièges que je dois rechercher? Est-ce possible en moins de lignes par permutation ou est-ce le plus propre que je reçois pour 3 lignes non sortingviales?

Mauvaise idée. Je veux dire vraiment mauvais.

Votre solution donne un résultat imprévisible , pas aléatoire et la différence est grande . Vous n’avez aucune idée réelle de ce qu’un qsort fera avec une comparaison aléatoire et si toutes les combinaisons sont également probables. C’est le critère le plus important pour un remaniement: toutes les combinaisons doivent avoir la même probabilité. Des résultats biaisés sont synonymes de gros problèmes. Il n’y a aucun moyen de le prouver dans votre exemple.

Vous devez mettre en œuvre le shuffle Fisher-Yates (également appelé shuffle Knuth).

En plus des autres réponses, cela est pire qu’un simple remaniement Fisher-Yates car il est trop lent. L’algorithme qsort est O (n * log (n)), le Fisher-Yates est O (n).

Quelques explications supplémentaires sont disponibles dans Wikipedia sur les raisons pour lesquelles ce type de “mélange aléatoire” ne fonctionne généralement pas aussi bien que la méthode de Fisher-Yates :

Comparaison avec d’autres algorithmes de armsage

Le shuffle Fisher-Yates est assez efficace; en effet, sa complexité asymptotique dans le temps et dans l’espace est optimale. Associé à une source de nombres aléatoires non biaisés de haute qualité, il garantit également la production de résultats non biaisés. Par rapport à d’autres solutions, elle présente également l’avantage que, si une partie seulement de la permutation résultante est nécessaire, elle peut être arrêtée à mi-parcours, ou même arrêtée et redémarrée à plusieurs resockets, générant la permutation de manière incrémentielle en fonction des besoins. Dans les langages de programmation de haut niveau avec un algorithme de sorting rapide intégré, une méthode alternative, dans laquelle un nombre aléatoire est atsortingbué à chaque élément de l’ensemble à mélanger et à l’ensemble qui est ensuite sortingé en fonction de ces numéros, peut être plus rapide en pratique [ citation nécessaire], malgré le fait que sa complexité temporelle soit asymptotique (O (n log n) vs O (n)). À l’instar du shuffle de Fisher-Yates, cette méthode produira également des résultats non biaisés si elle est correctement mise en œuvre et peut être plus tolérante vis-à-vis de certains types de biais dans les nombres aléatoires. Cependant, il faut veiller à ce que les nombres aléatoires atsortingbués ne soient jamais dupliqués, car les algorithmes de sorting ne commandent généralement pas les éléments de manière aléatoire en cas d’égalité. Une variante de la méthode ci-dessus qui a été utilisée dans les langues prenant en charge le sorting avec des fonctions de comparaison spécifiées par l’utilisateur consiste à mélanger une liste en la sortingant avec une fonction de comparaison renvoyant des valeurs aléatoires. Toutefois, cela ne fonctionne pas toujours: avec un certain nombre d’algorithmes de sorting couramment utilisés, les résultats sont biaisés en raison d’asymésortinges internes dans la mise en œuvre du sorting. [7]

Ce lien vers ici :

Juste une dernière chose En écrivant cet article, j’ai expérimenté différentes versions des méthodes et découvert un autre défaut dans la version originale (renommé par moi en shuffle_sort ). Je me suis trompé quand j’ai dit «cela renvoie un tableau bien mélangé à chaque fois qu’il est appelé».

Les résultats ne sont pas du tout bien mélangés. Ils sont biaisés. Mal. Cela signifie que certaines permutations (c.-à-d. Commandes) d’éléments sont plus probables que d’autres. Voici un autre extrait de code pour le prouver, emprunté à nouveau à la discussion sur le groupe de discussion:

 N = 100000 A = %w(abc) Score = Hash.new { |h, k| h[k] = 0 } N.times do sorted = A.shuffle Score[sorted.join("")] += 1 end Score.keys.sort.each do |key| puts "#{key}: #{Score[key]}" end 

Ce code mélange 100 000 fois le tableau de trois éléments: a, b, c et enregistre combien de fois chaque résultat possible a été atteint. Dans ce cas, il n’y a que six commandes possibles et nous devrions avoir chacune environ 16666.66 fois. Si nous essayons une version non biaisée de shuffle ( shuffle ou shuffle_sort_by ), le résultat est celui attendu:

 
  abc: 16517
  acb: 16893
  bac: 16584
  bca: 16568
  cabine: 16476
  cba: 16962

Bien sûr, il y a quelques écarts, mais ils ne devraient pas dépasser quelques pour cent de la valeur attendue et ils devraient être différents chaque fois que nous exécutons ce code. On peut dire que la dissortingbution est égale.

OK, que se passe-t-il si nous utilisons la méthode shuffle_sort?

  abc: 44278 
  acb: 7462
  bac: 7538
  bca: 3710
  cabine: 3698
  cba: 33314

Ce n’est pas du tout une dissortingbution uniforme. Encore?

Il montre comment la méthode de sorting est biaisée et explique en détail pourquoi. Enfin, il est lié à Coding Horror :

Jetons un coup d’œil au bon algorithme de mélange de Knuth-Fisher-Yates.

 for (int i = cards.Length - 1; i > 0; i--) { int n = rand.Next(i + 1); Swap(ref cards[i], ref cards[n]); } 

Voyez-vous la différence? Je l’ai raté la première fois. Comparez les swaps pour un jeu de 3 cartes:

 
 Mélange naïf Mélange Knuth-Fisher-Yates
 rand.Next (3);  rand.Next (3);
 rand.Next (3);  rand.Next (2);
 rand.Next (3); 

Le shuffle naïf donne 3 ^ 3 (27) combinaisons possibles. C’est étrange, car les mathématiques nous disent qu’il n’y en a vraiment que 3! ou 6 combinaisons possibles d’un jeu de 3 cartes. Dans le mélange KFY, nous commençons par une commande initiale, échangeons de la troisième position avec l’une des trois cartes, puis échangeons de la deuxième position avec les deux cartes restantes.

Non, cela ne mélangera pas correctement le tableau, il déplacera à peine les éléments autour de leur emplacement d’origine, avec une dissortingbution exponentielle.

La fonction de comparaison n’est pas censée renvoyer un type booléen, elle est censée renvoyer un nombre négatif, un nombre positif ou zéro que qsort() utilise pour déterminer quel argument est supérieur à l’autre.

The Old New Thing prend celui-ci

Je pense que l’idée de base de partitionner aléatoirement l’ensemble de manière récursive vers le bas et de concaténer les résultats vers le haut fonctionnera (elle fera la moyenne sur O (n * log n) décisions binarys et c’est sacrément proche de log2 (fact (n) ) mais q-sort ne sera pas sûr de le faire avec un prédicat aléatoire.

BTW Je pense que le même argument et les mêmes problèmes peuvent être affirmés pour toute stratégie de sorting O (n * log n).

Rand n’est pas la chose la plus aléatoire qui soit … Si vous voulez mélanger les cartes ou autre chose, ce n’est pas la meilleure. De plus, un mélange de Knuth serait plus rapide, mais votre solution est acceptable si elle ne tourne pas en boucle pour toujours