randomized_quicksort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include "chapter-7/quicksort/quicksort.h"namespace CLRS { template <typename T, std::size_t n> std::size_t randomized_partition(T (&a)[n], long long p, long long r) { std::default_random_engine e(std::time(0)); std::uniform_int_distribution<long long> u(p, r); long long i = u(e); T temp = a[r]; a[r] = a[i]; a[i] = temp; return CLRS::partition(a, p, r); } template <typename T, std::size_t n> void randomized_quicksort(T (&a)[n], long long p, long long r) { if(p < r) { std::size_t q = randomized_partition(a, p, r); randomized_quicksort(a, p, q - 1); randomized_quicksort(a, q + 1, r); } } } quicksort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 namespace CLRS { template <typename T, std::size_t n> std::size_t partition(T (&a)[n], long long p, long long r) { T x = a[r]; std::size_t i = p; for(std::size_t j = p; j !

heapsort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include "../build_max_min_heap/build_max_min_heap.h"#include "../max_min_heapify/max_min_heapify.h"namespace CLRS { template <typename T, std::size_t n> void heapsort(T (&a)[n]) { CLRS::build_max_heap(a); for(std::size_t i = n - 1; i >= 1; --i) { T temp = a[i]; a[i] = a[0]; a[0] = temp; if(i >= 2) CLRS::max_heapify(a, 0, i); } } /* * use minimal heap priority queue * result sorted from large to small.

hire_assistant_permute_by_sorting 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include "chapter-2/merge_sort/merge_sort.h"namespace CLRS { template <typename T> bool operator<=(std::pair<T, unsigned> p1, std::pair<T, unsigned> p2) { return p1.second <= p2.second; } template <typename T, std::size_t n> void permute_by_sorting(T (&array)[n]) { std::default_random_engine e(std::time(0)); std::uniform_int_distribution<unsigned> u(0, (n-1)*(n-1)*(n-1)); std::pair<T, unsigned> parray[n]; for(std::size_t i = 0; i != n; ++i) parray[i] = std::pair<T, unsigned>(array[i], u(e)); CLRS::merge_sort(parray, 0, n - 1); for(std::size_t i = 0; i !

square_matrix_multiply Is there any better idea to implement matrix operation helper functions? Or are these helper functions necessary, can we handle this algorithm without them? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 #include "square_matrix_multiply_recursive.

merge_sort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 namespace CLRS { template <typename T> void merge(T *array, std::size_t p, std::size_t q, std::size_t r) { std::size_t n1 = q - p + 1; std::size_t n2 = r - q; T larray[n1], rarray[n2]; for(std::size_t i = 0; i < n1; ++i) larray[i] = array[p + i]; for(std::size_t j = 0; j < n2; ++j) rarray[j] = array[q + j + 1]; std::size_t i = 0, j = 0, k = p; while(k <= r) { if(i < n1 && j == n2) { array[k] = larray[i]; ++i; } else if(i == n1 && j < n2) { array[k] = rarray[j]; ++j; } else if(larray[i] <= rarray[j]) { array[k] = larray[i]; ++i; } else { array[k] = rarray[j]; ++j; } ++k; } } template <typename T> void merge_sort(T *array, std::size_t p, std::size_t r) { if(p < r) { std::size_t q = (p + r) / 2; merge_sort(array, p, q); merge_sort(array, q + 1, r); merge(array, p, q, r); } } } insertion_sort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 namespace CLRS { template <typename T, std::size_t n> void insertion_sort(T (&array)[n]) { /* * for std::size_t is a alias of unsigned long, * and the index in while loop must not be an unsigned, * then index should be long long which could * accommodate the maximum unsigned long integer * to avoid bug.