1 Dziel – Rządź - Złącz
2 sort złączenia (”Merge Sort”) cz. 1#include
3 sort złączenia (”Merge Sort”) cz. 2char *a = data, *m; int ipos, jpos, mpos; /* inicjalizacja liczników złączania */ ipos = i; jpos = j + 1; mpos = 0; /* Rezerwacja pamięci na złączane elementy */
4 sort złączenia (”Merge Sort”) cz. 3if ((m = (char *) malloc(esize * ((k - i) + 1))) == NULL) return -1; /* Działamy, póki którakolwiek część ma elementy do złączania */ while (ipos <= j || jpos <= k) { if (ipos > j) {/* W lewej części nie ma już elementów do złączania */ while (jpos <= k) { memcpy(&m[mpos * esize], &a[jpos * esize], esize); jpos++; mpos++; }
5 sort złączenia (”Merge Sort”) cz. 4continue; } else if (jpos > k) {/* w prawej części nie ma już elementów do złączania */ while (ipos <= j) { memcpy(&m[mpos * esize], &a[ipos * esize], esize); ipos++; mpos++;
6 sort złączenia (”Merge Sort”) cz. 5/* Dołączenie do złączonych elementów następnego elementu */ if (compare(&a[ipos * esize], &a[jpos * esize]) < 0) { memcpy(&m[mpos * esize], &a[ipos * esize], esize); ipos++; mpos++; }
7 sort złączenia (”Merge Sort”) cz. 6else { memcpy(&m[mpos * esize], &a[jpos * esize], esize); jpos++; mpos++; }
8 sort złączenia (”Merge Sort”) cz. 7/* Przygotowanie do przekazania z powrotem złączonych danych */ memcpy(&a[i * esize], m, esize * ((k - i) + 1)); /* Zwolnienie pamięci używanej na złączanie */ free(m); return 0; } /* koniec funkcji merge */
9 sort złączenia (”Merge Sort”) cz. 8int mgsort(void *data, int size, int esize, int i, int k, int (*compare) (const void *key1, const void *key2)) { int j; /* Koniec rekurencji, kiedy niemożliwe są dalsze podziały */ if (i < k) { /* Ustalenie, gdzie należy podzielić elementy */ j = (int)(((i + k - 1)) / 2);
10 sort złączenia (”Merge Sort”) cz. 9/* Rekurencyjne sortowanie dwóch części */ if (mgsort(data, size, esize, i, j, compare) < 0) return -1; if (mgsort(data, size, esize, j + 1, k, compare) < 0) return -1; /* Złączanie dwóch posortowanych części w jeden zbiór posortowany */ if (merge(data, esize, i, j, k, compare) < 0) return -1; } return 0;
11 sort złączenia (”Merge Sort”) cz. 10int compare (const void * x, const void * y) { int *a, *b; a=(int *) x; b=(int *) y; if( (*a) > (*b) ) return(1); else return(-1); } /* koniec funkcji compare */
12 sort złączenia (”Merge Sort”) cz. 11/* program glówny testuje funkcję mgsort */ int main() { int a[5]; int n; int ktrl=-99;; srand(getpid()); for(n=0;n<5;++n) { a[n]=rand()%100; printf(" %d", *(a+n)); }
13 sort złączenia (”Merge Sort”) cz. 12ktrl=mgsort(a, 5, sizeof(int), 0,4,compare); /* sortowanie !! */ printf("\n ktrl=%d",ktrl); printf("\n\n"); for(n=0;n<5;++n) { printf(" %d", *(a+n)); /* to elementy posortowane */ } exit(0); }/* koniec funkcji main */
14 sort złączenia (”Merge Sort”) cz. 13users.uj.edu.pl/~ufrudy/mgsorttest.c
15 algorytm sortowania QUICKSORT- algorytm Mergesort ma pewną wadę..... statystycznie dobrany ”punkt podziału” - QUICKSORT - wady QUICKSORT; co jeśli ”punkt podziału” jest dobrany niefortunnie ?
16 sortowanie ze zliczaniemszybki algorytm sortowania, który opiera się na zliczaniu wystąpień poszczególnych elementów w zbiorze. niestety, ma ograniczenia dotyczące danych a)sortować można jedynie liczby całkowite i dane dające się jako takie wyrazić b)trzeba znać największą liczbę występująca w danych (rezerwuje się odpowiednio dużą tablicę)
17 sortowanie ze zliczaniem - 1#include
18 sortowanie ze zliczaniem - 2/* Alokacja pamięci na liczniki. */ if ((counts = (int *) malloc(k * sizeof(int))) == NULL) return -1; /* Alokacja pamięci na posortowane elementy. */ if ((temp = (int *)malloc(size * sizeof(int))) == NULL)
19 sortowanie ze zliczaniem - 3/* Inicjalizacja liczników. */ for (i = 0; i < k; i++) counts[i] = 0; /* Zliczanie wystąpień poszczególnych elementów. */ for (j = 0; j < size; j++) counts[data[j]] = counts[data[j]] + 1; /* ++counts[ *(data+j) ]; */ /* ( counts + (*(data+j)) ) ; */
20 sortowanie ze zliczaniem - 4/* Korekta poszczególnych liczników, aby zawierały liczbę poprzedzających je elementów */ for (i = 1; i < k; i++) counts[i] = counts[i] + counts[i - 1]; /* Użycie counts do położenia poszczególnych elementów w odpowiednie miejsca.*/ for (j = size - 1; j >= 0; j--) { temp[counts[data[j]] - 1] = data[j]; /* tu temp[] użyte */ counts[data[j]] = counts[data[j]] - 1; }
21 sortowanie ze zliczaniem - 5/* Przygotowanie posortowanych danych do zwrócenia*/ memcpy(data, temp, size * sizeof(int));/* /*Zwolnienie pamięci użytej do sortowania */ free(counts); free(temp); return 0; } /* koniec funkcji ctsort */
22 sortowanie ze zliczaniem - 6int main() {int a[5]; int n; int ktrl=-99;; srand(getpid()); for(n=0;n<5;++n) { a[n]=rand()%100; printf(" %d", *(a+n)); /* wartości niesortowane */ }
23 sortowanie ze zliczaniem - 7ktrl=ctsort(a, 5, 100); /* wywołanie f. sortującej */ printf("\n ktrl=%d",ktrl); printf("\n\n"); for(n=0;n<5;++n) { printf(" %d", *(a+n)); /* po przesortowaniu */ } }/* koniec funkcji main */
24 sortowanie ze zliczaniem - 8Adres strony: users.uj.edu.pl/~ufrudy/ctsorttest.c
25 Sortowanie na stercie Heap SortZbiór n liczb tworzy stertę (”heap”), jeżeli jego elementy spełniają następujący związek: aj/2 aj/2 aj dla j/2 j n (j/2 oznacza dzielenie całkowitoprzecinkowe)
26 Sortowanie na stercie Heap Sortadres strony z przykładowym zadaniem: users.uj.edu.pl/~ufrudy/heap3.c
27 Dlaczego dane w ogóle można skompresować? Kompresja danych Kompresja danych polega na zmniejszeniu liczby bitów potrzebnych do zapisania danych. Podstawy teoretyczne – teoria informacji (dział matematyki). Kompresja i dekompresja danych. Dlaczego dane w ogóle można skompresować? kompresja stratna, kompresja bezstratna. Każde dane można scharakteryzować jeśli chodzi o ich zawartość informacyjną używając pojęcia zapożyczonego z termodynamiki – entropia. przykład intuicyjny ; dwa układy N bajtów, o pierwszym nie wiemy nic, a drugim wiemy dodatkowo że np. układ odpowiadający znakowi ‘a’ stanowi 50 % bajtów; cyzli wiemy
28 kodowanie Huffmana jako przykład algorytmu kompresjiKompresja danych przykładowa entropia drzewo Huffmana kodowanie Huffmana jako przykład algorytmu kompresji przykład intuicyjny ; dwa układy N bajtów, o pierwszym nie wiemy nic, a drugim wiemy dodatkowo że np. układ odpowiadający znakowi ‘a’ stanowi 50 % bajtów;