sort Tag

Premessa

Tutti gli algoritmi usano il seguente codice:

#include <stdio.h>
#define NUM_OF_ELEMENTS 10000
main() {
	int i;
	int numeri[NUM_OF_ELEMENTS];
	srand(time(NULL));
	for(i = 0; i < NUM_OF_ELEMENTS; i++) {
		numeri[i] = rand();
	}
	for(i = 0; i < NUM_OF_ELEMENTS; i++) {
		printf("%d ", numeri[i]);
		if(i % 5 == 4) printf("\n");
		}
	printf("\n\n");
	sort(&numeri, NUM_OF_ELEMENTS);
	for(i = 0; i < NUM_OF_ELEMENTS; i++) {
		printf("%d ", numeri[i]);
		if(i % 5 == 4) printf("\n");
	}
	getchar();
}

In alcuni casi la chiamata alla funzione sort può avere una firma leggermente diversa (es. possono avere come parametro l'indice di partenza, tipicamente zero).

Algoritmi con costo di esecuzione O(n²)

Tipicamente gli algoritmi di ordinamento con costo di esecuzione O(n²) sono caratterizzati da una reiterazione di tutti gli elementi per ogni "sistemazione".

Selection sort

L'algoritmo inizia con un elemento, che per definizione è orditato.

Dal secondo elemento in poi, abbiamo un insieme già ordinato - convenzionalmente a sinistra - e un insieme da ordinare - a destra.

Per ciascun elemento non ancora ordinato, si sceglie il minore tra gli elementi non ancora ordinati e si scambia con quello più a sinistra.

1

3

4

7

8

10

29

44

14

73

19

36

1

3

4

7

8

10

29

44

14

73

19

36

1

3

4

7

8

10

14

44

29

73

19

36

1

3

4

7

8

10

14

44

29

73

19

36

Il tempo di esecuzione si può calcolare dividendo l'array in due.

Per ciascun elemento già ordinato si sottrae uno al totale di elementi da ordinare, quindi con n elementi la prima iterazione sarà tutti gli elementi (n), la seconda su tutti tranne il primo (n-1) e così via, fino a fare n iterazioni su

$\sum _{j=1}^{n}n-j$

Il totale delle iterazioni è il ben noto

$\frac{n\left(n-1\right)}{2}$

Apparentemente è un tempo migliore di n², ma a ben guardare il limite per n sufficientemente grande di

$\underset{n\to \infty }{\lim }\frac{\frac{n\left(n-1\right)}{2}}{n^2}=\underset{n\to \infty }{\lim }\frac{\frac{n^2}{2}-\frac{n}{2}}{n^2}$

Dividendo il numeratore e il denominatore per n²,

$\underset{n\to \infty }{\lim }\frac{1}{2}-\frac{1}{2n}$

Si ottiene che per n sufficientemente grande, l'algoritmo tende a un costo di Θ(n²) con costante = 1/2.

Il tempo di esecuzione non varia per il caso medio, ottimo e pessimo.

L'implementazione può essere fatta in loco.

void sort(int *numeri, int conteggio) {
	int i;
	int j;
	int m;
	int temp;
	for(i = 0; i < conteggio-1; i++) {
		m = i;
		for(j = i+2; j < conteggio; j++) {
			if(numeri[j] < numeri[m]) m = j;
		}
		temp = numeri[m];
		numeri[m] = numeri[i+1];
		numeri[i] = temp;
	}
}

Insertion Sort

L'algoritmo inizia con un elemento, che per definizione è orditato.

Dal secondo elemento in poi, abbiamo un insieme già ordinato - convenzionalmente a sinistra - e un insieme da ordinare - a destra.

Per ciascun elemento non ancora ordinato, si sceglie quello più a sinistra e si scorre da sinistra a destra l'insieme ordinato fino a trovare il primo elemento maggiore dell'elemento considerato.

A questo punto si scorrono a destra di una posizione tutti gli elementi maggiori e si inserisce l'elemento considerato nella posizione lasciata libera.

1

18

27

44

89

101

29

45

14

73

19

36

1

18

27

⇒ 44

⇒ 89

⇒ 101

29

45

14

73

19

36

il 29 è memorizzato in una variabile

1

18

27

*

44

89

101

45

14

73

19

36

* questa posizione è ancora occupata dal 44, ma ai fini dell'algoritmo è libera

1

18

27

29

44

89

101

45

14

73

19

36

Il tempo di esecuzione si può discutere in maniera estremamente simile a Selection Sort.

L'implementazione può essere fatta in loco.

void sort(int *numeri, int conteggio) {
	int i;
	int j;
	int k;
	int num;
	for(i = 0; i < conteggio-1; i++) {
		num = numeri[i+1];
		for(j = 0; j <= i; j++) { if(numeri[j] > num) {
				for(k = i+1; k > j; k--) {
					numeri[k] = numeri[k-1];
				}
				numeri[j] = num;
				break;
			}
		}
	}
}

Bubble Sort

L'algoritmo inizia con un elemento, che per definizione è orditato.

Dal secondo elemento in poi, abbiamo un insieme già ordinato - convenzionalmente a sinistra - e un insieme da ordinare - a destra.

Per ciascun elemento non ancora ordinato, si sceglie quello più a sinistra e si scambia con tutti quelli già ordinati che sono maggiori dell'elemento considerato.
È maggiore il 32 o il 18? Si fa lo scambio!

32

18

45

14

73

19

36

18

32

14

45

19

73

36

È maggiore il 32 o il 45? Siccome è il 45, non c'è scambio e l'indice si incrementa.

18

14

32

45

19

73

36

18

14

32

19

45

73

36

18

14

32

19

45

36

73

Anche in questo caso il tempo di esecuzione è Θ(n²), poiché per n volte posizioniamo l'n-k-esimo elemento a destra.

L'implementazione può essere fatta in loco.

void sort(int *numeri, int conteggio) {
	short scambio;
	int i;
	int j;
	int temp;
	scambio = 0;
	for(i = 0; i < conteggio - 1; i++) {
		for(j = 1; j < conteggio - i + 1; j++) { if(numeri[j-1] > numeri[j]) {
				temp = numeri[j-1];
				numeri[j-1] = numeri[j];
				numeri[j] = temp;
				scambio = 1;
			}
		}
		if(scambio == 0) break;
	}
}

Algoritmi con costo di esecuzione O(n logn)

Gli algoritmi con questo tempo di esecuzione sono i divide-et-impera, algoritmi in cui il vettore viene diviso (tipicamente in due) tante volte fino ad arrivare a blocchi con uno o due soli elementi.

Merge Sort

Il vettore viene spezzato a metà ricorsivamente, fino ad arrivare a piccoli blocchi di uno o due elementi. Successivamente tutti gli elementi, ordinati al loro interno, sono fusi (merge) in un unico blocco grande (circa) il doppio.

V1	1	4	14	19	29	36	44	73
V2	3	7	11	21	29	39	52

Vettore risultante

La freccia indica la posizione del puntatore, il grigio indica che il numero è il più basso tra i due

V1	⇒1	4	14	19	29	36	44	73
V2	⇒3	7	11	21	29	39	52

Vettore risultante	1

 

V1	1	⇒4	14	19	29	36	44	73
V2	⇒3	7	11	21	29	39	52

Vettore risultante	1	3

 

V1	1	⇒4	14	19	29	36	44	73
V2	3	⇒7	11	21	29	39	52

Vettore risultante	1	3	4

...eccetera...

V1	1	4	14	19	29	36	44	⇒73
V2	3	7	11	21	29	39	52	⇒ *

* il puntatore ha superato i limiti, quindi è sufficiente copiare il contenuto dell'altro array

Vettore risultante	1	3	4	7	11	14	19	21	29	29	36	39	44	52

Il tempo di esecuzione del merge è C(n) = n-1 + 2C(n/2). Per il teorema master, O(n^log₂2) = O(n-1) ⇒ C(n) = Θ(n logn)

L'implementazione può essere fatta con un vettore di appoggio.

void merge(int * numeri, int inizio, int pivot, int conteggio) {
	int * merged;
	int i;
	int ja, jb;
	ja = inizio;
	jb = pivot;
	merged = malloc(sizeof(int) * (conteggio - inizio));

	for(i = inizio; i < conteggio; i++) {
		if((numeri[ja] < numeri[jb] || jb >= conteggio) && ja < pivot)
			merged[i-inizio] = numeri[ja++];
		else
			merged[i-inizio] = numeri[jb++];
	}
	for(i = inizio; i < conteggio; i++) numeri[i] = merged[i-inizio];
	free(merged);
}
void sort(int *numeri, int inizio, int conteggio, int rec) {
	int pivot;
	int i;
	if(conteggio - inizio > 1) {
		pivot = (conteggio - inizio) / 2 + inizio;
		sort(numeri, inizio, pivot, rec+1);
		sort(numeri, pivot, conteggio, rec+1);
		merge(numeri, inizio, pivot, conteggio);
	}
}

Quick Sort

Quick Sort è un algoritmo in cui il grosso del costo consiste nella fase del divide, perché richiede di scegliere un elemento pivot e di spostare tutti gli elementi minori o uguali del pivot a sinistra e tutti quelli maggiori a destra, e di applicare ricorsivamente alle due metà l'algoritmo fino a ottenere blocchi di uno o due elementi.

Limiti e caratteristiche del Quick Sort

Quick Sort richiede la scelta di un elemento, contenuto nella parte di vettore che stiamo ordinando, che sia "circa" mediano, in modo da ottenere due parti "circa" uguali. Scegliendo un elemento completamente a caso, la probabilità seguirà la classica curva gaussiana, e la probabilità di scegliere il minimo o il massimo è estremamente bassa.

Però il Quick Sort processa per la maggior parte dei casi vettori di pochi elementi, in cui la probabilità di scegliere il minimo o il massimo è non trascurabile.

Scegliendo tre elementi a caso - e non uno - e utilizzando come pivot la mediana, si riduce in modo esponenziale la probabilità di scegliere un estremo (p.e. se c'è 1/100 probabilità di ottenere un minimo o un massimo, scegliendo tra tre numeri la probabilità diventa 1/100 * 1/100 * 1/100 = 1/1.000.000).

Quick Sort richiede un "aggiustamento" nel caso in cui ci possano essere molti valori duplicati. In questo caso ci si potrebbe trovare con semi-array contenenti sempre lo stesso numero, e in questo caso il divide porterebbe a un semi-array uguale a quello originale e un altro semi-array vuoto, all'infinito.

Per questo è necessario prevedere un controllo che tutti gli elementi dell'array siano non tutti uguali (basta un elemento diverso).

Esempio d'uso

Nota: gli elementi inseriti nella funzione med (=mediana) sono scelti casualmente.

52

4

19

36

73

29

21

44

1

39

3

7

11

29

14

Pivot: med(39, 29, 36) = 36

Ricorsione: sinistra

4

19

36

29

21

1

3

7

11

29

14

Pivot: med(19, 7, 11) = 11

Ricorsione: sinistra-sinistra

4

1

3

7

11

Pivot: med(1, 3, 7) = 3

Ricorsione: sinistra-sinistra-sinistra

1

3

A questo punto, se gli elementi non sono ordinati si scambiano.
In questo caso, 1, 3

Ricorsione: sinistra-sinistra-destra

4

7

11

A questo punto, la mediana è 7, che divide l'array in 4, 7 e 11.

4 e 7 non vengono scambiati perché sono già in ordine e 11 resta da solo. Fondendo i due array si ottiene 4, 7, 11

Ricorsione: sinistra-destra

19

36

29

21

29

14

Pivot: med(19, 21, 14) = 21

Ricorsione: sinistra-destra-sinistra

19

21

14

A questo punto, la mediana è 19, si ottengono 19, 14 e 21.
19 e 14 vengono scambiati e si ottiene 14, 19, 21

Ricorsione: sinistra-destra-destra

36

29

29

A questo punto, la mediana è 29. Si ottengono 29, 29 e 36.
29 e 29 sono uguali, quindi non avviene alcuno scambio e si restituisce la coppia di numeri.
Il risultato è 29, 29, 36

Ricorsione: destra

52

73

44

39

Pivot: med(52, 73, 44) = 52

Ricorsione: destra-sinistra

52

44

39

La mediana è 44, si ottengono 44, 39 e 52.
44 e 29 si scambiano, e unendo l'elemento singolo 52 si ottiene 39, 44, 52

Ricorsione: destra-destra
Si ottiene l'elemento unico 73.

Unendo nell'ordine di chiamata, dal ramo più a sinistra a quello più a destra, si ottiene

1

3

4

7

11

14

19

21

29

29

36

39

44

52

73

Il tempo di esecuzione del Quick Sort è O(n logn).

// NOTA: Questa implementazione funziona solo con valori distinti
// NOTA: Questa implementazione non utilizza il sistema della mediata descritto nel testo

void sort(int * a, int start, int end) {
	int s, e; // inizializzati a start e end, scorrono l'array dall'inizio o dalla fine
	int pivot; // l'elemento pivot. Nella prima implementazione, è un elemento scelto completamente a caso
	int i, tmp, r;
	
	// gestisco il caso di un array di 1 e 2 elementi
	if(start >= end) return;
	if(start + 1 == end) {
		if(a[start] > a[end]) {
			tmp = a[start];
			a[start] = a[end];
			a[end] = tmp;
		}
		return;
	}
	
	srand(time(NULL));
	
	s = start;
	e = end;
	srand(time(NULL));
	r = (rand() % (end-start+1)) + start;
	pivot = a[r]; // non è un'implementazione equiprobabile, ma per i nostri scopi è più che sufficiente
	while(s < e) {
		if(a[s] <= pivot) s++; else { if(a[e] > pivot) e--;
			if(a[s] > pivot && a[e] <= pivot) { tmp = a[s]; a[s] = a[e]; a[e] = tmp; } } } if(a[s] > a[e]) {
		tmp = a[s];
		a[s] = a[e];
		a[e] = tmp;
	}
	if(a[s] <= pivot) e++; sort(a, start, e-1); if(e >= s) sort(a, e, end);
}

Algoritmi con costo di esecuzione O(n) e simili

Integer Sort

Integer Sort ha tempi migliori degli algoritmi precedenti perché suppone che gli elementi da ordinare siano tutti numeri interi positivi (in realtà è facile includere nell'algoritmo anche quelli negativi).

L'idea è di creare un array che utilizzi gli interi da ordinare come degli indici e l'elemento del secondo array incrementa semplicemente l'indice ogni volta che si incontra quel numero.

Per esempio:

5, 9, 13, 13, 6, 9, 5, 14, 2 è l'array da ordinare.

max(array) = 14, quindi si crea un array di 14 elementi (per semplicità sarà indicizzato da 1 a n, contro la prassi degli array) e si inizializzano i contatori a zero.

[0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0]

Per ogni numero esaminato si incrementa il rispettivo contatore:

5

[0] [0] [0] [0] [1] [0] [0] [0] [0] [0] [0] [0] [0] [0]

9

[0] [0] [0] [0] [1] [0] [0] [0] [1] [0] [0] [0] [0] [0]

13

[0] [0] [0] [0] [1] [0] [0] [0] [1] [0] [0] [0] [1] [0]

13

[0] [0] [0] [0] [1] [0] [0] [0] [1] [0] [0] [0] [2] [0]

...eccetera. L'ordine finale è il seguente:

[0] [1] [0] [0] [2] [1] [0] [0] [2] [0] [0] [0] [2] [1]

Scorrendo l'array si ottiene

2, 5, 5, 6, 9, 9, 13, 13, 14

Il tempo di esecuzione dipende dagli n elementi e dal k massimo, ed è O(n+k).

L'implementazione è la seguente:

sort(int * a, int count) {
	int i, k, max;
	int * appo;
	
	max = 0;
	k = 0;
	
	for(i = 0; i < count; i++) if(max < a[i]) max = a[i];
	
	appo = malloc(sizeof(int) * max + 1);
	for(i = 0; i <= max; i++) appo[i] = 0;
	for(i = 0; i < count; i++) appo[a[i]]++;
	for(i = 0; i <= max; i++) while(appo[i] > 0) {a[k++] = i; appo[i]--;}
}