Dans quelles situations utilise-t-on ces algorithmes de tri ?

Question

Je connais l'implémentation de la plupart de ces algorithmes, mais je ne sais pas pour quelles tailles d'ensembles de données les utiliser (et les données incluses) :

1. Tri fusion
2. Tri à bulles (je sais, pas très souvent)
3. Tri rapide
4. Tri par insertion
5. Tri par sélection
6. Tri par base

Answer 1

Tout d'abord, vous prenez tous les algorithmes de tri qui ont une complexité O(n2) et vous les jetez.

Ensuite, vous devez étudier plusieurs propriétés de vos algorithmes de tri et décider si chacun d'eux conviendra mieux au problème que vous souhaitez résoudre. Les plus importants sont :

L'algorithme est-il en place ? Cela signifie que l'algorithme de tri n'utilise pas de mémoire supplémentaire (O(1) en réalité). Cette propriété est très importante lorsque vous exécutez des applications qui nécessitent peu de mémoire.

Tri à bulles, tri par insertion et tri par sélection utilisent une mémoire constante. Il existe également une variante en place pour le tri fusion.

L'algorithme est-il stable ? Cela signifie que si deux éléments x et y sont égaux selon votre méthode de comparaison, et que dans l'entrée x est trouvé avant y, alors dans la sortie x sera trouvé avant y.

Le tri fusion, le tri à bulles et le tri par insertion sont stables.

L'algorithme peut-il être parallélisé ? Si l'application que vous construisez peut utiliser des calculs parallèles, vous voudrez peut-être choisir des algorithmes de tri parallélisables.

Plus d'informations ici.

Answer 2

Utilisez Bubble Sort uniquement lorsque les données à trier sont stockées dans une mémoire à tambour rotatif. C'est optimal à cette fin, mais pas pour la mémoire à accès aléatoire. De nos jours, cela revient à "ne pas utiliser Bubble Sort".

Utilisez Insertion Sort ou Selection Sort jusqu'à une taille que vous déterminez en le testant contre les autres types de tri disponibles. Cela revient généralement à environ 20 à 30 éléments, mais cela peut varier. En particulier, lors de la mise en œuvre de tri par division et conquête comme Merge Sort et Quick Sort, vous devriez "sortir" vers un tri par insertion ou un tri par sélection lorsque votre bloc de données actuel est suffisamment petit.

Utilisez également Insertion Sort sur des données presque triées, par exemple si vous savez d'une manière ou d'une autre que vos données étaient triées auparavant et n'ont pas beaucoup changé depuis.

Utilisez Merge Sort lorsque vous avez besoin d'un tri stable (c'est aussi bon pour le trier les listes chaînées), attention car pour les tableaux, il utilise une mémoire supplémentaire significative.

Généralement, vous n'utilisez pas du tout le "simple" Quick Sort, car même avec un choix intelligent de pivots, il a toujours un pire cas de Omega(n^2), mais contrairement à Insertion Sort, il n'a pas de meilleurs cas utiles. Les cas "meurtriers" peuvent être construits de manière systématique, donc si vous triez des données "non fiables", un utilisateur pourrait délibérément nuire à vos performances, et de toute façon il pourrait y avoir une raison spécifique à votre domaine pour laquelle vos données s'approximent à des cas meurtriers. Si vous choisissez des pivots aléatoires, alors la probabilité de cas meurtriers est négligeable, c'est donc une option, mais l'approche habituelle est "IntroSort" - un QuickSort qui détecte les mauvais cas et bascule vers HeapSort.

Le Radix Sort est un peu particulier. Il est difficile de trouver des problèmes courants pour lesquels il est le meilleur, mais il a une limite asymptotique intéressante pour les données de largeur fixe (O(n), là où les tris par comparaison sont Omega(n log n)). Si vos données sont de largeur fixe et que l'entrée est plus grande que le nombre de valeurs possibles (par exemple, plus de 4 milliards d'entiers sur 32 bits), alors il y a une chance qu'une forme de tri par radix performe bien.

Answer 3

1. Lorsque l'utilisation d'un espace supplémentaire égal à la taille du tableau n'est pas un problème
2. Uniquement sur de très petits ensembles de données
3. Lorsque vous voulez un tri sur place et qu'un tri stable n'est pas nécessaire
4. Uniquement sur de très petits ensembles de données, ou si le tableau a une forte probabilité d'être déjà trié
5. Uniquement sur de très petits ensembles de données
6. Lorsque la plage de valeurs par rapport au nombre d'éléments est faible (expérimentation suggérée)

Notez que les implémentations de Merge ou Quick sort utilisent généralement le tri par insertion pour les parties du sous-routine où le sous-tableau est très petit.