burohkr
22-08-2003, 17:13
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?
View Full Version : ordinamento per scambio a bolle in C
recoil
22-08-2003, 17:41
scambio di bolle :eek:
ma è il caro vecchio bubble sort per caso?
ma è il caro vecchio bubble sort per caso?
burohkr
22-08-2003, 17:54
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
22-08-2003, 18:48
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!
Aloha!
cionci
22-08-2003, 18:55
www.google.it !!!!
http://www.nist.gov/dads/HTML/sort.html
http://www-ee.eng.hawaii.edu/Courses/EE150/Book/chap10/chapter2.1.html
http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/appldsal.html
Un po' di iniziativa personale non guasta mai !!! ;)
http://www.nist.gov/dads/HTML/sort.html
http://www-ee.eng.hawaii.edu/Courses/EE150/Book/chap10/chapter2.1.html
http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/appldsal.html
Un po' di iniziativa personale non guasta mai !!! ;)
burohkr
22-08-2003, 19:57
l' insersion sort è più performante del bubble?
recoil
22-08-2003, 20:11
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...
l' insersion sort è più performante del bubble?
direi di si ma c'è cmq di meglio, basti pensare al merge sort, quick sort...
bsummer
22-08-2003, 20:34
...ma il più figo di tutti è sempre e solo lui...il bucket sort!!!!
L'unico ed il solo che ha complessità lineare!!! :eek:
Peccato solo che le sua applicabilità sia mooolto limitata :(
L'unico ed il solo che ha complessità lineare!!! :eek:
Peccato solo che le sua applicabilità sia mooolto limitata :(
mjordan
24-08-2003, 23:57
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 ... :D
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 ... :D
verloc
25-08-2003, 08:26
Vai qua :è in italiano e ti da un supporto grafico per comprendere gli algoritmi di ordinamento.
http://digilander.libero.it/unno2/sort/index.htm
http://digilander.libero.it/unno2/sort/index.htm
TriacJr
06-09-2003, 13:25
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!!! :eek:
Ma che algoritmo è?! :confused:
A complessità lineare?
Ciao. :)
...ma il più figo di tutti è sempre e solo lui...il bucket sort!!!!
L'unico ed il solo che ha complessità lineare!!! :eek:
Ma che algoritmo è?! :confused:
A complessità lineare?
Ciao. :)
bsummer
06-09-2003, 14:04
Originariamente inviato da TriacJr
Ma che algoritmo è?! :confused:
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!
Ma che algoritmo è?! :confused:
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
06-09-2003, 15:41
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. :)
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. :)
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.