Here is an example that google does not give me the result in the first page. I want to know how to calculate median efficiently, and so I search “c calculate median”. In the first result page, google brings me to several forums which only show very naive implementations. The 11th result, this page, is the truely invaluable one which should be favoured by most programmers. I do not want to replicate that website. I just want to show you a function that is adapted from quickselect.c on the website. This function calculates the k-smallest (0<=k<n) element in an array. Its time complexity is linear to the size of the array and in practice it runs much faster than sorting and then locating the k-smallest element.
type_t ks_ksmall(size_t n, type_t arr[], size_t kk) { type_t *low, *high, *k, *ll, *hh, *middle; low = arr; high = arr + n - 1; k = arr + kk; for (;;) { if (high <= low) return *k; if (high == low + 1) { if (cmp(*high, *low)) swap(type_t, *low, *high); return *k; } middle = low + (high - low) / 2; if (lt(*high, *middle)) swap(type_t, *middle, *high); if (lt(*high, *low)) swap(type_t, *low, *high); if (lt(*low, *middle)) swap(type_t, *middle, *low); swap(type_t, *middle, *(low+1)) ; ll = low + 1; hh = high; for (;;) { do ++ll; while (lt(*ll, *low)); do --hh; while (lt(*low, *hh)); if (hh < ll) break; swap(type_t, *ll, *hh); } swap(type_t, *low, *hh); if (hh <= k) low = ll; if (hh >= k) high = hh - 1; } }
In this funcion, type_t is a type, swap() swaps two values, and lt() is a macro or a function that returns true if and only if the first value is smaller.
Leave a comment