fork download
copy 
  1. // Quick Sort example
  2. // For input array
  3. // 2 8 7 1 3 5 6 4
  4. //
  5. #include <stdio.h>
  6. #define IPSIZE 8
  7.  
  8. // To enable debug messages uncomment #define
  9. // #define DEBUG 1
  10.  
  11. #ifdef DEBUG
  12. #  define D(x) x
  13. #else
  14. #  define D(x)
  15. #endif
  16.  
  17. void quicksort(int arr[], int p, int r); 
  18. int partition(int arr[], int p, int r); 
  19. void swap(int i, int j); 
  20.  
  21. int arr[IPSIZE] = {2, 8, 7, 1, 3, 5, 6, 4}; 
  22.  
  23. int main()
  24. {
  25. 	int i = 0;
  26.     printf("Input array\n");
  27.     for (i = 0; i <= IPSIZE - 1; i++) {
  28.         printf("%d ", arr[i]);
  29.     }   
  30.     printf("\n\n");
  31.  
  32.     quicksort(arr, 0, IPSIZE - 1); 
  33.  
  34.     printf("Sorted output\n");
  35.     for (i = 0; i <= IPSIZE - 1; i++) {
  36.         printf("%d ", arr[i]);
  37.     }   
  38.     printf("\n");
  39.  
  40.     return 0;
  41. }
  42.  
  43. void quicksort(int arr[], int p, int r)
  44. {
  45.     if (p < r) {
  46.         int pivotIndx = partition(arr, p, r);
  47.  
  48.         quicksort(arr, p, pivotIndx - 1);
  49.         quicksort(arr, pivotIndx + 1, r);
  50.     }
  51. }
  52.  
  53. int partition(int arr[], int p, int r)
  54. {
  55.     int pivot = arr[r];
  56.     int i = p - 1;
  57.     int j = 0;
  58.  
  59.     // Debug messages
  60.     D(printf("\n############\n"));
  61.     D(printf("Partition\n"));
  62.     D(printf("p=%d, r=%d, pivot=%d\n", p, r, pivot));
  63.     D(printf("Elements\n"));
  64.     for (j = p; j <= r; j++) {
  65.         D(printf("%d ", arr[j]));
  66.     }
  67.     D(printf("\n"));
  68.  
  69.     for (j = p; j <= r - 1; j++) {
  70.         if (arr[j] <= pivot) {
  71.             i++;
  72.             swap(i, j);
  73.         }
  74.     }
  75.  
  76.     swap(i + 1, r);
  77.  
  78.     D(printf("Elements after partition\n"));
  79.     for (j = p; j <= r; j++) {
  80.         D(printf("%d ", arr[j]));
  81.     }
  82.     D(printf("\n"));
  83.  
  84.     return (i + 1);
  85. }
  86.  
  87. void swap(int i, int j)
  88. {
  89.     int temp = arr[i];
  90.     arr[i] = arr[j];
  91.     arr[j] = temp;
  92. }
  93.  
Success #stdin #stdout 0s 2248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input array
2 8 7 1 3 5 6 4 

Sorted output
1 2 3 4 5 6 7 8
https://ideone.com/qGqmLR
QuickSort
language:
C (gcc 8.3)
created:
10 years 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!