StoneHaos

qsort

Apr 30th, 2020
285
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void __qswap(void *a, int offseta, void *b, int offsetb, size_t size) {
  2.     void *tmp = malloc(size);
  3.     memcpy(tmp, (char*)a + (offseta * size), size);
  4.     memcpy((char*)a + (offseta * size), (char*)b + (offsetb * size), size);
  5.     memcpy((char*)b + (offsetb * size), tmp, size);
  6.     free(tmp);
  7. }
  8.  
  9. void qs(void *arr, unsigned n, size_t size, int (*comp)(const void*, const void*)) {
  10.     if (n <= 1)
  11.         return;
  12.     int pivot = (n - 1) >> 1;
  13.     int left = 0, right = n - 1;
  14.     void *a = malloc(size), *b = malloc(size);
  15.     while (left < right) {
  16.         memcpy(a, (char*)arr + (left * size), size);
  17.         memcpy(b, (char*)arr + (pivot * size), size);
  18.         while (left < pivot && comp(a, b) < 1) { // while (left < pivot && arr[left] <= arr[pivot])
  19.             ++ left;
  20.             memcpy(a, (char*)arr + (left * size), size);
  21.         }
  22.         memcpy(a, (char*)arr + (right * size), size);
  23.         memcpy(b, (char*)arr + (pivot * size), size);
  24.         while (right > pivot && comp(a, b) > -1) { // while (right > pivot && arr[right] >= arr[pivot])
  25.             -- right;
  26.             memcpy(a, (char*)arr + (right * size), size);
  27.         }
  28.         memcpy(a, (char*)arr + (left * size), size);
  29.         memcpy(b, (char*)arr + (right * size), size);
  30.         if (comp(a, b) == 1) { // if (arr[left] > arr[right])
  31.             if (left == pivot) {
  32.                 __qswap(arr, left, arr, right, size);
  33.                 pivot = right;
  34.             }
  35.             else if (right == pivot) {
  36.                 __qswap(arr, right, arr, left, size);
  37.                 pivot = left;
  38.             }
  39.             else {
  40.                 __qswap(arr, left, arr, right, size);
  41.             }
  42.         }
  43.         memcpy(a, (char*)arr + (left * size), size);
  44.         memcpy(b, (char*)arr + (right * size), size);
  45.         if (comp(a, b) == 0) // if (arr[left] == arr[right])
  46.             break;
  47.     }
  48.     if (n == 2) {
  49.         memcpy(a, (char*)arr + (0 * size), size);
  50.         memcpy(b, (char*)arr + (1 * size), size);
  51.         if (comp(a, b) == 1) // if (arr[0] > arr[1])
  52.             __qswap(arr, 0, arr, 1, size);
  53.         free(a);
  54.         free(b);
  55.         return;
  56.     }
  57.     free(a);
  58.     free(b);
  59.     qs(arr, pivot, size, comp);
  60.     qs((char*)arr + (pivot * size), n - pivot, size, comp);
  61. }
RAW Paste Data