-->
  • Home
    • WorldInformatic's history
  • Operative Systems
    • Mac
    • Windows
  • Some guide
  • Programming language
    • C
    • Java
    • HTML
  • Smartphone
    • Apple iOS
    • Android
  • Games
    • Smartphone Games
    • Web Games
    • PC e Console
  • News
    • Apple News
    • Android/Google News
  • Enjoy!
  • Contact us

C: corso completo

- Parte 01: Introduzione
- Parte 02: Fasi, variabili, operatori e software
- Parte 03: Tipi di dato, direttive e primo programma
- Parte 04: Tipi di formato, printf e scanf
- Parte 05: Istruzioni condizionali e di iterazione
- Parte 06: Funzioni e progetti su più file
- Parte 07: Puntatori e passaggio dei parametri
- Parte 08: Array, stringhe e strutture
- Parte 09: Gestione file: file di testo
- Parte 10: Gestione file: file binari
- Parte 11: Allocazione dinamica della memoria
- Parte 12: Creare ed utilizzare le liste nel C
- Parte 13: Algoritmi di ordinamento di array e strutture
- Parte 14: Esercizi sul linguaggio C

C: corso completo

27 febbraio 2013

Immagine
Ciao 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:
  • Naive sort: molto semplice, ma poco efficiente;
  • Bubble sort: la più usata, perché abbastanza semplice e abbastanza efficiente;
  • Insert sort: non facilissima, ma più efficiente della bubble sort;
  • Merge sort: di difficile comprensione, ma molto efficiente;
  • Quick sort: di difficile comprensione, ma la più efficiente.

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);
Immagine
void swap(Element *e1, Element *e2);
Immagine
int compare(Element e1, Element e2);
Immagine
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:
  • Ad ogni ciclo confronta gli elementi a due a due, eventualmente scambiandoli se non sono nell'ordine che si desidera;
  • In sostanza, ad ogni iterazione quindi l'elemento più grande si trova sempre in fondo alla parte di array considerata.

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:
  • Spezza l'array in due parti di uguale dimensione;
  • Ordina queste due parti separatamente, procedendo per ricorsione;
  • Infine fonde insieme i due sub-array in modo da ottenerne uno unico ordinato.
Immagine
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ì:
  1. Si determina un pivot (ad esempio pivot = a[dim-1]);
  2. Si scandisce il vettore dato mediante due indici: i, che parte da 0 e procede in avanti, e j, che parte da dim-1 e procede all'indietro;
  3. Poi procede ad una scansione in avanti: ogni elemento a[i] viene confrontato con il pivot; se a[i] > pivot, la scansione in avanti si ferma;
  4. Se la scansione in avanti si ferma, si procede a quella indietro: ogni elemento a[j] viene confrontato con il pivot; se a[j] < pivot, la scansione in indietro si ferma e l’elemento a[j] viene scambiato con a[i];
  5. Poi si riprende con la scansione avanti, indietro, ... Il tutto si ferma quando i == j. A questo punto si scambia a[i] con il pivot;
  6. Alla fine della scansione il pivot è collocato nella sua posizione definitiva;
  7. L’algoritmo è ricorsivo: si richiama su ciascun sotto-array fino a quando non si ottengono sotto- array con un solo elemento;
  8. A questo punto il vettore iniziale risulta ordinato!


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:
ordinamento.zip
File Size: 4 kb
File Type: zip
Download File

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

Tweet
    Condividi



comments powered by Disqus

Social
Aiutate a diffondere il sito, cliccando qui




Segui @WInformatic

Autore
Salve a tutti!
Mi chiamo Pumo Matteo.
Per saperne di più: Biografia


Categorie
  • -> Mac
  • -> Windows
  • -> Apple iOS
  • -> Android
  • -> Programmazione
  • -> Guide varie
  • -> Hardware
  • -> Games
  • -> News



Social Network

Follow us on Social Network:

Topics

Windows
Smartphone games

If you want, make a donation

TO CONTACT US, USING THE PAGE IN THE TOP

Author

Immagine
I'm Matteo Pumo. University of Bologna - Faculty of computer Engeneering.
- My Biography

Italian version of site


Site made by Pumo Matteo © Copyright 2013 - Bologna, Italy - All rights reserved - It's prohibit all reproduction form, partial or total, of materials.