Je recherche des algorithmes de tri sur calto en c en ASM ou en basic avec les différentes méthodes de tri (par bulle ...)
C pour trier des chiffres au fait
Merci d'avance
), sinon je ne sais pas, enfin à bulles c'est tellement pourri comme algorithme que ça m'étonnerait qu'on le trouve...
#include <stdlib.h>
// Do not use register a5; callback function might need it.
register long __tbl asm ("a5");
__ATTR_LIB_C__ void qsort(void *list, short num_items, short size, compare_t cmp_func)
{
unsigned short gap,byte_gap,i,j;
char *p,*a,*b,temp;
for (gap=((unsigned short)num_items)>>1; gap>0; gap>>=1) // Yes, this is not a quicksort,
{ // but works fast enough...
byte_gap=gap*(unsigned short)size;
for(i=byte_gap; i<((unsigned short)num_items)*(unsigned short)size; i+=size)
for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap)
{
a=p; b=p+byte_gap;
if(cmp_func(a,b)<=0) break;
for(j=size;j;j--)
temp=*a, *a++=*b, *b++=temp;
}
}
})
Le tri-fusion n'est pas in-place
Kevin Kofler :
Le tri fusion n'est pas in-place (enfin, on peut le faire in-place, mais en O(n²)...), donc inutilisable pour qsort. Et le tri par tas, bien qu'optimal asymptotiquement dans le pire des cas, est trop lent dans le cas moyen, et aussi trop gros pour TIGCCLIB. Le tri rapide est aussi trop gros pour TIGCCLIB.
void swap(int t[], int m, int n)
{
int temp = t[m];
t[m] = t[n];
t[n] = temp;
}
int partition(int m, int n, int t[])
{
int v = t[m];
int i = m-1;
int j = n+1;
while (42)
{
do
{
j--;
} while (t[j] > v);
do
{
i++;
} while (t[i] < v);
if (i<j)
swap(t, i, j);
else
return j;
}
}
void quicksort(int m, int n, int t[])
{
if (m<n)
{
int p = partition(m,n,t);
quicksort(m,p,t);
quicksort(p+1,n,t);
}
}
Pollux
:Le tris quicksort est en O(n²) dans le cas moyen :/Pas vraiment, non. C'est juste dans le pire des cas.
Moumou
: Oui mais, selon Levin et Kolmogorov, le cas moyen est malheureusement le pire cas. (ie dans la vie courante, pour des données courantes, et non pas des données totalement aléatoires comme dans un exercice formel)
Comment est-ce qu'on peut formaliser qqch de ce style?
Sally :
Euh tu veux les programmer ou tu veux qu'ils soient déjà programmés ?
y en a au moins un dans tigcclib mais je crains que ce ne soit le quicksort (), sinon je ne sais pas, enfin à bulles c'est tellement pourri comme algorithme que ça m'étonnerait qu'on le trouve... Le meilleur algorithme c'est le tri-fusion, c'est pas très dur à faire...
Moumou
: La probabilité d'apparition d'une séquence s (en binaire) est en 1/2^n(s). Avec n la taille du plus petit programme (ou du plus petit ruban d'une machine de Türing, si tu préfère un résultat très formalisé) permettant d'obtenir la séquence s en output. Ou encore, plus une séquence est "facile à décrire", plus elle est probable.
liquid
: quicksort, c le tri rapide ? selon les donnees que tu as a trier et le nbre d'elements, il est plus efficace que le tri fusion (O(nlog(n) contre O(n²) (d'apres mes souvenirs hein))