ordinamento per scambio a bolle in C

[burohkr]

devo fare una relazione su questo algoritmo ma non sò di che parlare a parte il suo funzionamento......potete aiutarmi a trovare del materiale utile per metterlo nella relazione?

[recoil]

scambio di bolle
ma è il caro vecchio bubble sort per caso?

[burohkr]

esattamente. Se puoi consigliarmi qualche documentazione, ma se ne hai molta riguardo shakesort o ordinamento per selezione ti prego di darmela, ho poco tempo e non sono una vetta!!!!

[bsummer]

Mah...il bubble è un algoritmo di ordinamento molto semplice, c'è poco da dire...se non che ha un ordine di complessità quadratico e che quindi è completamente inadatto per ordinamenti che non siano piccoli, molto piccoli.

Aloha!

[cionci]

www.google.it !!!!

http://www.nist.gov/dads/HTML/sort.html
http://www-ee.eng.hawaii.edu/Courses...hapter2.1.html
http://www.cosc.canterbury.ac.nz/peo.../appldsal.html

Un po' di iniziativa personale non guasta mai !!!

[burohkr]

l' insersion sort è più performante del bubble?

[recoil]

Originariamente inviato da burohkr
l' insersion sort è più performante del bubble?

direi di si ma c'è cmq di meglio, basti pensare al merge sort, quick sort...

[bsummer]

...ma il più figo di tutti è sempre e solo lui...il bucket sort!!!!

L'unico ed il solo che ha complessità lineare!!!

Peccato solo che le sua applicabilità sia mooolto limitata

[mjordan]

Originariamente inviato da burohkr
devo fare una relazione su questo algoritmo ma non sò di che parlare a parte il suo funzionamento......potete aiutarmi a trovare del materiale utile per metterlo nella relazione?

Scambio a bolle...A sentirlo così faresti rigirare qualche vecchio informatico nella tomba ... Pensa che quando ho aperto il thread per leggerlo pensavo si parlasse di roba di fatture ...

[verloc]

Vai qua :è in italiano e ti da un supporto grafico per comprendere gli algoritmi di ordinamento.

http://digilander.libero.it/unno2/sort/index.htm

[TriacJr]

Originariamente inviato da bsummer
...ma il più figo di tutti è sempre e solo lui...il bucket sort!!!!

L'unico ed il solo che ha complessità lineare!!!

Ma che algoritmo è?!

A complessità lineare?

Ciao.

[bsummer]

Originariamente inviato da TriacJr
Ma che algoritmo è?!

A complessità lineare?

Ciao.

Ciao.

Immagina di avere un vettore di lunghezza infinita. Ogni elemento del vettore a sua volta è una lista di lunghezza indefinita (all'inizio vuota).

Ogni volta che devi ordinare un numero n (intero) lo inserisci in testa alla lista che si trova all' n-esima posizione del vettore.

Il vettore finale ordinato è dato dalla concatenazione di tutte le liste contenute nel vettore.

In soldoni:

per ogni numero n da ordinare
- prendi n
- aggiungi in testa alla lista contenuta in vettore[n]

Alla fine : concatena tutte le liste partendo da quella di indice minore (le liste vuote non si prendono).

Il risultato sarà il vettore ordinato.

Se consideriamo n passaggi per inserire gli n numeri e quindi n per concatenare le liste non vuote il risultato sarà 2*n, al contrario del bubblesort che compie n*(n-1) passi o l'heapsort ed il quick sort che ne fanno n*ln(n).

Naturalmente non è possibile applicarlo sempre, ma nel caso in cui si conosca a priori qual'è l'intero massimo che può essere presente e se questo non ha un valore troppo grande, si può fare (ad es: se al max esce 5000, un vettore di 5000 elementi è facilmente allocabile)

Aloha!

[TriacJr]

Originariamente inviato da bsummer
Ciao.

Immagina di avere un vettore di lunghezza infinita. Ogni elemento del vettore a sua volta è una lista di lunghezza indefinita (all'inizio vuota).

Ogni volta che devi ordinare un numero n (intero) lo inserisci in testa alla lista che si trova all' n-esima posizione del vettore.

Il vettore finale ordinato è dato dalla concatenazione di tutte le liste contenute nel vettore.

In soldoni:

per ogni numero n da ordinare
- prendi n
- aggiungi in testa alla lista contenuta in vettore[n]

Alla fine : concatena tutte le liste partendo da quella di indice minore (le liste vuote non si prendono).

Il risultato sarà il vettore ordinato.

Se consideriamo n passaggi per inserire gli n numeri e quindi n per concatenare le liste non vuote il risultato sarà 2*n, al contrario del bubblesort che compie n*(n-1) passi o l'heapsort ed il quick sort che ne fanno n*ln(n).

Naturalmente non è possibile applicarlo sempre, ma nel caso in cui si conosca a priori qual'è l'intero massimo che può essere presente e se questo non ha un valore troppo grande, si può fare (ad es: se al max esce 5000, un vettore di 5000 elementi è facilmente allocabile)

Aloha!

Ah, ok. Capito.

Grazie e ciao.