fork download
copy 
  1.  
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4.  
  5. typedef struct Node Node;
  6.  
  7. struct Node {
  8.     int data;
  9.     Node *next;
  10. };
  11.  
  12. void print(const Node *node)
  13. {
  14.     while (node) {
  15.         printf("%d -> ", node->data);
  16.         node = node->next;
  17.     }
  18.  
  19.     puts("$");
  20. }
  21.  
  22. /*
  23.  *      Sort linked list with quicksort; return new tail
  24.  */
  25.  
  26. Node *quicksort(Node **head)
  27. {
  28.     // base cases: empty list and single node
  29.  
  30.     if (*head == NULL) return NULL;
  31.     if ((*head)->next == NULL) return *head;
  32.  
  33.     // partition with *head as pivot
  34.  
  35.     Node *lt = NULL;        // less than pivot
  36.     Node *ge = NULL;        // greater than or equal to pivot
  37.  
  38.     Node *node = (*head)->next;
  39.  
  40.     while (node) {
  41.         Node *next = node->next;
  42.  
  43.         if (node->data < (*head)->data) {
  44.             node->next = lt;
  45.             lt = node;
  46.         } else {
  47.             node->next = ge;
  48.             ge = node;
  49.         }
  50.  
  51.         node = next;
  52.     }
  53.  
  54.     // quick-sort recursively
  55.  
  56.     Node *ltail = quicksort(&lt);
  57.     Node *gtail = quicksort(&ge);
  58.  
  59.     // rearrange lists: lt -> pivot -> ge
  60.  
  61.     (*head)->next = ge;
  62.  
  63.     if (gtail == NULL) gtail = *head;
  64.  
  65.     if (lt) {
  66.         ltail->next = *head;
  67.         *head = lt;
  68.     }
  69.  
  70.     return gtail;
  71. }
  72.  
  73. int main(void)
  74. {
  75.     Node node[10];
  76.     Node *head = NULL;
  77.  
  78.     for (unsigned i = 0; i < 10; i++) {
  79.         node[i].data = (7 + 3*i) % 10;
  80.         node[i].next = head;
  81.         head = &node[i];
  82.     }
  83.  
  84.     print(head);
  85.     quicksort(&head);
  86.     print(head);    
  87.  
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0s 5360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4 -> 1 -> 8 -> 5 -> 2 -> 9 -> 6 -> 3 -> 0 -> 7 -> $
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> $
https://ideone.com/927LhE
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!