Tri à bulle accéléré

[amrani]

Bonsoir,
voici le tri à bulle classique

k->1
répéter
ordre->vrai
pour i->1 à n-k pas->1
si T>T[i+1]
alors tmp->T
T->T[i+1]
T[i+1]->tmp
ordre->vrai
Finsi
Finpour
k->k+1
jusqu'à(ordre=vrai)

j'ai entendu parlé d'un tri bulle accéléré parcourant le tableau dans les deux sens,
voila ce que je propose

k->1
répéter
ordre->vrai
pour i->k à n-k pas->1
pour j->n-k à k pas->-1
si T>T[i+1]
alors tmp->T
T->T[i+1]
T[i+1]->tmp

Finsi
si T[j]<T[j-1]
alors tmp->T[j]
T[j]->T[j-1]
T[j-1]->tmp
ordre->faux
Finpour
k->k+1
jusqu'à(ordre=vrai)

est-ce l'algoritme que j'ai proposé correct? est-il plus rapide que le premier?

[V@J]

Bonsoir,
voici le tri à bulle classique

k->1
répéter
ordre->vrai
pour i->1 à n-k pas->1
si T>T[i+1]
alors tmp->T
T->T[i+1]
T[i+1]->tmp
ordre->faux
Finsi
Finpour
k->k+1
jusqu'à(ordre=vrai)

j'ai entendu parlé d'un tri bulle accéléré parcourant le tableau dans les deux sens,
voila ce que je propose

k->1
répéter
ordre->vrai
pour i->k à n-k pas->1
pour j->n-k à k pas->-1
si T>T[i+1]
alors tmp->T
T->T[i+1]
T[i+1]->tmp
ordre->faux
Finsi
si T[j]<T[j-1]
alors tmp->T[j]
T[j]->T[j-1]
T[j-1]->tmp
ordre->faux
Finpour
k->k+1
jusqu'à(ordre=vrai)

est-ce l'algoritme que j'ai proposé correct? est-il plus rapide que le premier?

En l'état actuel (à part les coquilles, que j'ai soulignées et écrites en rouge) ton algorithme me semble fonctionner.
Cependant, il est clairement non optimal, puisque tu fais au minimum $ (n-1)^2 $ comparaisons (contre au plus $ \frac{(n-1)^2}{2} $) avec la version 1 du tri à bulle.
Par contre, si tu évites de mettre tes deux boucles for (portant sur les variables locales i et j) l'une dans l'autre, la complexité devrait redevenir peu ou prou équivalente à la complexité du premier algorithme. Ça devrait donner quelque chose comme (en reprenant tes notations) :

Code : Tout sélectionner

k->1
répéter
  ordre->vrai
  pour i->k à n-k pas->1
    si T[i]>T[i+1]
    alors
      tmp->T[i]
      T[i]->T[i+1]
      T[i+1]->tmp
      ordre->faux
    Finsi
  Finpour
  pour j->n-k à k pas->-1   
    si T[j]<T[j-1]
    alors
      tmp->T[j]    
      T[j]->T[j-1]
      T[j-1]->tmp
      ordre->faux  
    Finsi                                            
  Finpour
  k->k+1
jusqu'à(ordre=vrai)

[amrani]

je crois que mon algorithme n'est pas rapide, par contre il parait que le quicksort (c'est un tri mais qui n'est pas à bulle) est le plus rapide concernant les tris (ceci reste à vérifier)

[hatonjan]

c'était necessaire de recréer un sujet ? http://forum.prepas.org/viewtopic.php?f ... &sk=t&sd=a créé par tes soins ne suffisait pas ? Et les tri, dans tout les langage du monde, ça se trouve facilement sur google...

[amrani]

je crois qu'il faudrait ajouter un ptit"-1"

pour j->n-k à k-1pas->-1 au lieu de pour j->n-k à kpas->-1

Code : Tout sélectionner

k->1
répéter
  ordre->vrai
  pour i->k à n-k pas->1
    si T[i]>T[i+1]
    alors
      tmp->T[i]
      T[i]->T[i+1]
      T[i+1]->tmp
      ordre->faux
    Finsi
  Finpour
  pour j->n-k à k-1pas->-1 
    si T[j]<T[j-1]
    alors
      tmp->T[j]    
      T[j]->T[j-1]
      T[j-1]->tmp
      ordre->faux  
    Finsi                                            
  Finpour
  k->k+1
jusqu'à(ordre=vrai)

c'était necessaire de recréer un sujet ?

j'avoue que non , mais j'avais oublié d'avoir créer un premier topic

[Dadin]

Une petite précision, Quicksort n'est pas vraiment le "plus rapide" (par exemple, HeapSort à une complexité au pire en $ O(n\,log\,n) $ alors qu'il ne s'agit, pour Quicksort, que de sa complexité en moyenne. Pourtant, chose curieuse, si on implémente ces tris, on se rend compte que le second est souvent, voir très très souvent, plus rapide que le premier pour des raisons d'architecture PC...). Les algos les plus rapides sont en général des mixes entres plusieurs. Par exemple, en général, avant d'appliquer Quicksort, on mélange toute la liste pour éviter le cas où celle-ci est déjà triée.

Enfin, le point le plus important : n'oublions pas de rajouter "TRI PAR COMPARAISON" où l'on démontre effectivement que la complexité de tris comme Quicksort, Heapsort... sont optimaux ... dans le cas de la comparaison. On peut avoir, moyennant des hypothèses supplémentaire sur la liste, des tris beaucoup plus rapides, souvent probabilistes.
Enfin, un autre exemple, si tu as une liste de $ 4000000 $ de nombres de 3 chiffres, tu peux les comparer chiffre à chiffre en ne parcourant que 3 fois la liste... ce qui les trie de façon linéaire.