Algorytmy i struktury danych Informatyka, sem IV Wyk³ad 4: Sortowanie 1. Proste algorytmy sortowania (z³o¿ono¶æ O(n*n) ) Makro do zamiany dwoch el. wektora double: #define swap( V, i, j ) { double tmp= (v)[(i)]; (v)[(i)]= (v)[(j)]; (v)[(j)]= tmp; } 1.1. Sortowanie b±belkowe void bublesort( double v[], int n ) { int bylazamiana; do { register int i; bylazamiana= 0; for( i= 1; i < n; i++ ) if( v[i] < v[i-1] ) { swap( v, i, i-1 ); bylazamiana= 1; } } while( bylazamiana ); } 1.2. Sortowanie przez wybieranie void choosesort( double v[], int n ) { register int i,j; for( i= 0; i < n-1; i++ ) { register int min= i; for( j= i+1; j < n; j++ ) if( v[j] < v[min] ) min= j; swap( v, i, min ); } } 1.3 Sortowanie przez wstawianie void insertsort( double v[], int n ) { register int i,j; for( i= 1; i < n; i++ ) { double tmp= v[i]; for( j= i-1; j >= 0 && v[j] > tmp; j-- ) v[j+1]= v[j]; v[j+1]= tmp; } } 1.4 Sortowanie Shella void shellsort( double v[], int n ) { register int i,j; register int gap= 1; while( gap <= n/9 ) gap= 3*gap + 1; /* Ustalamy maks. gap - ciag zalecany przez Knuth'a dla n <= 1000 */ for( ; gap >= 1; gap /= 3 ) for( i= gap; i < n; i++ ) { double tmp= v[i]; for( j= i-gap; j >= 0 && v[j] > tmp; j-= gap ) v[j+gap]= v[j]; v[j+gap]= tmp; } } Czy to sortuje ? Prosze zwrocic uwage, i¿ dwie wewnêtrzne pêtle for to uogolniona wersja alg. przez wstawianie. A wiêc, w najgorszym wypadku Shellsort to insertsort. Ulepszenie polega na tym, ze w pierwszych przebiegach (dla du¿ych wart. gap) porownywane (i ew. zamieniane) s± odleg³e elementy. W dalszych przebiegach pozostaje juz niewiele do zrobienia. 2. Algorytmy optymalne (z³o¿ono¶æ O(n*log_2(n))) 2.1 Sortowanie szybkie (najlepszy znany algorytm oparty na porównywaniu elementów) int rozdziel( double a[], int s, int k ) { /* rozdziela wektor a wzgledem a[0], zwraca pozycje a[0] w wektorze wynikowym */ int i, j; double tmp; j= s; for( i= s+1; i <= k; i++ ) /* niezmiennik: a[s+1..j] < a[s] i a[j+1..i-1] >= a[s] */ if( a[i] < a[j] ) { tmp= a[++j]; a[j]= a[i]; a[i]= tmp; } tmp= a[j]; a[j]= a[s]; a[s]= tmp; return j; } void mqsort( double a[], int s, int k ) { /* sortuje in situ, rosnaco a[s..k] */ if( s < k ){ int j= rozdziel( a, s, k ); mqsort( a, s, j-1 ); mqsort( a, j+1, k ); } } void quicksort( double a[], int na ) { mqsort( a, 0, na-1 ); } Bez rekurencji: #define MAXS 1024 /* maksymalna gleb. stosu */ void mqsort( double a[], int s, int k ) { /* sortuje in situ, rosnaco a[s..k] */ int ss[MAXS], ks[MAXS], sp= 0; /* ss <- "poczatki", ks <- "konce" pod-wektorow */ if( s < k ){ ss[0]= s; ks[0]= k; sp= 1; while( sp ) { int bs= ss[--sp]; int bk= ks[sp]; int j= rozdziel( a, bs, bk ); if( j-1 > bs ) { ss[sp]= bs; ks[sp++]= j-1; } if( k > j+1 ) { ss[sp]= j+1; ks[sp++]= bk; } } } } 2.2 Sortowanie stogowe Zagadnienia wstêpne: - pojecie stogu; - implementacja tablicowa; typedef struct { Data d; /* jakiekolwiek dane */ int key; /* klucz porz±dkuj±cy */ } Elem; typedef Elem * Heap; /* stog jest tablica elementów */ #define swap( h, i, j ) { Elem tmp= (h)[(i)]; (h)[(i)]= (h)[(j)]; (h)[(j)]= tmp; } - wstawianie nowego elementu: dodanie na koniec i przesiewanie w górê (funkcja "do góry" o koszcie O(log_2(n))) void heap_up( Heap s, int n ) { int i= n; int p= (i-1)/2; while ( i > 0 && s[p].key > s[i].key ) { swap( s, p, i ); i= p; p= (i-1)/2; } } - usuwanie szczytowego elementu: zast±pienie go ostatnim i przesiewanie w dó³ (funkcja "na dó³" o koszcie O(log_2(n))) void heap_down( Heap s, int n ) { int p= 0; int d= 2*p+1; while ( d < n ) { if( d+1 < n && s[d+1].key < s[d].key ) d++; if( s[p].key < s[d].key ) return; swap( s, p, d ); p= d; d= 2*p+1; } } Teraz sortowanie stogowe, zrobione analogicznie do standardowego qsort-a (potrafi sortowac dowolne tablice). void hsort(void *t, int n, size_t s, int (* cmpf)(const void *, const void *)) { int i; int b, p; char *tmp = malloc(s); char *v = t; int k; for (i = 1; i < n; i++) { /* dogory(t[i]... */ b = i; p = (n-1)/2; while (cmpf(v+p*s, v+b*s) < 0) { memcpy(tmp, v+p*s, s); memcpy(v+p*s, v+b*s, s); memcpy(v+b*s, tmp, s); b = p; p = (b-1)/2; } for (k = 0; k <= i; k++) printf("%g ", *(float *)(v+k*s)); printf("\n"); } for (i = 0; i < n; i++) printf("%g ", *(float *)(v+i*s)); printf("\n"); for (i = n-1; i > 0; i--) { memcpy(tmp, v, s); memcpy(v, v+i*s, s); memcpy(v+i*s, tmp, s); b = 0; p = 2*b+1; while (p < n) { if (p+1 < n && cmpf(v+(p+1)*s, v+p*s) > 0) p++; if (cmpf(v+p*s, v+b*s) <= 0) break; memcpy(tmp, v+p*s, s); memcpy(v+p*s, v+b*s, s); memcpy(v+b*s, tmp, s); b = p; p = 2*b+1; } } } Zagadnienia dodatkowe: - wykorzystanie stogu do implementacji kolejki priorytetowej - scalanie posortowanych plików (ci±gów danych) => wyk³ad z j. C