Algoritmi di Ordinamento in linguaggio C: Appunti universitari con esempi molto ultili sui seguenti argomenti: algoritmi di Ordinamento Interni, algoritmi di Ordinamento Evoluti: algoritmo di Ordinamento QuickSort, (11 pagine formato doc)

VOTO: 5 Appunto inviato da giov8

L'ordinamento di una sequenza di informazioni consiste nel disporre le stesse informazioni in modo da rispettare una qualche relazione d'ordine di tipo lineare. Ad esempio una relazione d'ordine "minore o uguale" di tipo lineare, dispone le informazioni in modo "non descrescente". L'ordinamento risulta molto importante in quanto permette di ridurre notevolmente i tempi di ricerca di una informazione nell'ambito di una sequenza di informazioni. Nel caso in cui tale sequenza risulta ordinata secondo una qualche relazione d'ordine, possibile sfruttare la stessa relazione d'ordine per effettuare la ricerca. Ad esempio sia data una sequenza di informazioni ordinata secondo una relazione d'ordine del tipo "minore o uguale". L'algoritmo di ricerca procede scandendo la sequenza di elementi, fino a quando o individua l'elemento cercato o trova una informazione maggiore di quella cercata. In tal caso la ricerca deve essere interrotta in quanto la relazione d'ordine adottata assicura che gli elementi successivi sono senz'altro superiori a quello cercato. In genere le informazioni che compongono la sequenza e che devono essere ordinate risultano piuttosto complesse. Ad esempio, si pensi ad un vettore di elementi di tipo struct, dove ciascuno struct sia composto da differenti campi. In tal caso l'ordinamento viene applicato ad un numero finito di attributi di ciascuna informazione. Tali attributi sono dette chiavi.Sempre con riferimento all'esempio del vettore di struct, l'ordinamento potrebbe essere realizzato considerando come chiavi solo alcuni campi dello struct. In tal caso la ricerca pu trarre vantaggio dall'ordinamento se la ricerca stessa viene effettuata utilizzando le stesse chiavi sulle quali stata applicata la relazione d'ordine. Esistono diverse categorie di algoritmi di ordinamento. Essi possono essere distinti in due classi: Algoritmi di Ordinamento Interno. Fanno uso di strutture dati allocate in memoria centrale dell'elaboratore. Per tale motivo hanno il principale limite di non permettere l'ordinamento di grosse sequenze di informazioni. Algoritmi di Ordinamento Esterno. Tipicamente fanno uso di strutture file per la memorizzazione e le operazioni di ordinamento della sequenza di informazioni da ordinare. Continua »

vedi tutti gli appunti di informatica »
Carica un appunto Home Appunti