Advertisement
nezvers

Introsort with callbacks

Sep 2nd, 2021
1,202
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.28 KB | None | 0 0
  1. #include "stdio.h"
  2.  
  3. #include "math.h"
  4. #include "stdbool.h"
  5.  
  6. // IntroSort(data, size, set, swap, bigger, bigoreq)
  7. // bool(*bigoreq)(void*, void*)
  8. // bool(*bigger)(void*, void*)
  9. // void(*swap)(void*, void*)
  10. // void(*set)(void*, void*)
  11.  
  12. void InsertionSort(int* data, int count, void(*swap)(void*, void*), bool(*bigger)(void*, void*)) {
  13.     for (int i = 1; i < count; ++i){
  14.         int j = i;
  15.         while (j > 0){
  16.             if (bigger( &data[j - 1], &data[j])){
  17.                 swap(&data[j], &data[j - 1]);
  18.                 --j;
  19.             }
  20.             else{
  21.                 break;
  22.             }
  23.         }
  24.     }
  25. }
  26.  
  27. void MaxHeapify(int* data, int heapSize, int index, void(*swap)(void*, void*), bool(*bigger)(void*, void*)) {
  28.     int left = (index + 1) * 2 - 1;
  29.     int right = (index + 1) * 2;
  30.     int largest = 0;
  31.  
  32.     if (left < heapSize && bigger(&data[left], &data[index]) ){
  33.         largest = left;
  34.     }
  35.     else{
  36.         largest = index;
  37.     }
  38.  
  39.     if (right < heapSize && bigger(&data[right], &data[largest])){
  40.         largest = right;
  41.     }
  42.  
  43.     if (largest != index){
  44.         swap(&data[index], &data[largest]);
  45.  
  46.         MaxHeapify(data, heapSize, largest, swap, bigger);
  47.     }
  48. }
  49.  
  50. void HeapSort(int* data, int count, void(*swap)(void*, void*), bool(*bigger)(void*, void*)) {
  51.     int heapSize = count;
  52.  
  53.     for (int p = (heapSize - 1) / 2; p >= 0; --p){
  54.         MaxHeapify(data, heapSize, p, swap, bigger);
  55.     }
  56.  
  57.     for (int i = count - 1; i > 0; --i) {
  58.         swap(&data[i], &data[0]);
  59.  
  60.         --heapSize;
  61.         MaxHeapify(data, heapSize, 0, swap, bigger);
  62.     }
  63. }
  64.  
  65. int Partition(int* data, int left, int right, void(*set)(void*, void*), void(*swap)(void*, void*), bool(*bigoreq)(void*, void*)) {
  66.     void *pivot = &data[right];
  67.     int i = left;
  68.  
  69.     for (int j = left; j < right; ++j){
  70.         if ( bigoreq(pivot, &data[j])){
  71.             swap(&data[j], &data[i]);
  72.             i++;
  73.         }
  74.     }
  75.     set(&data[right], &data[i]);
  76.     set(&data[i], pivot);
  77.     return i;
  78. }
  79.  
  80. void QuickSortRecursive(int* data, int left, int right, void(*set)(void*, void*), void(*swap)(void*, void*), bool(*bigoreq)(void*, void*)){
  81.     if (left < right){
  82.         int q = Partition(data, left, right, set, swap, bigoreq);
  83.         QuickSortRecursive(data, left, q - 1, set, swap, bigoreq);
  84.         QuickSortRecursive(data, q + 1, right, set, swap, bigoreq);
  85.     }
  86. }
  87.  
  88.  
  89. void IntroSort(void* data, int count, void(*set)(void*, void*), void(*swap)(void*, void*), bool(*bigger)(void*, void*), bool(*bigoreq)(void*, void*)) {
  90.     int partitionSize = Partition(data, 0, count - 1, set, swap, bigoreq);
  91.  
  92.     if (partitionSize < 16) {
  93.         InsertionSort(data, count, swap, bigoreq);
  94.     }
  95.     else if (partitionSize >(2 * log(count))){
  96.         HeapSort(data, count, swap, bigger);
  97.     }
  98.     else{
  99.         QuickSortRecursive(data, 0, count - 1, set, swap, bigoreq);
  100.     }
  101. }
  102.  
  103.  
  104. void set(void* a, void* b){
  105.     *(int*)a = *(int*)b;
  106. }
  107.  
  108. void swap(void* a, void* b){
  109.     int temp = *(int*)a;
  110.     *(int*)a = *(int*)b;
  111.     *(int*)b = temp;
  112. }
  113.  
  114. bool bigger(void* a, void* b){
  115.     return *(int*)a > *(int*)b;
  116. }
  117.  
  118. bool bigoreq(void* a, void* b){
  119.     return *(int*)a >= *(int*)b;
  120. }
  121.  
  122. void print_array(int *data, int size){
  123.     for (int i = 0; i < size; i++){
  124.         printf("%d, ", data[i]);
  125.     }
  126.     printf("\n");
  127. }
  128.  
  129. int main(){
  130.     int data[] = { -1, 25, -58964, 8547, -119, 0, 78596 };
  131.     IntroSort(data, 7, set, swap, bigger, bigoreq);
  132.     print_array((void*)data, sizeof(data) / sizeof(data[0]));
  133.     return 0;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement