fork download
copy 
  1.  
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <string.h>
  5. #include <stdbool.h>
  6.  
  7. void print(const int *a, unsigned n)
  8. {
  9.     printf("[");
  10.  
  11.     for (unsigned i = 0; i < n; i++) {
  12.         if (i) printf(", ");
  13.         printf("%d", a[i]);
  14.     }
  15.  
  16.     printf("]\n");
  17. }
  18.  
  19. void swap(int *p, int *q)
  20. {
  21.     int t = *p; *p = *q; *q = t;
  22. }
  23.  
  24. int *partition(int *a, const int *end)
  25. {
  26.     int *pivot = a;
  27.  
  28.     for (int *p = pivot + 1; p < end; p++) {
  29.         if (*p < *pivot) {
  30.             swap(p, pivot + 1);
  31.             swap(pivot, pivot + 1);
  32.             pivot++;
  33.         }
  34.     }
  35.  
  36.     return pivot;
  37. }
  38.  
  39. void quicksort_rec(int *a, const int *end)
  40. {
  41.     if (a + 1 < end) {
  42.         int *pivot = partition(a, end);
  43.  
  44.         quicksort_rec(a, pivot);
  45.         quicksort_rec(pivot + 1, end);
  46.     }
  47. }
  48.  
  49. typedef struct Stack Stack;
  50.  
  51. enum {
  52.     MAX = 32
  53. };
  54.  
  55. struct Stack {
  56.     unsigned n;    
  57.     int *item[MAX];
  58. };
  59.  
  60. void push(Stack *st, int *p)
  61. {
  62.     if (st->n == MAX) {
  63.         fprintf(stderr, "Stack overflow!\n");
  64.         exit(1);
  65.     }
  66.  
  67.     st->item[st->n++] = p;
  68. }
  69.  
  70. int *pop(Stack *st)
  71. {
  72.     if (st->n == 0) {
  73.         fprintf(stderr, "Stack underflow!\n");
  74.         exit(1);
  75.     }
  76.  
  77.     return st->item[--st->n];
  78. }
  79.  
  80. bool isempty(const Stack *st)
  81. {
  82.     return (st->n > 0);
  83. }
  84.  
  85. void quicksort_iter(int *a, int *end)
  86. {
  87.     Stack stack = {0};
  88.  
  89.     push(&stack, a);
  90.     push(&stack, end);
  91.  
  92.     while (isempty(&stack)) {
  93.         end = pop(&stack);
  94.         a = pop(&stack);
  95.  
  96.         if (a + 1 < end) {
  97.             int *pivot = partition(a, end);
  98.  
  99.             push(&stack, a);
  100.             push(&stack, pivot);
  101.  
  102.             push(&stack, pivot + 1);
  103.             push(&stack, end);
  104.         }
  105.     }
  106. }
  107.  
  108. int main(void)
  109. {
  110.     int a[] = {1, 5, 3, 7, 8, 4, 9, 2, 3, 1, 4, 6, 8, 4};
  111.     int b[sizeof(a) / sizeof(*a)];
  112.     unsigned n = sizeof(a) / sizeof(*a);
  113.  
  114.     memcpy(b, a, sizeof(a));
  115.  
  116.     puts("recursive");
  117.  
  118.     print(a, n);
  119.     quicksort_rec(a, a + n);
  120.     print(a, n);
  121.  
  122.     puts("");
  123.     puts("iterative");
  124.  
  125.     print(b, n);
  126.     quicksort_iter(b, b + n);
  127.     print(b, n);
  128.  
  129.     return 0;
  130. }
  131.  
Success #stdin #stdout 0.01s 5500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
recursive
[1, 5, 3, 7, 8, 4, 9, 2, 3, 1, 4, 6, 8, 4]
[1, 1, 2, 3, 3, 4, 4, 4, 5, 6, 7, 8, 8, 9]

iterative
[1, 5, 3, 7, 8, 4, 9, 2, 3, 1, 4, 6, 8, 4]
[1, 1, 2, 3, 3, 4, 4, 4, 5, 6, 7, 8, 8, 9]
https://ideone.com/ujaIc5
language:
C (gcc 8.3)
created:
3 years ago
visibility:
secret

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!