flashsort.h (5310B)
1 #pragma once 2 3 /** 4 * \file 5 * 6 * type safe flashsort implementation 7 * 8 * flashsort is in the classification sort category (no string compare) and sorts numbers (int, uint, float, ...). 9 * 10 * struct and pointer elements in the input array are supported 11 * 12 * 13 * the performance depends on how uniform is the distribution, 14 * the more uniform the better (high variance). 15 * 16 * adjust the m parameter (number of classes) to change the performance/memory usage ratio. 17 * 18 * when the variance is high, a m/size ratio of 0.1 gives good performance and low memory usage. 19 * 20 * an array of size m * sizeof(size_t) is allocated the heap and then freed 21 * 22 * 23 * Example: 24 * 25 * // declare an array 26 * typ struct { 27 * i32 key; 28 * i32 value; 29 * } elemt; 30 * 31 * elemt array[1000]; 32 * 33 * // define flashsortGet 34 * #define flashsortGet(ptr) (ptr)->key 35 * 36 * // call flashsort 37 * flashsort(array, ARRAY_SIZE(array)); 38 * 39 * // or call flashsortM to be able to set the number of classes 40 * // flashsortM(array, ARRAY_SIZE(array), 0.43 * ARRAY_SIZE(array)); 41 * 42 * #undef flashsortGet 43 */ 44 45 46 /** 47 * flashsort with predefined m/size ratio for high variance distributions 48 * 49 * the flashsortGet macro or function has to be defined before calling flashsortM 50 * flashsortGet takes an address in parameter and returns a key 51 * 52 * \param 53 * arr array to sort 54 * \param 55 * size number of elements in the array 56 */ 57 #define flashsort(arr, size) flashsortM(arr, size, size / 16 /* m classes */) 58 59 60 61 62 63 // ******** 64 // internal helper macros 65 #define flashsortSubKMacro(num)\ 66 if (num > 0 and min < 0)\ 67 k = c * ((toUnsignedType(num))(num) + (toUnsignedType(num))(-min)) + 1;\ 68 else\ 69 k = c * ((num) - min) + 1 70 // end internal helper macros 71 72 73 // ******** 74 /** 75 * flashsort with predefined m/size ratio for high variance distributions 76 * 77 * the flashsortGet macro or function has to be defined before calling flashsortM 78 * flashsortGet takes an address in parameter and returns a key 79 * 80 * \param 81 * arr array to sort, this parameter is evaluated multiple times, 82 * it cannot be a value returned by a function that changes during the flashsort execution 83 * \param 84 * size number of elements in the array 85 * \param 86 * m number of classes 87 */ 88 #define flashsortM(arr, asize, mc) do {\ 89 size_t UNIQVAR(size) = asize;\ 90 size_t UNIQVAR(m) = mc;\ 91 if (UNIQVAR(m) < 2) {\ 92 logE("number of class m is too low: %zu", UNIQVAR(m));\ 93 break;\ 94 }\ 95 /* Phase 1*/\ 96 var min = flashsortGet(&arr[0]);\ 97 var max = flashsortGet(&arr[0]);\ 98 /* added { to isolate variable definition in range */\ 99 {rangeFrom(i, 0, UNIQVAR(size)) {\ 100 min = MIN(flashsortGet(&arr[i]), min);\ 101 max = MAX(flashsortGet(&arr[i]), max);\ 102 /*logVarG(i);\ 103 logI("v %u %d", flashsortGet(&arr[i]), flashsortGet(&arr[i)]);\ 104 logI("min %u max %u", min, max);\ 105 logVarG(flashsortGet(&arr[i)]);\ 106 logVarG(arr[i]);\ 107 logVarG(flashsortGet(&arr[i]));*/\ 108 }}\ 109 \ 110 /*logVarG(min);\ 111 logVarG(max);*/\ 112 \ 113 if (min == max)\ 114 break;\ 115 \ 116 /* Divide to UNIQVAR(m) class */\ 117 /* c could be float instead of double, but the performance is better with double (intel skylake cpu) */\ 118 double c;\ 119 /* avoid overflow */\ 120 if (max > 0 and min < 0)\ 121 c = (double)(UNIQVAR(m) - 1) / ((toUnsignedType(max))max + (toUnsignedType(min))(-min));\ 122 else\ 123 c = (double)(UNIQVAR(m) - 1) / (max - min);\ 124 /*logVarG(UNIQVAR(m));\ 125 logVarG((double)c);*/\ 126 \ 127 size_t *L = callocArray(L, UNIQVAR(m) + 1);\ 128 /* added { to isolate variable definition in range */\ 129 {range(i, UNIQVAR(size)) {\ 130 size_t k;\ 131 flashsortSubKMacro(flashsortGet(&arr[i]));\ 132 /* L[k]: the number of class K */\ 133 L[k]++;\ 134 }}\ 135 /* added { to isolate variable definition in range */\ 136 {rangeFrom(k, 2, UNIQVAR(m)+1) {\ 137 /* L[k]: upper bound of class K */\ 138 L[k] += L[k - 1];\ 139 }}\ 140 \ 141 /* Phase 2 */\ 142 /* number of move */\ 143 size_t move = 0;\ 144 size_t j = 0;\ 145 size_t k = UNIQVAR(m);\ 146 /* Only move UNIQVAR(size) - 1 step */\ 147 while (move < UNIQVAR(size) - 1)\ 148 {\ 149 /* flashsortGet(&arr[j]) is in right class */\ 150 while (j >= L[k])\ 151 {\ 152 j++;\ 153 flashsortSubKMacro(flashsortGet(&arr[j]));\ 154 }\ 155 /* temp to hold the value */\ 156 var flash = flashsortGet(&arr[j]);\ 157 var flashEl = arr[j];\ 158 /* stop when flashsortGet(&arr[j]) is changed */\ 159 while (j < L[k])\ 160 {\ 161 flashsortSubKMacro(flash);\ 162 /* swap */\ 163 var tmpEl = flashEl;\ 164 flashEl = arr[--L[k]];\ 165 arr[L[k]] = tmpEl;\ 166 flash = flashsortGet(&flashEl);\ 167 move++;\ 168 }\ 169 }\ 170 \ 171 /* Phase 3 172 Use Insertion sort for every class 173 Don't sort the UNIQVAR(m) class, 174 Because the UNIQVAR(m) class is all max */\ 175 rangeFrom(k, 1, UNIQVAR(m)) {\ 176 for (size_t i = L[k] + 1; i < L[k + 1]; i++) {\ 177 var key = flashsortGet(&arr[i]);\ 178 var keyEl = arr[i];\ 179 i64 j = i - 1;\ 180 while (j >= 0 and flashsortGet(&arr[j]) > key)\ 181 {\ 182 arr[j+1] = arr[j];\ 183 j--;\ 184 }\ 185 arr[j+1] = keyEl;\ 186 }\ 187 }\ 188 free(L);\ 189 }while(0) 190 191 // vim: set expandtab ts=2 sw=2: