Les tri de tableaux

[Rockleader]

J'aimerais quelques infos sur la méthode de tri rapide aussi appelé tri par pivot. J'ai un algo là dessus à faire, mais je n'ai pas trouvé de lien sur internet m'expliquant clairement la méthode.


S'agit il de prendre arbitrairement une valeur que l'on dis être le pivot, puis de placer toutes les valeurs inférieur dans un sous tableau et de réitérer pour les valeurs supérieure ?
On obtient ainsi un tableau avec des élément < pivot et un autre avec des éléments > pivot.
Est ce que la méthode s'arrête là ou bien elle continue jusqu'à ce que la totalité des éléments soit dans l'ordre désiré ?

Ex si 5 est un pivot

On aurait une liste

5; 10;4;2;7

Ce qui nous donnerait

4;2;5;10;7 la méthode s'arrête ici, ou bien va t'elle jusqu'à 2;4;5;7;10.

Je parle bien d'une méthode en particulier et non d'autre chose.

[fatal_error]

hello
wikipedia quick sort

[Rockleader]

hello
wikipedia quick sort

"La méthode consiste à placer un élément du tableau (appelé pivot) à sa place définitive, en permutant tous les éléments de telle sorte que tous ceux qui sont inférieurs au pivot soient à sa gauche et que tous ceux qui sont supérieurs au pivot soient à sa droite."

c'est bien l'article que j'ai lu. Et d'après ce dernier on s'arrête lorsque le pivot est au milieu.
soit 4;2;5;10;7 sur mon exemple.
L'exemple de wiki s'arrête là.

Mais l'article en lui même suggère qu'il faut aller plus loin si je ne me trompe pas.

"Cette opération s'appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Ce processus est répété récursivement, jusqu'à ce que l'ensemble des éléments soit trié."


On trierait donc en totalité ? Mais ce n'est pas ce qui est montré par l'exemple...

[fatal_error]

essaies en anglais

The steps are:

Pick an element, called a pivot, from the list.
Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

"Cette opération s'appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Ce processus est répété récursivement, jusqu'à ce que l'ensemble des éléments soit trié."

ca parait explicite.

qu'est-ce que tu comprends pas dans l'énoncé?
illustres avec une liste en appliquant l'algo jusqu'à là ou tu piges po

[Rockleader]

Ben je comprends à peu près l'algo, mais là il se fait sur un seul tableau si je ne me trompe pas.

Moi on me demande de faire ça en utilisant 3 tableaux.

J'ai un tableau avec les val <= pivot et un avec les val > pivot

Ensuite je peux remonter et trier sans soucis, mais au final j'aurais pour ainsi dire deux sous tableau trier et non le tableau principal. C'est ce que sous entend de faire mon énoncé. Hors la méthode du pivot se pratique dans un seul tableau à ce que je vois.

[fatal_error]

Code: Tout sélectionner

[1 6 8 4 9 7]
Choisir un pivot (au pif)
1 6 8 4 9 7
    ^
placer les nombres comme il faut
1 6 4 7 8 9
        ^
Réappliquer sur les deux parties du tableau...: [1 6 4 7 ] et [9]
Première partie :
  [1 6 4 7]
  Choisir un pivot
  1 6 4 7
      ^
  Placer les nombres comme il faut   
  1 4 7 6
    ^
 
  Réappliquer sur les deux parties du tableau...: [1] et [7 6]
  Première partie :
    [1]
    Rien à placer

  Deuxième partie
    [7 6]
    Choisir un pivot
    7 6
    ^
    Placer les nombres
    6 7
      ^
    Réappliquer sur les deux parties du tableau...:[] et [7]
    Première partie :
    []
    Rien à faire
   
    Deuxième partie :
    [7]
    Rien à faire
   
    Bilan :
    [6 7]
   
  Bilan :
  [1 4 6 7]
 
Deuxième partie :
  [9]
  Rien à faire
Bilan :
[1 4 6 7 8 9] 


[Rockleader]

Merci,

j'ai bien compris comment fonctionnait l'algorithme.

On définit un nouveau pivot à chaque fois jusqu'à ce que chaque sous tableaux soit trié. Donc si au départ on avait n nombre dans le tableau, l’algorithme s'arrêteraient lorsque l'on aurait en fait n tableaux de un élément chacun.

Bref sur papier c'est assez facile à faire une fois le principe compris.

Je bloque encore au niveau du code.

J'ai défini un pivot et découpé en deux premiers sous tableaux. Mais je n'arrive pas à voir comment continuer, ou plutot comment va se faire la récurrence au niveau codage pour définir à chaque fois un nouveau pivot et pouvoir redécouper les tableaux.




EDIT: Je pense avoir peut être trouvé une solution en parcourant le tableau simultanément dans les deux sens, en gros en comparant la première valeur du tableau avec la dernière. Je testerais demain.

[fatal_error]

très bonne initiative de tester ton idée.:++:

sinon, l'algorithme que je t'ai proposé se translate assez facilement en récursif:

Code: Tout sélectionner

//arraySize is the size of arrayToSort
//returns a pivot eligible in arrayToSort
int getPivot(Tab arrayToSort, int arraySize){
  return arraySize/2;
}
Tab substractLeftArray(Tab arrayToSort, int arraySize, int pivotIndex){
  return arrayToSize(0...pivotIndex-1)
}
Tab quickSort(Arr arrayToSort, int arraySize){
  //add special cases such as array size==1
  //return arrayToSort

  int pivotIndex = getPivot(arrayToSort, arraySize);
  Tab leftArray = substractLeftArray(arrayToSort, arraySize, pivotIndex)
  Tab rightArray = substractRightArray(arrayToSort, arraySize, pivotIndex)
 
  Tab sortedLeftArray = quickSort(leftArray, pivotIndex)  //aux indices pres
  Tab sortedLeftArray = quickSort(rightArray, arraySize - pivotIndex)
  currentPivotElem = arrayToSort[pivotIndex];
  Arr sortedArray = concatenate(sortedLeftArray, currentPivotElem, sortedRightArray)
  return sortedArray;
}


A la syntaxe exotique..
j'ai également omis la partie placer les nombres inférieurs au pivot d'un coté ou de l'autre mais faut bien que tu transpires un peu!

[Rockleader]

Bon, pour mon idée, elle ne fonctionne pas, ou devrais je dire elle fonctionne seulement dans certains cas particulier, donc pas bon :cry:


Pour ton code, j'ai un peu de mal à le comprendre n'étudiant pas ce langage, même si je décrypte un peu x)


Je vais essayer de réaliser une sous procédure QuickSort qui d'un tableau donnée en entrer en retourne deux, un plus petit au pivot et l'autre plus grand.
Et je devrais la faire récursivement. Mais sans tester je parle dans le vide; et là je ne peux pas tester j'ai cours :)

[Rockleader]

J'ai testé mon programme, et j'ai un truc qui déconne à l'exécution, j'arrive pas du tout à voir pourquoi...




Le code:

Code: Tout sélectionner

procedure partitionSelonPivot is
nb_max: constant Integer := 50;

subtype Intervalle is integer range 1..nb_max ;
type TabEntier is array (Intervalle) of Integer;


  procedure getTab (tabAsk:out TabEntier; valEff:in Integer) is
  valeur:Integer;
    begin
      for k in 1..valEff loop
   put("Valeur ");put(k,2);put(": ");
   get(valeur);
   tabAsk(k):=valeur;
      end loop;
    end getTab;

    procedure putTab(tabEntre : in tabEntier; nb_val:in Integer) is
      begin
   for k in 1..nb_val loop
     put(tabEntre(k));
   end loop;
      end putTab;

    procedure QuickSort(tabEntre: in out tabEntier;indicePivot:In Integer) is
   tempo:Integer;
   begin
      for k in 1..tabEntre'last loop
         if tabEntre(indicePivot) >= tabEntre(k) then
        tempo:= tabEntre(k);   
             tabEntre(k):=tabEntre(indicePivot);
             tabEntre(indicePivot):=tempo;
         end if;
      end loop;
   end QuickSort;
   
   
tab1: TabEntier;
valEff:Integer;

  begin

    put("Combien de valeur dans le tableau ");
    get(valEff);
    getTab(tab1,valEff);
    new_line;
    for k in 1..tab1'last loop
      QuickSort(tab1,k);
      putTab(tab1,valEff);new_line; -- trace
   end loop;
   putTab(tab1,valEff); -- trace

end partitionSelonPivot;


ET voici ce que j'obtiens à l'exécution:

Code: Tout sélectionner

Combien de valeur dans le tableau 4
Valeur  1: 5
Valeur  2: 3
Valeur  3: 7
Valeur  4: 2

-1248694356          5          7          3
          5-1248694356          7          3
          7          5-1248694356          3
          7          5          3-1248694356
          7          5          3          2
          7          5          3          2
 1967335744          7          5          3
 1967335744   38272576          7          5
 1967335744 1966711874   38272576          7
 1967335744 1967325944 1966711874   38272576
 1967335744 1967325944 1966711874   38272588
 1967335744 1967325944 1966732101 1966711874
 1967335744 1967325944 1966732101 1966711874
 1967335744 1967325944 1966732101 1966711874
 1967335744 1967325944 1967165425 1966732101
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967325944 1967165425
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944
 1967335744 1967335744 1967335744 1967325944


De toute évidence, dès le début il y a des opération qui se font avec l'adresse d'une variable et non la variable elle même, et je vois pas du tout pourquoi....

Si vous arrivez à trouver l'insecte qui me fait planter tout ça =)



EDIT:


J'ai en partie trouvé ce qui coinçait au niveau de la boucle. Mais j'ai toujours un soucis que je n'arrive pas à régler au niveau d'une valeur. Malgré cela l'algorithme tourne plutot bien.

Code: Tout sélectionner

Combien de valeur dans le tableau 4
Valeur  1: 2
Valeur  2: 7
Valeur  3: 1
Valeur  4: 9

    -139264          7          2          9
          7    -139264          2          9
          7          2    -139264          9
          9          7          2    -139264
          9          7          2    -139264


Comme vous le voyez le tri se fait bien dans l'ordre décroissant, mais j'ai une variable fausse et je ne vois pas pourquoi...

Voilà la sous procédure

Code: Tout sélectionner

procedure QuickSort(tabEntre: in out tabEntier;indicePivot:In Integer) is
   tempo:Integer;
   begin
      for k in 1..tabEntre'last loop
         if tabEntre(indicePivot) >= tabEntre(k) then
        tempo:= tabEntre(k);   
             tabEntre(k):=tabEntre(indicePivot);
             tabEntre(indicePivot):=tempo;
         end if;
      end loop;
   end QuickSort;

ET voilà son utilisation dans le programme principal

Code: Tout sélectionner

put("Combien de valeur dans le tableau ");
    get(valEff);
    getTab(tab1,valEff);
    new_line;
   for k in 1..valEff loop
      QuickSort(tab1,k);
      putTab(tab1,valEff);new_line; -- trace pour debugguer
   end loop;
   putTab(tab1,valEff); -- affichage final