fork download
copy 
  1. #include <iostream>
  2. #include <random>
  3.  
  4. struct Node
  5. {
  6.     int data;
  7.     Node *next;
  8.  
  9.     Node(int arg, Node *nxt = nullptr)
  10.         : data(arg), next(nxt)
  11.     {}
  12.  
  13.     Node(const Node&) = delete;
  14.     Node& operator =(const Node&) = delete;
  15. };
  16.  
  17. void print_nodes(const Node* lst)
  18. {
  19.     while (lst)
  20.     {
  21.         std::cout << lst->data << ' ';
  22.         lst = lst->next;
  23.     }
  24.     std::cout << '\n';
  25. }
  26.  
  27. void sort_nodes(Node*& head)
  28. {
  29.     Node *dst = NULL;
  30.     Node **psrc = &head;
  31.  
  32.     while (*psrc)
  33.     {
  34.         Node ** pdst = &dst;
  35.         while (*pdst && (*pdst)->data < (*psrc)->data)
  36.             pdst = &(*pdst)->next;
  37.  
  38.         Node *tmp = *psrc;
  39.         *psrc = (*psrc)->next;
  40.         tmp->next = *pdst;
  41.         *pdst = tmp;
  42.  
  43.         // print intermediate results
  44.         print_nodes(dst);
  45.     }
  46.  
  47.     *psrc = dst;
  48. }
  49.  
  50. int main()
  51. {
  52.     std::random_device rd;
  53.     std::default_random_engine rng(rd());
  54.     std::uniform_int_distribution<> dist(1,100);
  55.  
  56.     Node *lst = nullptr;
  57.     for (int i=0; i<15; ++i)
  58.         lst = new Node(dist(rng), lst);
  59.  
  60.     print_nodes(lst);
  61.     sort_nodes(lst);
  62. }
Success #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10 39 38 32 53 41 64 4 100 79 99 25 22 62 5 
10 
10 39 
10 38 39 
10 32 38 39 
10 32 38 39 53 
10 32 38 39 41 53 
10 32 38 39 41 53 64 
4 10 32 38 39 41 53 64 
4 10 32 38 39 41 53 64 100 
4 10 32 38 39 41 53 64 79 100 
4 10 32 38 39 41 53 64 79 99 100 
4 10 25 32 38 39 41 53 64 79 99 100 
4 10 22 25 32 38 39 41 53 64 79 99 100 
4 10 22 25 32 38 39 41 53 62 64 79 99 100 
4 5 10 22 25 32 38 39 41 53 62 64 79 99 100
https://ideone.com/TFfvuE
language:
C++14 (gcc 8.3)
created:
10 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!