Programexempel från Progmet-föreläsning 11, onsdag 6 oktober 2010 ================================================================= Kvar från igår: 3. Lågnivåprogrammering: bitar och bytes 4. Mer om hårdvarunära programmering 5. Trådar (3-5: se anteckningarna för föreläsning 10) Om vi hinner: 6. Sorteringsalgoritmer och deras tidskomplexitet 6. 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 (men fel?!) void linear_insertion_sort(double a[], int length) { for (int sorted = 0; sorted < length; ++sorted) { // Insert the current elmenent (a[sorted]) at its place in the sorted part int current = a[sorted]; int place = sorted; while (place > 0 && a[place - 1] > current) { a[place] = a[place - 1]; --place; } a[place] = current; } } * Binary Insertion Sort -- O(n log n) jämförelser, men O(n^2) förflyttningar * Quicksort -- O(n log n) "Okonventionella" ("utan jämförelser"): * Counting Sort -- O(n) * Radix Sort -- O(n) Stora datamängder: * Merge sort