Elenco degli algoritmi di ordinamento

La seguente tabella riepiloga gli algoritmi di ordinamento.
La spiegazione del funzionamento è solo un promemoria, non ha intento di essere esauriente.

Algoritmo Complessità Funzionamento
InsertionSort O(n2) (base) Si lascia il primo elemento dov'è

(passo induttivo) Per ogni elemento n, si trova il primo elemento maggiore tra quelli già ordinati, si sposta di una posizione da lì a n e si inserisce n tra quello appena minore e quello appena maggiore

SelectionSort O(n2) (base) Si scorre l'elenco trovando quello più piccolo e si scambia con il primo.

(passo induttivo) Posto che fino all'elemento n-1 l'elenco è ordinato e contiene solo elementi più piccoli di quelli ancora da ordinare, si scorre l'elenco da n alla fine e si scambiano l'n-esimo con il più piccolo.

BubbleSort O(n2) (base) Si confrontano il primo e il secondo elemento. Se il primo è minore del secondo non si fa niente, se il secondo è minore del primo si scambiano.

(passo induttivo) Si scorre tutto l'insieme effettuando scambi a coppie se il primo elemento è maggiore del secondo. Si procede finché tutto l'elenco non è ordinato. In pratica, si identifica al termine del primo ciclo l'elemeno più grande, poi il vice-più grande e così via

HeapSort O(nlog(n)) Utilizzando un heap si trasferisce la lista nell'heap e poi si rimuovono uno a uno gli elementi. Se max-heap si rimuove il più grande e si mette alla fine, se min-heap il contrario.
MergeSort Θ(nlog(n)) Algoritmo divide-et-impera
(Impera) avendo due sequenze ordinate da fondere, basta estrarre di volta in volta l'elemento più piccolo tra i due elementi correnti delle due code e incrementare l'indice.
(Divide) divide l'array in due parti uguali e applica il mergesort stesso a entrambe le metà.
QuickSort O(n2) (caso peggiore), O(nlog(n)) (caso medio) Algoritmo divide-et-impera
(Impera) concatena i due pezzi di array divisi dalla parte divide.
(Divide) divide l'array in due parti, in cui la prima contiene gli elementi ≥ x e la seconda gli elementi < x, dove x è un numero scelto casualmente.
IntegerSort

Nota: è detto anche CountingSort

O(n+k), dove k è l'intero più grande dell'array L'algoritmo usa un array A di appoggio di dimensione k, in cui a ogni elemento e dell'array di partenza incrementa A[e]. Alla fine scorre l'array A aggiungendo un elemento a ogni A[i] > 0 e decrementa A[i].
BucketSort O(n+k), dove k è l'intero più grande dell'array L'algoritmo funziona in maniera molto simile a IntegerSort, ma ordina record invece che interi e quindi non può usare solo un array di interi ma deve usare una lista di record.

Calcolo combinatorio: mappa del "tesoro"

In questo prospetto sono presenti i quattro tipi di insieme su cui si basa il calcolo combinatorio: ordinato/non ordinato e con/senza ripetizioni.

Prospetto

[su_accordion]
[su_spoiler title="Convenzioni" style="fancy"]
In questa notazione:

  • Y è l'insieme da cui ricaviamo gli elementi da combinare
  • |Y| è la cardinalità di Y, cioè il numero di elementi in Y
  • n è un altro modo di dire |Y|
  • k è il numero di elementi dell'insieme di destinazione
  • m è l'insieme composto dai primi m numeri naturali
  • Per non fare confusione, la notazione X è utilizzata solo per rappresentare l'operazione di prodotto cartesiano
  • m! si legge "emme fattoriale" ed è il prodotto di tutti i numeri da 1 a m (es 4! = 1x2x3x4 = 24). Inoltre 0! = 1 per definizione.
  • {a, b, c} è un insieme (non ordinato), mentre (a, b, c) è una lista (ordinato)

Esempi:

  • se Y è l'insieme dei numeri del lotto, |Y| = 90, perché si estrae da un insieme di 90 numeri
  • nello stesso esempio, k = 5, perché per ogni estrazione sono estratti cinque numeri
  • 90 è l'insieme di numeri naturali che possono essere messi in corrispondenza con i numeri del lotto
  • Se A = {1, 2} e B = {3, 4, 5} allora A X B = {(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)}
  • 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720... la funzione fattoriale cresce davvero velocemente! 20! = 2.432.902.008.176.640.000

[/su_spoiler]
[/su_accordion]

Ordinato Non ordinato
Con ripetizioni

Disposizioni con ripetizione

[su_accordion]
[su_spoiler title="Dettagli" style="fancy"]

Inglese Ordered selections with repetitions
Cardinalità (formula) |Y| = nk
Cardinalità (spiegazione) Per ogni elemento k possiamo scegliere qualunque elemento y ∈ Y.
Esempio Tombola! Il primo fa ambo, il secondo terno... quante disposizioni ci sono se Y è l'insieme di vincite (ambo, terno, quaterna...) e k il numero di giocatori?

[/su_spoiler]
[/su_accordion]

Combinazioni con ripetizioni

[su_accordion]
[su_spoiler title="Dettagli" style="fancy"]

Inglese Unordered selections with repetitions
Cardinalità (formula) |Y|=n+k-1!k!·n-k!
Cardinalità (spiegazione) Come le combinazioni senza le ripetizioni, ma con in più k-1 altre possibilità (le ripetizioni)
Esempio Ho 12 penne e 5 cassetti. In quanti modi posso distribuire le penne nei cassetti?

[/su_spoiler]
[/su_accordion]

Senza ripetizioni

Disposizioni semplici

[su_accordion]
[su_spoiler title="Dettagli" style="fancy"]

Inglese Ordered selections without repetitions
Cardinalità (formula) |Y|=n!n-k!
Cardinalità (spiegazione) Per ogni elemento k possiamo scegliere qualunque elemento y ∈ Y, tranne quelli già scelti. Abbiamo n possibilità alla prima scelta, n-1 alla seconda, e così via finché non arriviamo a n-k+1 scelte. n-k+1 e non n-k perché non abbiamo ancora scelto l'elemento.
Esempio Tris! Bisogna indovinare il piazzamento dei primi tre (k) cavalli di dieci (n) che partecipano. Quante disposizioni ci sono?

[/su_spoiler]
[/su_accordion]

Permutazioni

disposizioni semplici dove k=n
[su_accordion]
[su_spoiler title="Dettagli" style="fancy"]

Inglese Permutation
Cardinalità (formula) |Y|=n!n-k!ma siccome k=n

|Y|=n!0!=n!1=n!

Cardinalità (spiegazione) Il primo elemento può essere uno qualunque (n); il secondo può essere uno qualunque tranne quello già scelto (n-1), il terzo uno tranne quelli già scelti (n-2) finché resta un elemento solo.
Esempio Anagrammi! Quante parole diverse (non di senso compiuto) si possono scrivere con le lettere che compongono la parola RUOTA?

[/su_spoiler]
[/su_accordion]

Combinazioni senza ripetizioni

(Insiemi)

[su_accordion]
[su_spoiler title="Dettagli" style="fancy"]

Inglese Unordered selections without repetitions
Cardinalità (formula) |Y|=n!k!·n-k!
Cardinalità (spiegazione) Partendo dalle disposizioni semplici, si tolgono le permutazioni di insiemi uguali ma con ordini diversi. Per esempio, Y = {a, b, c, d}. P3 = (a,b,c), (a,c,b), (a,c,d), (a,d,c), (a,b,d), (a,d,b), (b,a,c), (b,a,d), (b,c,a), (b,d,a), (b,c,d), (b,d,c), (c,a,b), (c,a,d), (c,b,a), (c,d,a), (c,b,d), (c,d,b), (d,a,b), (d,a,c), (d,b,a), (d,c,a), (d,b,c), (d,c,b).
Quelle evidenziate in rosso sono le permutazioni di {a,b,c}
Esempio

[/su_spoiler]
[/su_accordion]