Algo

différences tri à bulle et par permutation

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : différences tri à bulle et par permutation

Nethacker

rule televisions, rule minds

Bonsoir,
je me demande est ce qu'il y'a une différence entre le tri à bulle et celui par permutation,
pour moi c'est pratiquement le même principe, j'ai un truc à faire, et on me demande de faire et le tri à bulle et par permutation.
en gros on compare i et i+1 et on permute s'ils ne sont pas dans le bon ordre, et on refait si y'a eu une permutation pendant le dernier balayage.
Vous en connaissez des différences vous ?

Merci d'avance

Publicité

Joel F

Real men use unique_ptr

http://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles

Permutation ej connais pas, c'ets pas plutot insertion ou fusion ?

http://fr.wikipedia.org/wiki/Algorithme_de_tri

rufo

Pas me confondre avec Lycos!

Même remarque que Joel F : ça me dit rien le tri par permutation. En cherchant sur google j'ai trouvé ça entre autre : http://www.mat.ulaval.ca/uploads/m [...] xes_01.pdf

Ca me fait quand même bien penser au tri à bulles.

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta

Nethacker

rule televisions, rule minds

Insertion et fusion sont aussi cités, comme des tris à part à faire, merci en tout cas

Nethacker

rule televisions, rule minds

Bonsoir,
J'ai trouvé cela : comme étant un tri par permutation !

'principe :

'On parcourt le tableau jusqu'à ce que l'on trouve un élément plus petit

'que le précedent donc mal placé.

'On prend cet élément et on le range à sa place dans le tableau puis on

'continue la lecture.

'On s'arrête à la fin du tableau.

Dim i, j, k As Integer

Dim permute As Integer

For i = 0 To UBound(tabl) - 1

If tabl(i + 1) < tabl(i) Then

permute = tabl(i + 1)

j = 0

Do While (j < i) And (tabl(j) < tabl(i + 1))

j = j + 1

Loop

For k = i + 1 To j + 1 Step -1

tabl(k) = tabl(k - 1)

Next

tabl(j) = permute

End If

Affichetour(tabl, i + 1)

Que j'ai traduit humblement par :

Code :

/* tri par permutation */
void permutation(int *t, int dimension)
{
int i,j,k,permute;
for (i = 0; i < (dimension-1); i++)
{
if(*(t+i+1) < *(t+i))
{
permute = *(t+i+1);
j = 0;
while( (j<i) && (*(t+j)< *(t+i+1)) ) j++;
for(k=i+1; k < j+1; k--)
*(t+k) = *(t+k-1);
*(t+j) = permute;
}
}
}

Mais le tableau n'est pas trié, des idées ? peut être que c'est mal traduit ?
Merci d'avance !

rufo

Pas me confondre avec Lycos!

bizarre, ça ressemble au tri par insertion, ça,non?

Nethacker

rule televisions, rule minds

Tout le monde le dit ...

Edit :
J'ai trouvé ça yoopi ! je vais essayer de traduire en C et voir si ça marche,
en fait ça parcourt le tableau avec pair et impair ...

Citation :

Swap Sort

Swap sort is similar to bubble sort, although the first time through the list the first and second elements are compared (and swapped if necessary), then the 3rd and 4th elements are compared, etc. The second time through the list the first element is skipped and the second and third elements are compared, then the 4th and 5th, and so on...

Swap Sort

Given a list of elements L = ( e1 e2 ... en ) with length n.

Do n/2 times:
For each element ei where i is odd:
If ei > ei+1 Then swap ei with ei+1

For each element ei where i is even:
If ei > ei+1 Then swap ei with ei+1

The list is now sorted.

This sorting algorithm is less intuitive than the bubble sort (it's not as obvious why after completion the list will be sorted).

Message édité par Nethacker le 08-06-2009 à 23:04:03

Nethacker

rule televisions, rule minds

Mais ce n'était pas ça, pour toute personne égarée je suis finalement tombé sur celui là !

http://www.javafr.com/forum/sujet- [...] 65307.aspx

Bonne chance !

Message cité 1 fois

Corebreaker

Nethacker a écrit :

http://www.javafr.com/forum/sujet- [...] 65307.aspx

Bah ça c'est un tri insertion (O(n²)).

Mais moins performant que celui où on parcours le tableau et à chaque élément d'index I, on utilise un algorithme dichotomique pour placer l'élément courant (d'index I) à la bonne place (d'index J) dans la partie triée (indexes de 0 à (I-1)), placement effectué par une permutation circulaire entre les indexes J et I (O(n log(n))).

Message édité par Corebreaker le 11-06-2009 à 20:33:52

FORUM HardWare.fr

Programmation

Algo

différences tri à bulle et par permutation

Sujets relatifs
Différences entre gawk et les autres awk	permutation
création d'une info bulle	Listing des différences avec le C++
Différences de perfs entre foreach et array_map	[resolu]différences entre deux fichiers
Différences à la compilation	compter le nombre de différences de deux fichiers (diff...)
algorithme de permutation et rotation cyclik	Algorithme permutation
Plus de sujets relatifs à : différences tri à bulle et par permutation

Page générée en 0.065 secondes