fork download
copy 
  1. #include <stdbool.h>
  2. #include <stddef.h>
  3. #include <stdint.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include <time.h>
  8.  
  9. int int_compar(const void *a, const void *b) {
  10.     // Cast pointers to integers
  11.     int int_a = *(const int *)a;
  12.     int int_b = *(const int *)b;
  13.  
  14.     // Return comparison result without overflow
  15.     if (int_a < int_b) {
  16.         return -1;
  17.     } else if (int_a > int_b) {
  18.         return 1;
  19.     } else {
  20.         return 0;
  21.     }
  22. }
  23.  
  24. void quicksort_internal(void *base, size_t size, size_t start, size_t end, int (*compar)(const void *, const void *)) {
  25.     // Base case: If the range is invalid or trivially sorted
  26.     if (start >= end - 1 || end == 0) {
  27.         return;
  28.     }
  29.  
  30.     // Treat base as a byte array for pointer arithmetic
  31.     uint8_t *array = (uint8_t *)base;
  32.  
  33.     // Choosing a pivot: Set pivot as the last element in the range
  34.     size_t pivot = end - 1;
  35.  
  36.     // Randomly select a "swapper" index within the range and swap it with the pivot
  37.     size_t swapper = start + rand() % (end - start);
  38.     if (swapper != pivot) {
  39.         uint8_t temp[size];
  40.         memcpy(temp, array + swapper * size, size);
  41.         memcpy(array + swapper * size, array + pivot * size, size);
  42.         memcpy(array + pivot * size, temp, size);
  43.     }
  44.  
  45.     // Partitioning
  46.     size_t swappoint = start; // Tracks the position of smaller elements
  47.     for (size_t examinepoint = start; examinepoint < pivot; examinepoint++) {
  48.         if (compar(array + examinepoint * size, array + pivot * size) < 0) {
  49.             // Swap element at examinepoint with element at swappoint
  50.             uint8_t temp[size];
  51.             memcpy(temp, array + examinepoint * size, size);
  52.             memcpy(array + examinepoint * size, array + swappoint * size, size);
  53.             memcpy(array + swappoint * size, temp, size);
  54.             swappoint++;
  55.         }
  56.     }
  57.  
  58.     // Place the pivot in its correct position by swapping with the swappoint
  59.     if (swappoint != pivot) {
  60.         uint8_t temp[size];
  61.         memcpy(temp, array + pivot * size, size);
  62.         memcpy(array + pivot * size, array + swappoint * size, size);
  63.         memcpy(array + swappoint * size, temp, size);
  64.     }
  65.  
  66.     // Recursive sorting of the left and right partitions
  67.     quicksort_internal(base, size, start, swappoint, compar);         // Left partition
  68.     quicksort_internal(base, size, swappoint + 1, end, compar);      // Right partition
  69. }
  70.  
  71.  
  72. // This is the exact same format as qsort, but you
  73. // must NOT use qsort to implement this.
  74. // You probably want to create a quicksort_internal function that
  75. // you call in order to properly implement quicksort.
  76. void quicksort_c(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
  77. {
  78.     if (!base || size == 0 || nmemb <= 1 || !compar) {
  79.         return;
  80.     }
  81.     uint8_t *array = (uint8_t *)base;
  82.  
  83.     bool is_sorted = true;  // Assume the array is sorted unless proven otherwise
  84.     // Check if the array is pre-sorted or all-same
  85.     for (size_t i = 1; i < nmemb; i++) {
  86.         if (compar(array + (i - 1) * size, array + i * size) > 0) {
  87.             is_sorted = false;  // Found an unsorted pair
  88.             break;
  89.         }
  90.     }
  91.  
  92.     // If the array is not sorted, proceed with quicksort
  93.     if (!is_sorted) {
  94.         quicksort_internal(base, size, 0, nmemb, compar);
  95.     } else {
  96.         printf("Array is already sorted. Skipping quicksort.\n");
  97.     }
  98. }
  99.  
  100. int main() {
  101.  
  102.     // Seed for randomness
  103.     srand((unsigned)time(NULL));
  104.  
  105.  
  106.     int data[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};  // Reverse-sorted data
  107.     size_t nmemb = sizeof(data) / sizeof(data[0]);
  108.     quicksort_c(data, nmemb, sizeof(int), int_compar);
  109.  
  110.     // Print sorted array
  111.     printf("Sorted array:\n");
  112.     for (size_t i = 0; i < nmemb; i++) {
  113.         printf("%d ", data[i]);
  114.     }
  115.     printf("\n");
  116.  
  117.     printf("\nPathological pre-sorted test\n");
  118.     nmemb=10000;
  119.     int sorted_data[nmemb];
  120.     for (size_t i = 0; i < nmemb; i++) {
  121.         sorted_data[i] = i;
  122.     }
  123.     clock_t start_time = clock();
  124.     quicksort_c(sorted_data, nmemb, sizeof(int), int_compar);
  125.     clock_t stop_time = clock();
  126.     double total_time = (double)(stop_time - start_time) / CLOCKS_PER_SEC * 1e6; // in microseconds
  127.     printf("Pathological pre-sorted time: %.2f microseconds\n", total_time);
  128.  
  129.  
  130.     printf("\nPathological all-equal test\n");
  131.     int equal_data[nmemb];
  132.     for (size_t i = 0; i < nmemb; i++) {
  133.         equal_data[i] = 42;
  134.     }
  135.     start_time = clock();
  136.     quicksort_c(equal_data, nmemb, sizeof(int), int_compar);
  137.     stop_time = clock();
  138.     total_time = (double)(stop_time - start_time) / CLOCKS_PER_SEC * 1e6; // in microseconds
  139.     printf("Pathological all-equal time: %.2f microseconds\n", total_time);
  140.  
  141.  
  142.     printf("\nRandomized test\n");
  143.     int random_data[nmemb];
  144.     for (size_t i = 0; i < nmemb; i++) {
  145.         random_data[i] = rand() % 1000;
  146.     }
  147.     start_time = clock();
  148.     quicksort_c(random_data, nmemb, sizeof(int), int_compar);
  149.     stop_time = clock();
  150.     total_time = (double)(stop_time - start_time) / CLOCKS_PER_SEC * 1e6; // in microseconds
  151.     printf("Randomized time: %.2f microseconds\n", total_time);
  152.  
  153.  
  154.     return 0;
  155. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sorted array:
1 2 3 4 5 6 7 8 9 10 

Pathological pre-sorted test
Array is already sorted. Skipping quicksort.
Pathological pre-sorted time: 0.00 microseconds

Pathological all-equal test
Array is already sorted. Skipping quicksort.
Pathological all-equal time: 0.00 microseconds

Randomized test
Randomized time: 2102.00 microseconds
https://ideone.com/xfvvhK
language:
C (gcc 8.3)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!