Today is Dena’s 26th birthday. Yup, she’s 26 thirty-two days before I am 🙂 She’ll be collecting her pension before me. So today, flood her with birthday wishes, if you can.
Not much else is new. I’ve updated a few more sections on the site; only a couple more to go. Oh, here’s a thought on sorting algorithms:
Bubble sort
-O(n^2) complexity
-easy to implement
-inefficient
void bubbleSort(int numbers[], int array_size) { int i, j, temp; for (i = (array_size - 1); i >= 0; i--) { for (j = 1; j < = i; j++) { if (numbers[j-1] > numbers[j]) { temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp; } } } } |
Heap sort
-O(n log n) complexity
-good for large data sets, but not for small ones
void heapSort(int numbers[], int array_size) { int i, temp; for (i = (array_size / 2)-1; i >= 0; i--) siftDown(numbers, i, array_size); for (i = array_size-1; i >= 1; i--) { temp = numbers[0]; numbers[0] = numbers[i]; numbers[i] = temp; siftDown(numbers, 0, i-1); } } void siftDown(int numbers[], int root, int bottom) { int done, maxChild, temp; done = 0; while ((root*2 < = bottom) && (!done)) { if (root*2 == bottom) maxChild = root * 2; else if (numbers[root * 2] > numbers[root * 2 + 1]) maxChild = root * 2; else maxChild = root * 2 + 1; if (numbers[root] < numbers[maxChild]) { temp = numbers[root]; numbers[root] = numbers[maxChild]; numbers[maxChild] = temp; root = maxChild; } else done = 1; } } |
Insertion sort
-O(n^2) complexity
-easy to implement
-best suited for small data sets
void insertionSort(int numbers[], int array_size) { int i, j, index; for (i=1; i < array_size; i++) { index = numbers[i]; j = i; while ((j > 0) && (numbers[j-1] > index)) { numbers[j] = numbers[j-1]; j = j - 1; } numbers[j] = index; } } |
Quick sort
-O(n log n) complexity
-fast
-recursive and ugly to look at
void quickSort(int numbers[], int array_size) { q_sort(numbers, 0, array_size - 1); } void q_sort(int numbers[], int left, int right) { int pivot, l_hold, r_hold; l_hold = left; r_hold = right; pivot = numbers[left]; while (left < right) { while ((numbers[right] >= pivot) && (left < right)) right--; if (left != right) { numbers[left] = numbers[right]; left++; } while ((numbers[left] <= pivot) && (left < right)) left++; if (left != right) { numbers[right] = numbers[left]; right--; } } numbers[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot) q_sort(numbers, left, pivot-1); if (right > pivot) q_sort(numbers, pivot+1, right); } |
I may not know all of these off the top of my head, since I don’t use most them on a daily basis. However, I can easily look them up in my notes from university and it all comes flooding back. Just a thought.
