Come fare un Bubble sort

Bubble sort è uno dei più semplici algoritmi di ordinamento. Si chiama bubble sort perché la lo farà valori ' bolla ' nel tuo elenco verso l'alto ( o in basso a seconda di come si pensa di esso ) . Mentre è una specie facile , non è così efficiente come i tipi più avanzati , e in realtà dovrebbe essere utilizzato solo per scopi di apprendimento ( se non si conosce l'elenco è quasi allineati , nel qual caso non è male ) quello che vi serve
Un computer in grado di compilare un certo linguaggio di programmazione o
carta e matita per passare attraverso l' esempio
Mostra Altre istruzioni
1

Penso che il modo migliore per discutere di bubble sort è con un esempio . Ti darò una panoramica dell'algoritmo , e quindi lavoreremo con un esempio passo- passo per darvi un'idea di come funziona. Quindi, in primo luogo , l'idea.
2

Bubble sort viene utilizzato per ordinare un elenco di elementi in ordine crescente o decrescente . Supponiamo per questo tipo che si desidera inserire l'elenco in ordine (cioè 1,2,3 , ecc ) crescente. L'ordinamento funziona facendo passare su ogni elemento nella lista e confrontandola con l'elemento successivo della lista . Se il primo elemento è maggiore del secondo elemento , i due vengono commutati . Se il primo elemento è minore o uguale al secondo , non succede nulla . Dopo aver guardato questo elemento , l'elemento successivo si vede , e il processo si ripete .
3

Quando il genere ha esaminato ogni elemento , un ' passaggio ' è stato completato. Dopo un passaggio, si sa per certo che un numero deve essere nella posizione corretta . Nel nostro ordine ascendente , il più grande valore volontà ' bubble ' alla fine dell'elenco . Purtroppo , non si sa se il resto della lista è in ordine , in modo da prendere un altro passaggio. Tuttavia, in questo passaggio , è possibile interrompere un elemento prima del termine in quanto si sa che il numero è già nella posizione corretta .
4

Bubble sort ( di solito) richiede diversi passaggi per completare . I più passaggi grazie alla richiesta è uguale al numero di elementi nella lista meno 1 . Quindi, se si hanno 10 elementi in lista , potrebbe prendere 9 passaggi per completare l'ordinamento . Passiamo con un esempio per spiegare meglio
5

Usiamo la seguente lista non ordinata : . 6 , 3 , 1 , 8 , 2 , 4

Vorremmo l'elenco per simile a questa: 1 , 2 , 3 , 4 , 6 , 8

al primo passaggio , ci confrontare i numeri uno alla volta , e sappiamo che dopo un passaggio dovremmo avere il maggior numero di tutta la strada a destra , quindi in questo caso , che sarà 8 . Per il nostro esempio , il segno ^ punterà il posto nella lista che stiamo esaminando .
6

6 , 3 , 1 , 8 , 2 , 4

Passo 1 , Punto 1 ) Confronta il 6 e il 3 . 6 è maggiore di 3 , quindi dovremo scambiare them.3 , ^ 6 , 1 , 8 , 2 , 4

Passo 1 , Passo 2) Confronta il 6 e l' 1 . 6 è maggiore di 1 , quindi dovremo scambiare them.3 , 1 , ^ 6 , 8 , 2 , 4

Passo 1 , punto 3 ) Confrontare il 6 e l' 8 . 6 è inferiore o uguale a 8 , quindi nulla happens.3 , 1 , 6 , 8 ^ , 2 , 4

Passo 1 , Passo 4 ) Confronta l' 8 e il 2 . 8 è maggiore di 2 , in modo da scambiare them.3 , 1 , 6 , 2 , ^ 8 , 4

Passo 1 , punto 5 ) Confronta l' 8 e il 4 . 8 è maggiore di 4 , in modo da scambiare them.3 , 1 , 6 , 2 , 4, 8

ed ecco fatto il primo passo !
7

3 , 1 , 6 , 2 , 4 , 8 è certo un elenco ordinato , ma si può vedere , come promesso , l' 8 è il fine . Io ora scrivo che cosa la lista si presenta come dopo ogni passaggio. Provate voi stessi , e vedere se il vostro incontri miniera : Passo 2 : 1 , 3 , 2 , 4 , 6, 8 ( guardando meglio ) Passo 3 : 1 , 2 , 3 , 4 , 6, 8 ( fatto ) Passo 4 : 1 , 2 , 3 , 4 , 6, 8 ( umm ... non eravamo già fatto ? ) Passo 5 : ( ! ancora fatto) 1 , 2 , 3 , 4 , 6 , 8
8

Come si può vedere , la lista è stata ordinata dopo 3 passaggi, ma il bubble sort continuato ad andare . Perché è così? Beh , l'algoritmo di base bubble sort è abbastanza stupida . Si vuole fare in modo che funzioni nel caso peggiore ( che è un elenco che è completamente all'indietro come 9 , 8 , 7 , 6 , 5) . È possibile aggiungere una velocità fino a rendere il vostro bubble sort correre un po 'più veloce . Ad ogni passaggio , una bandiera che viene impostata su true solo se effettivamente passate due numeri . Prima di fare il passo successivo , verificare se la bandiera è vera o falsa . Se è vero , è scambiato due numeri , e si deve fare un altro passaggio. Se è falso , l'elenco è ordinato , e si può fare. Nel nostro esempio , anche se la lista è stata ordinata dopo 3 passaggi , ci sarebbe ancora bisogno di fare un 4 ° passaggio perché abbiamo fatto uno swap nel 3 ° passaggio .
9

Ora sapete come fare un bubble sort . Lasciare commenti con tutte le domande che potreste avere. Grazie per la lettura !

• Programmazione di base Aiuto 
• Come imparare Prolog