Programexempel från Progmet-föreläsning 12, tisdag 12 oktober 2010 ================================================================== Dagens program: 1. Sorteringsalgoritmer och deras tidskomplexitet 2. En abstrakt datatyp: mängd av heltal 1. Sorteringsalgoritmer och deras tidskomplexitet ================================================= Från inlämningsuppgift 2: * Selection Sort // Sorts the array "a" of length "length" in ascending order using selection sort void sort_array(double a[], int length) { for (int sorted = 0; sorted < length - 1; ++sorted) { int smallest_in_rest = sorted; for (int in_rest = sorted + 1; in_rest < length; ++in_rest) { if (a[in_rest] < a[smallest_in_rest]) { smallest_in_rest = in_rest; } } double temp = a[sorted]; a[sorted] = a[smallest_in_rest]; a[smallest_in_rest] = temp; } } * Bogosort void bogosort_array(double a[], int length) { while (! is_array_sorted(a, length)) shuffle_array(a, length); } * Ännu dummare: void hopesort_array(double a[], int length) { // Gör inget, bara hoppas att den redan är sorterad } * Men! "Near sorting" ("soft heap") ... Fler: * Linear Insertion Sort -- O(n^2) // Sorts the array "a" of length "length" in ascending order using linear insertion sort void linear_insertion_sort(double a[], int length) { for (int sorted = 1; sorted < length; ++sorted) { // Insert the current elmenent (a[sorted]) at its place in the sorted part // Sorted part starts as 1, since a single element is always sorted! double current = a[sorted]; int place = sorted; while (place > 0 && a[place - 1] > current) { a[place] = a[place - 1]; --place; } a[place] = current; } } // linear_insertion_sort * Binary Insertion Sort -- O(n log n) jämförelser, men O(n^2) förflyttningar // Sorts the array "a" of length "length" in ascending order using binary insertion sort void binary_insertion_sort(double a[], int length) { for (int sorted = 1; sorted < length; ++sorted) { // Insert the current elmenent (a[sorted]) at its place in the sorted part // Sorted part starts as 1, since a single element is always sorted! double current = a[sorted]; // Binary search in the sorted part to find the right place for current int left = 0; int right = sorted; while (left < right) { int middle = (left + right) / 2; if (current >= a[middle]) left = middle + 1; else right = middle; } for (int i = sorted; i > left; --i) a[i] = a[i - 1]; a[left] = current; } } // binary_insertion_sort * Quicksort -- O(n log n) // Sorts the array "a" from (including) "left" to (also including) "right" static void qs(double a[], int left, int right) { int i, j; i = left; j = right; double pivot = a[(left+right)/2]; do { while((a[i] < pivot) && (i < right)) i++; while((pivot < a[j]) && (j > left)) j--; if(i <= j) { double temporary = a[i]; a[i] = a[j]; a[j] = temporary; i++; j--; } } while(i <= j); if(i < right) qs(a, i, right); if(left < j) qs(a, left, j); } // Sorts the array "a" of length "length" in ascending order using quicksort void quicksort(double a[], int length) { qs(a, 0, length - 1); } "Okonventionella" ("utan jämförelser"): * Counting Sort -- O(n) * Radix Sort -- O(n) Stora datamängder: * Merge sort "Fysisk sortering": Om det är järnvägsvagnar på en bangård, eller containrar på en båt? Hur gör man då? 2. En abstrakt datatyp: mängd av heltal ======================================= Ett gränssnitt: * Namnet IntSet * Funktionerna init, add, is_member, remove och cleanup * (De kallas IntSet_init, IntSet_add, IntSet_is_member, IntSet_remove och IntSet_cleanup.) Användning: Bilnummerspelet Flera möjliga implementationer: Variant 1 - fast array av tal, ett tal per position Variant 2 - dynamisk allokerad array av tal, ett tal per position Variant 3 - fast array av flaggor, en per möjligt tal Variant 4 - fast array av flaggor, en per möjligt tal, men packad Variant 5 - dynamiskt allokerad array av flaggor, en per möjligt tal, packad Variant 6 - binärt träd Variant 7 - hashtabell (Variant 8 - std::set) Variant 1 - fast array av tal, ett tal per position --------------------------------------------------- /* bilnummer.c */ #include #include "IntSet.h" int main(void) { IntSet mina_bilnummer; IntSet_init(&mina_bilnummer); printf("Mata in heltalsdelen av bilnummer. Avsluta med ett ogiltigt tal.\n"); int bilnumret; while (scanf("%d", &bilnumret) == 1) { if (IntSet_is_member(&mina_bilnummer, bilnumret)) printf("Fanns redan.\n"); else { printf("Nytt!\n"); IntSet_add(&mina_bilnummer, bilnumret); } } IntSet_cleanup(&mina_bilnummer); return 0; } /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #define INTSET_MAX_MEMBERS 1000 struct IntSet { int members[INTSET_MAX_MEMBERS]; int nr_members; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { isp->nr_members = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else if (isp->nr_members == INTSET_MAX_MEMBERS) { fprintf(stderr, "IntSet: Set full. Sorry.\n"); exit(EXIT_FAILURE); } else { isp->members[isp->nr_members++] = new_number; } } /* void int IntSet_is_member(IntSet* isp, int wanted) { for (int i = 0; i < isp->nr_members; ++i) if (isp->members[i] == wanted) return 1; return 0; } */ static int find_position(IntSet* isp, int wanted) { for (int i = 0; i < isp->nr_members; ++i) if (isp->members[i] == wanted) return i; return -1; } int IntSet_is_member(IntSet* isp, int wanted) { return find_position(isp, wanted) != -1; } void IntSet_remove(IntSet* isp, int doomed) { int position = find_position(isp, doomed); if (position == -1) { // Not a member, so do nothing } else { for (int i = position; i < isp->nr_members - 1; ++i) isp->members[i] = isp->members[i + 1]; --isp->nr_members; } } void IntSet_cleanup(IntSet* isp) { isp->nr_members = 0; } Variant 2 - dynamisk allokerad array av tal, ett tal per position ----------------------------------------------------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H struct IntSet { int* members; int allocated_members; int nr_members; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { isp->members = NULL; isp->allocated_members = 0; isp->nr_members = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else { if (isp->nr_members == isp->allocated_members) { if (isp->allocated_members == 0) isp->allocated_members = 16; else isp->allocated_members *= 2; isp->members = realloc(isp->members, isp->allocated_members * sizeof(isp->members[0])); if (isp->members == NULL) { fprintf(stderr, "IntSet: Memory full. Couldn't allocate %ld bytes. Sorry.\n", (long int)(isp->allocated_members * sizeof(isp->members[0]))); exit(EXIT_FAILURE); } } isp->members[isp->nr_members++] = new_number; } } static int find_position(IntSet* isp, int wanted) { for (int i = 0; i < isp->nr_members; ++i) if (isp->members[i] == wanted) return i; return -1; } int IntSet_is_member(IntSet* isp, int wanted) { return find_position(isp, wanted) != -1; } void IntSet_remove(IntSet* isp, int doomed) { int position = find_position(isp, doomed); if (position == -1) { // Not a member, so do nothing } else { for (int i = position; i < isp->nr_members - 1; ++i) isp->members[i] = isp->members[i + 1]; --isp->nr_members; } } void IntSet_cleanup(IntSet* isp) { free(isp->members); isp->members = NULL; isp->allocated_members = 0; isp->nr_members = 0; } Variant 3 - fast array av flaggor, en per möjligt tal ----------------------------------------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #define INTSET_MAX_NUMBER 1000 struct IntSet { int members[INTSET_MAX_NUMBER + 1]; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { for (int i = 0; i <= INTSET_MAX_NUMBER; ++i) isp->members[i] = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else if (new_number < 0 || new_number > INTSET_MAX_NUMBER) { fprintf(stderr, "IntSet: Number outside allowed range. Sorry.\n"); exit(EXIT_FAILURE); } else { isp->members[new_number] = 1; } } int IntSet_is_member(IntSet* isp, int wanted) { if (wanted < 0 || wanted > INTSET_MAX_NUMBER) return 0; else return isp->members[wanted]; } void IntSet_remove(IntSet* isp, int doomed) { if (doomed < 0 || doomed > INTSET_MAX_NUMBER) { // Outside range, so can't be in the set. Do nothing. exit(EXIT_FAILURE); } else { isp->members[doomed] = 0; } } void IntSet_cleanup(IntSet* isp) { for (int i = 0; i <= INTSET_MAX_NUMBER; ++i) isp->members[i] = 0; } Variant 4 - fast array av flaggor, en per möjligt tal, men packad ----------------------------------------------------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #include #define INTSET_MAX_NUMBER 1000 #define INTSET_NR_BYTES ((INTSET_MAX_NUMBER + 1) / CHAR_BIT + 1) struct IntSet { char members[INTSET_NR_BYTES]; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { for (int i = 0; i < INTSET_NR_BYTES; ++i) isp->members[i] = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else if (new_number < 0 || new_number > INTSET_MAX_NUMBER) { fprintf(stderr, "IntSet: Number outside allowed range. Sorry.\n"); exit(EXIT_FAILURE); } else { isp->members[new_number / CHAR_BIT] |= (1 << new_number % CHAR_BIT); } } int IntSet_is_member(IntSet* isp, int wanted) { if (wanted < 0 || wanted > INTSET_MAX_NUMBER) return 0; else return (isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT)) != 0; // return isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT); -- Doesn't work: } void IntSet_remove(IntSet* isp, int doomed) { if (doomed < 0 || doomed > INTSET_MAX_NUMBER) { // Outside range, so can't be in the set. Do nothing. exit(EXIT_FAILURE); } else { isp->members[doomed / CHAR_BIT] &= ~(1 << doomed % CHAR_BIT); } } void IntSet_cleanup(IntSet* isp) { for (int i = 0; i <= INTSET_NR_BYTES; ++i) isp->members[i] = 0; } Variant 5 - dynamiskt allokerad array av flaggor, en per möjligt tal, packad ---------------------------------------------------------------------------- ... Variant 6 - binärt träd ----------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H struct IntSetNode { int member; struct IntSetNode* left; struct IntSetNode* right; }; struct IntSet { struct IntSetNode* root; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ .... Variant 7 - hashtabell ---------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #define INTSET_HASH_TABLE_SIZE 4703 struct IntSetHashNode { int member; struct IntSetHashNode* next_in_bucket; }; struct IntSet { struct IntSetHashNode* hash_table[INTSET_HASH_TABLE_SIZE]; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int new_number); extern int IntSet_is_member(IntSet* isp, int wanted); extern void IntSet_remove(IntSet* isp, int wanted); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { for (int i = 0; i < INTSET_HASH_TABLE_SIZE; ++i) isp->hash_table[i] = NULL; } static unsigned int hash_function(int n) { if (n < 0) n = -n; return n % INTSET_HASH_TABLE_SIZE; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else { struct IntSetHashNode* newnode = malloc(sizeof(struct IntSetHashNode)); if (newnode == NULL) { fprintf(stderr, "IntSet: Minnet är fullt. Vi beklagar. Adjö.\n"); exit(EXIT_FAILURE); } newnode->member = new_number; unsigned int position = hash_function(new_number); newnode->next_in_bucket = isp->hash_table[position]; isp->hash_table[position] = newnode; } } int IntSet_is_member(IntSet* isp, int wanted) { unsigned int position = hash_function(wanted); struct IntSetHashNode* p = isp->hash_table[position]; while (p != NULL) { if (p->member == wanted) return 1; else p = p->next_in_bucket; } return 0; } void IntSet_remove(IntSet* isp, int wanted) { unsigned int position = hash_function(wanted); struct IntSetHashNode* p = isp->hash_table[position]; struct IntSetHashNode* previous = NULL; while (p != NULL) { if (p->member == wanted) { struct IntSetHashNode* doomed = p; if (previous == NULL) isp->hash_table[position] = p->next_in_bucket; else previous->next_in_bucket = p->next_in_bucket; free(doomed); return; } previous = p; p = p->next_in_bucket; } } void IntSet_cleanup(IntSet* isp) { for (int i = 0; i < INTSET_HASH_TABLE_SIZE; ++i) { struct IntSetHashNode* p = isp->hash_table[i]; while (p != NULL) { struct IntSetHashNode* doomed = p; p = p->next_in_bucket; free(doomed); } } } (Variant 8 - std::set) ---------------------- Förstås enklare att implementera, men datastrukturen i botten är ju någon av de här (eller en annan). Övning: Vilken?