Guida Algoritmi di ordinamento

[ptm]

Algoritmi di ordinamento

Gli algoritmi di ordinamento sono algoritmi che consentono di riposizionare elementi di una lista in un determinato ordine. Gli ordini più utilizzati sono quello numerico e quello lessicografico.
Il problema dell'ordinamento è molto importante in informatica in quanto permette di ottimizzare il funzionamento di altri algoritmi (per esempio quelli di unione di due liste o di ricerca); di conseguenza è chiaro che sarebbe desiderabile avere algoritmi di ordinamento il più efficienti possibile.

Un algoritmo di ordinamento deve rispettare due condizioni:

1. Deve essere stabilita una relazione d'ordine tra gli elementi (per esempio x[SUB]1[/SUB] ≤ x[SUB]2[/SUB] ≤ .. ≤ x[SUB]n[/SUB] )
2. La lista in output deve essere una permutazione della lista in input (cioè nella lista in output devono apparire tutti e soli gli elementi della lista in input)

Gli algoritmi che vedremo saranno studiati per funzionare sugli array che permettono accesso casuale agli elementi. Un limite fondamentale per gli algoritmi che si basano su confronti è che hanno una complessità computazionale pari a Ω(n log n) dove n è il numero di elementi da ordinare (non ci soffermeremo sulle dimostrazioni delle complessità computazionali degli algoritmi),
Gli algoritmi di ordinamento vengono molto utilizzati nell'apprendimento di materie connesse all'informatica perchè trasmettono una serie importante di concetti come la

Perfavore, Entra oppure Registrati per vedere i Link!

, lo stile "

Perfavore, Entra oppure Registrati per vedere i Link!

" e diversi tipi di

Perfavore, Entra oppure Registrati per vedere i Link!

.


Algoritmi di ordinamento comuni

• Selection Sort
• Bubble Sort
• http://www.sciax2.it/forum/c-c/merge-sort-685533.html#post4305797
• http://www.sciax2.it/forum/c-c/quick-sort-687093.html#post4314962
• http://www.sciax2.it/forum/c-c/counting-sort-688299.html#post4321472

Note sulle guide

• Gli algoritmi sono stati scritti in C/C++, ma possono essere costruiti tranquillamente in altri linguaggi
• Verranno applicati all'ordinamento di vettori (per semplicità), ma i discorsi valgono anche per altre strutture dati
• Non dimostreremo la complessità computazionale degli algoritmi

 

[TBH]

@ptm topic interessante, attendo sviluppi sugli altri algoritmi di ordinamento :soso: .

 

[ptm]

@ptm topic interessante, attendo sviluppi sugli altri algoritmi di ordinamento :soso: .

Grazie Si, ho intenzione di aggiungerne altri presto..

 

[Dvdxseo]

Spero anche in un'aggiunta di almeno un algoritmo di ordinamento non basato sui confronti come esempio di ordinamento in tempo lineare sotto certe ipotesi.. :P

 

[ptm]

Spero anche in un'aggiunta di almeno un algoritmo di ordinamento non basato sui confronti come esempio di ordinamento in tempo lineare sotto certe ipotesi.. :P

Grazie per il consiglio; aggiunto :ok: