Discussion :

[fpasquer]

Bonjour, je suis entrain de coder un programme qui utilise un pivot pour trier des données.

Je vais vous donner un exemple pour que vous comprenez bien.

Imaginons, une liste chainée avec les valeurs suivantes :

-7 -8 -3 35 2

Pour avoir un pivot optimal, j'ai besoin dans cet exemple, de la valeur qui a 2 valeurs en dessous, et 2 valeurs au dessus. Donc ici -3. Pour trouver cette valeur c'est simple, je parcours x fois ma liste chainée jusqu'a trouver une valeur qui a 2 valeurs en dessous et 2 valeurs au dessus.

Le problème est le suivant :

Imaginons la liste chainée suivante :

-7 -8 35 3 -3

Dans cet exemple, mon pivot est toujours -3. Mais pour le trouver, j'ai dû parcourir toutes la liste chainée. Dans l'exemple, elle est de 5 valeurs. Ce n'est pas grave. Mais si ma liste chainée fait 2000 valeurs voir plus, je me retrouve a attendre trop longtemps pour avoir le résultat de mon pivot.

Avez-vous une idée de comment résoudre ce problème svp ? merci

[picodev]

Bonjour,

Bonjour, je suis entrain de coder un programme qui utilise un pivot pour trier des données.

Un quicksort avec selection du meilleur pivot ?

Je vais vous donner un exemple pour que vous comprenez bien.

Imaginons, une liste chainée avec les valeurs suivantes :

C'est juste un exemple ou tu utilises bel et bien des listes chaînées ?

-7 -8 -3 35 2

Pour avoir un pivot optimal, j'ai besoin dans cet exemple, de la valeur qui a 2 valeurs en dessous, et 2 valeurs au dessus. Donc ici -3. Pour trouver cette valeur c'est simple, je parcours x fois ma liste chainée jusqu'a trouver une valeur qui a 2 valeurs en dessous et 2 valeurs au dessus.

Le problème est le suivant :

Imaginons la liste chainée suivante :

-7 -8 35 3 -3

Dans cet exemple, mon pivot est toujours -3. Mais pour le trouver, j'ai dû parcourir toutes la liste chainée. Dans l'exemple, elle est de 5 valeurs. Ce n'est pas grave. Mais si ma liste chaine fais 2000 valeurs voir plus, je me retrouve a attendre trop longtemps pour avoir le résultat de mon pivot.

Avez-vous une idée de comment résoudre ce problème svp ? merci

Tu cherches la médiane. Il y a des algorithmes performants pour ça mais bon avec des listes chaînées c'est moins facile.

[fpasquer]

Bonjour Picodev,

Oui, je souhaite utiliser un QS avec selection du meilleur pivot.

Je n'ai pas le choix d'utiliser des listes chainées. Des valeurs peuvent être rajoutées ou supprimées. Meme pour etre exacte, les listes sont doublement chainées et circulaire.

Je vais regarder ce qu'est "la mediane" et ces algos, je ne connais pas. Merci

Ce qui est sur, c'est que je ne veux pas faire (val_max + val_min)/2

[dinobogan]

Chercher le meilleur pivot possible pour un quicksort annule complètement la performance de ce tri. Tu vas de retrouver avec un tri aussi lent qu'un tri à bulles. Pour plusieurs dizaines de milliers d'entrées, le temps de tri devient catastrophique.

Il m'est arrivé à plusieurs reprises de créer des programmes qui doivent trier plusieurs centaines de millions d'entrées. J'ai réussi a avoir des temps d'exécutions exceptionnels avec un quicksort 3 pivots. J'ai pris arbitrairement la première valeur, la valeur du milieu et la dernière valeur. Je trie ces trois valeurs et elles deviennent mes 3 pivots.
Ensuite je fais un arrêt récursif lorsque le sous-tableau possède moins d'une vingtaine de valeurs et j'utilise un tri par insertion.
Bien sûr, ces informations sont en fonction des valeurs à trier, du processeur, de la machine, des ressources disponibles.... Il n'y a pas de tri universellement efficace.
La recherche d'un bon pivot pour un quicksort est analysé depuis le début de l'invention de ce tri. Tu peux trouver une foultitude de stratégies différentes dans d'innombrables thèses. Dans beaucoup de cas, il s'agit de calculer la médiane d'un certain nombre de valeurs prises plus ou moins au hasard dans le tableau. Pour un quicksort simple pivot, la médiane parmi 5 valeurs prises équitablement sur toute la longueur du tableau donne de très bons résultats. Augmenter le nombre de valeurs augmente aussi le temps de recherche de la médiane et ralentie le temps d'exécution globale dans mon cas, et pour mes jeux de données.

A toi d'expérimenter, mais une chose est sûr et certaine : ne cherche surtout pas le pivot optimal du tableau à trier !

[foetus]

Dans beaucoup de cas, il s'agit de calculer la médiane d'un certain nombre de valeurs prises plus ou moins au hasard dans le tableau.

Je pense qu'avec le tri rapide c'est plus l'algo "Median of Three" qui est utilisé

Stackoverflow - median of three values strategy

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(Python)
# Get the median of three of the array, changing the array as you do.
# arr = Data Structure (List)
# left = Left most index into list to find MOT on.
# right = Right most index into list to find MOT on
 
def MedianOfThree(arr, left, right):
    mid = (left + right)/2
    if arr[right] < arr[left]:
        Swap(arr, left, right)        
    if arr[mid] < arr[left]:
        Swap(arr, mid, left)
    if arr[right] < arr[mid]:
        Swap(arr, right, mid)
    return mid
 
# Generic Swap for manipulating list data.
def Swap(arr, left, right):
    temp = arr[left]
    arr[left] = arr[right]
    arr[right] = temp

[picodev]

@foetus : avec les listes chaînées le po aurait plus d'avantages à utiliser un tri par fusion qu'un quicksort.

[dinobogan]

Je pense qu'avec le tri rapide c'est plus l'algo "Median of Three" qui est utilisé

Tout dépend des tests réels sur des données de production. Une médiane sur 5 éléments peut être encore mieux.

Lorsque je parle du quicksort 3 pivots, je parle d'une partition en 4 zones au lieu de 2 zone dans l'algorithme historique.
En Java, c'est le quicksort 2 pivots qui a été choisi. Le tableau est partitionné en 3 zones.

[picodev]

[...]
Je n'ai pas le choix d'utiliser des listes chainées. Des valeurs peuvent être rajoutées ou supprimées. Meme pour etre exacte, les listes sont doublement chainées et circulaire.

Tu as le choix. Tu peux très bien implémenter ta liste circulaire avec un tableau croissant dynamiquement (realloc) … quand c'est bien fait tu n'as pas de perte de performance due qu relloc et tu gardes un temps d'insertion amorti constant avec l'avantage des tableaux.