// ex6_3_1.cpp // selection sort #include <iostream.h> #include <stdlib.h> #include <time.h> // scambia due interi void scambia (int& a, int& b) { int t = a; a = b; b = t; } // ordina un array di interi da inf a sup void selectionSort (int v[], int inf, int sup) { for (int i = inf; i < sup; i++) { int min = i; for (int j = i + 1; j < sup; j++) if (v[j] < v[min]) scambia (v[j], v[min]); } } void stampa (int v[], int inf, int sup) { for (int i = inf; i < sup; i++) if (i % 5 == 4) cout << v[i] << "\n"; else cout << v[i] << "\t"; } void main() { const int N = 20; int v[N]; // inserisce N numeri a caso nel vettore srand ( time(0) ); for (int i = 0; i < N; i++) v[i] = rand() % 100 + 1; cout << "vettore disordinato:\n"; stampa (v, 0, N); selectionSort (v, 0, N); cout << "\nvettore ordinato:\n"; stampa(v, 0, N); }
esempio di output:
vettore disordinato:
58 | 96 | 89 | 15 | 28 | |
18 | 32 | 87 | 18 | 74 | |
90 | 7 | 65 | 19 | 93 | |
75 | 17 | 62 | 68 | 3 |
3 | 7 | 15 | 17 | 18 | |
18 | 19 | 28 | 32 | 58 | |
62 | 65 | 68 | 74 | 75 | |
87 | 89 | 90 | 93 | 96 |
Come si vede, con sole 8 righe di codice si riesce ad ordinare un array; si sappia comunque che questo metodo è poco efficiente; il tempo di ordinamento, infatti, cresce circa al quadrato all'aumentare del numero di elementi (cioè se per ordinare un gruppo di dati ci vuole un certo tempo, raddoppiando il numero dei dati, il tempo necessario è almeno quattro volte superiore). Comunque nei nostri futuri esempi utilizzeremo sempre tale metodo, perché facile da capire e da memorizzare, e sufficiente ai nostri scopi; come è ovvio, nei nostri esempi non dovremo mai ordinare un numero di dati tale da potere apprezzare sensibilmente la differenza di tempo di esecuzione tra questo metodo di ordinamento ed un altro, anche molto più efficiente (provando il programma su una macchina con un processore Intel Pentium II, ci vogliono circa 1.5 secondi ad ordinare diecimila interi con il selection sort).