daily pastebin goal
72%
SHARE
TWEET

Untitled

a guest Jan 16th, 2018 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "Sort.h"
  2.  
  3. void Partition(list &l, list &l1, list &l2, list &l3)
  4. {
  5.     node* p = l.PopFront();
  6.     l2.PushFront(p);
  7.     while (l.head)
  8.     {
  9.         p = l.PopFront();
  10.         if (p->key < l2.head->key) l1.PushFront(p);
  11.         if (p->key == l2.head->key) l2.PushFront(p);
  12.         if (p->key > l2.head->key) l3.PushFront(p);
  13.     }
  14. }
  15.  
  16. list QuickSort(list l)
  17. {
  18.     if (l.head == l.tail) return l;
  19.  
  20.     list l1, l2, l3;
  21.     Partition(l, l1, l2, l3);
  22.     l1 = QuickSort(l1);
  23.     l3 = QuickSort(l3);
  24.     if (l2.tail) l2.tail->next = l3.head;
  25.     else l2.head = l2.tail = l3.head;
  26.     if(l1.tail) l1.tail->next = l2.head;
  27.     else l1.head = l1.tail = l2.head;
  28.     l.head = l1.head;
  29.     if(l3.tail) l.tail = l3.tail;
  30.     else l.tail = l2.tail;
  31.  
  32.     return l;
  33. }
  34.  
  35. void PartitionEvenOdd(list &l, list &l1, list &l2)
  36. {
  37.     while (l.head)
  38.     {
  39.         node* p = l.PopFront();
  40.         if (p->key % 2 == 0) l1.PushFront(p);
  41.         else l2.PushFront(p);
  42.     }
  43. }
  44.  
  45. list QuickSortEvenOdd(list l)
  46. {
  47.     list l1, l2;
  48.     PartitionEvenOdd(l, l1, l2);
  49.     l1 = QuickSort(l1);
  50.     l2 = QuickSort(l2);
  51. //  cout << l1  << endl << l2 << endl;
  52.     if (l1.tail) l1.tail->next = l2.head;
  53.     else l1.tail = l1.head = l2.head;
  54.     if (l2.tail) l.tail = l2.tail;
  55.     else l.tail = l1.tail;
  56.     l.head = l1.head;
  57.  
  58.     return l;
  59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top