27 febbraio 2013Ciao ragazzi, in questa tredicesima parte del corso completo di C tenuto su questo sito, voglio parlarvi degli algoritmi di ordinamento, molto utili in qualsiasi programma. I principali algoritmi di ordinamento sono:
Esaminiamole ora insieme una alla volta molto rapidamente, poichè vi do poi la possibilità di scaricarle tutte insieme raccolte in un unico file; prima però bisogna definire altre tre funzioni, utili ai fini dell'ordinamento: void assign(Element *lvalue, Element rvalue); void swap(Element *e1, Element *e2); int compare(Element e1, Element e2); Naive sort
La Naive sort è l'algoritmo di ordinamento più facile; in sostanza prima assume come massimo il primo elemento di un array (o struttura, o lista), poi si scandisce l'array e, se si trova un elemento maggiore del max attuale, lo si assume come nuovo massimo, memorizzandone a questo punto la posizione. Bubble sort La Bubble sort è l'algoritmo di ordinamento più usato in assoluto, e secondo me è quello migliore e più intuitivo da usare; la Bubble sort opera per "passate successive" sull'array:
Insert sort Solitamente per ordinare un array "basta" costruirne uno nuovo ordinato con gli stessi elementi; invece con la Insert sort non è assolutamente necessario costruire un secondo array, in quanto le operazioni per ordinare un array possono essere svolte direttamente infatti sull'array originale. Merge sort La Merge sort produce sempre due sub-array di uguale grandezza; in sostanza:
Quick sort
Come la Merge sort, la Quick sort suddivide il vettore in due sotto-array, delimitati da un elemento "sentinella" (un pivot); il pivot viene poi spostato ricorsivamente in modo da raggiungere l'obiettivo, che e' quello di avere nel primo sotto-array solo elementi minori o uguali al pivot, e nel secondo sotto-array solo elementi maggiori. Quindi procede così:
A questo punto vi metto a disposizione qui da scaricare tutti gli algoritmi di ordinamento, adatti per ogni sorta di struttura: array, struct, liste; basterà infatti solamente cambiare le operazioni "swap, compare e assign" e la definizione di Element per adattarle: ![]()
Questa è l'ultima parte di questo corso; vi ricordo che se volete esercitarvi su parecchi esercizi dovete andare all'ultima parte: Esercizi sul linguaggio C.
Pumo Ciao a tutti, Pumo Matteo |
Social Aiutate a diffondere il sito, cliccando qui Segui @WInformatic Autore Salve a tutti! Mi chiamo Pumo Matteo. Per saperne di più: Biografia Categorie
|