fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <ctime>
  4.  
  5. using namespace std;
  6.  
  7. struct node
  8. {
  9. 	double key;
  10. 	node* next;
  11.  
  12. 	node(double _key, node* _next) : key(_key), next(_next) {}
  13. };
  14.  
  15. struct nodeQ // for MergeSort
  16. {
  17. 	node* head;
  18. 	node* tail;
  19. 	nodeQ* next;
  20.  
  21. 	nodeQ(node* _head, node* _tail, nodeQ* _next) : head(_head), tail(_tail), next(_next) {}
  22. };
  23.  
  24. void AddToFront(node*& head, node*& tail, double x)
  25. {
  26. 	head = new node(x, head);
  27. 	if (!head->next)
  28. 		tail = head;
  29. }
  30.  
  31. void Print(node* head, string info = "", string separator = " ", string prefix = "[", string postfix = "]\n")
  32. {
  33. 	cout << info << prefix;
  34. 	string sep = "";
  35. 	while (head)
  36. 	{
  37. 		cout << sep << head->key;
  38. 		sep = separator;
  39. 		head = head->next;
  40. 	}
  41. 	cout << postfix;
  42. }
  43.  
  44. void PrintLists(nodeQ* qhead, string info = "")
  45. {
  46. 	cout << info;
  47. 	if (!qhead)
  48. 		return;
  49. 	nodeQ* tmp = qhead;
  50. 	do
  51. 	{
  52. 		Print(tmp->head);
  53. 		tmp = tmp->next;
  54. 	} while (tmp != qhead);
  55. }
  56.  
  57. void RemoveList(node*& head)
  58. {
  59. 	node* tmp;
  60. 	while (tmp = head)
  61. 	{
  62. 		head = head->next;
  63. 		delete(tmp);
  64. 	}
  65. }
  66.  
  67. void ShiftToEnd(node*& head1, node*& head, node*& tail)
  68. {
  69. 	if (!head1)
  70. 		return;
  71.  
  72. 	node* tmp = head1;
  73. 	head1 = head1->next;
  74. 	tmp->next = nullptr;
  75.  
  76. 	if (!head)
  77. 	{
  78. 		head = tail = tmp;
  79. 		return;
  80. 	}
  81. 	tail->next = tmp;
  82. 	tail = tmp;
  83. }
  84.  
  85.  
  86. void SplitList(nodeQ*& qhead, node*& head) // for MergeSort
  87. {
  88. 	while (head)
  89. 	{
  90. 		node* tmphead = nullptr;
  91. 		node* tmptail = nullptr;
  92.  
  93. 		double lastkey;
  94. 		do
  95. 		{
  96. 			lastkey = head->key;
  97. 			ShiftToEnd(head, tmphead, tmptail);
  98. 		} while (head && lastkey <= head->key);
  99.  
  100. 		nodeQ* tmp = new nodeQ(tmphead, tmptail, nullptr);
  101. 		if (qhead)
  102. 		{
  103. 			tmp->next = qhead->next;
  104. 			qhead->next = tmp;
  105. 		}
  106. 		else
  107. 			qhead = tmp->next = tmp;
  108.  
  109. 		cout << endl;
  110. 		Print(head, "Not splitted part:\n");
  111. 		PrintLists(qhead, "Splitted parts:\n");
  112. 	}
  113. }
  114.  
  115. void Merge(node* head1, node* tail1, node* head2, node* tail2, node*& head, node*& tail) // for MergeSort
  116. {
  117. 	while (head1&&head2)
  118. 		if (head1->key < head2->key)
  119. 			ShiftToEnd(head1, head, tail);
  120. 		else
  121. 			ShiftToEnd(head2, head, tail);
  122. 	if (head1)
  123. 	{
  124. 		tail->next = head1;
  125. 		tail = tail1;
  126. 	}
  127. 	else if (head2)
  128. 	{
  129. 		tail->next = head2;
  130. 		tail = tail2;
  131. 	}
  132. }
  133.  
  134. void SelectionSort(node*& head)
  135. {
  136. 	node* headS = NULL;
  137.  
  138. 	while (head)
  139. 	{
  140. 		node** pMax = &head;
  141. 		node** tmp = &(head->next);
  142.  
  143. 		while (*tmp)
  144. 		{
  145. 			if ((*tmp)->key >= (*pMax)->key)
  146. 				pMax = tmp;
  147. 			tmp = &((*tmp)->next);
  148. 		}
  149.  
  150. 		node* max = *pMax;
  151. 		*pMax = (*pMax)->next;
  152.  
  153. 		max->next = headS;
  154. 		headS = max;
  155. 	}
  156.  
  157. 	head = headS;
  158. }
  159.  
  160. void InsertionSort(node*& head)
  161. {
  162. 	node* headS = NULL;
  163.  
  164. 	while (head)
  165. 	{
  166. 		node* front = head;
  167. 		head = head->next;
  168.  
  169. 		node** tmp = &headS;
  170. 		while (*tmp && (*tmp)->key < front->key)
  171. 			tmp = &((*tmp)->next);
  172.  
  173. 		front->next = *tmp;
  174. 		*tmp = front;
  175. 	}
  176.  
  177. 	head = headS;
  178. }
  179.  
  180. void MergeSort(node*& head, node*& tail)
  181. {
  182. 	if (!head)
  183. 		return;
  184.  
  185. 	cout << "\n------------------------ SPLITTING ------------------------\n";
  186. 	nodeQ* qhead = nullptr;
  187. 	SplitList(qhead, head);
  188.  
  189. 	cout << "\n------------------------ MERGING ------------------------\n";
  190. 	while (qhead->next != qhead)
  191. 	{
  192. 		node* tmphead = nullptr;
  193. 		node* tmptail = nullptr;
  194. 		Merge(qhead->head, qhead->tail, qhead->next->head, qhead->next->tail, tmphead, tmptail);
  195.  
  196. 		nodeQ* tmp = qhead->next;
  197. 		qhead->next = tmp->next;
  198. 		delete tmp;
  199.  
  200. 		qhead->head = tmphead;
  201. 		qhead->tail = tmptail;
  202. 		qhead = qhead->next;
  203.  
  204. 		cout << endl;
  205. 		PrintLists(qhead, "Splitted parts:\n");
  206. 	}
  207.  
  208. 	head = qhead->head;
  209. 	tail = qhead->tail;
  210. 	delete qhead;
  211. }
  212.  
  213. int main(void)
  214. {
  215. 	node* head = nullptr;
  216. 	node* tail = nullptr;
  217.  
  218. 	srand((unsigned)time(nullptr));
  219.  
  220. 	int N = 20;
  221. 	for (int i = 0; i < N; i++)
  222. 		AddToFront(head, tail, rand() % 20);
  223. 	Print(head, "Before sort:\n");
  224.  
  225. 	//SelectionSort(head);
  226. 	//InsertionSort(head);
  227. 	MergeSort(head, tail);
  228.  
  229. 	Print(head, "\nAfter  sort:\n");
  230.  
  231. 	RemoveList(head);
  232.  
  233. 	return 0;
  234. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Before sort:
[3 15 7 0 6 8 8 1 9 19 16 8 2 3 12 11 5 17 17 5]

------------------------ SPLITTING ------------------------

Not splitted part:
[7 0 6 8 8 1 9 19 16 8 2 3 12 11 5 17 17 5]
Splitted parts:
[3 15]

Not splitted part:
[0 6 8 8 1 9 19 16 8 2 3 12 11 5 17 17 5]
Splitted parts:
[3 15]
[7]

Not splitted part:
[1 9 19 16 8 2 3 12 11 5 17 17 5]
Splitted parts:
[3 15]
[0 6 8 8]
[7]

Not splitted part:
[16 8 2 3 12 11 5 17 17 5]
Splitted parts:
[3 15]
[1 9 19]
[0 6 8 8]
[7]

Not splitted part:
[8 2 3 12 11 5 17 17 5]
Splitted parts:
[3 15]
[16]
[1 9 19]
[0 6 8 8]
[7]

Not splitted part:
[2 3 12 11 5 17 17 5]
Splitted parts:
[3 15]
[8]
[16]
[1 9 19]
[0 6 8 8]
[7]

Not splitted part:
[11 5 17 17 5]
Splitted parts:
[3 15]
[2 3 12]
[8]
[16]
[1 9 19]
[0 6 8 8]
[7]

Not splitted part:
[5 17 17 5]
Splitted parts:
[3 15]
[11]
[2 3 12]
[8]
[16]
[1 9 19]
[0 6 8 8]
[7]

Not splitted part:
[5]
Splitted parts:
[3 15]
[5 17 17]
[11]
[2 3 12]
[8]
[16]
[1 9 19]
[0 6 8 8]
[7]

Not splitted part:
[]
Splitted parts:
[3 15]
[5]
[5 17 17]
[11]
[2 3 12]
[8]
[16]
[1 9 19]
[0 6 8 8]
[7]

------------------------ MERGING ------------------------

Splitted parts:
[5 17 17]
[11]
[2 3 12]
[8]
[16]
[1 9 19]
[0 6 8 8]
[7]
[3 5 15]

Splitted parts:
[2 3 12]
[8]
[16]
[1 9 19]
[0 6 8 8]
[7]
[3 5 15]
[5 11 17 17]

Splitted parts:
[16]
[1 9 19]
[0 6 8 8]
[7]
[3 5 15]
[5 11 17 17]
[2 3 8 12]

Splitted parts:
[0 6 8 8]
[7]
[3 5 15]
[5 11 17 17]
[2 3 8 12]
[1 9 16 19]

Splitted parts:
[3 5 15]
[5 11 17 17]
[2 3 8 12]
[1 9 16 19]
[0 6 7 8 8]

Splitted parts:
[2 3 8 12]
[1 9 16 19]
[0 6 7 8 8]
[3 5 5 11 15 17 17]

Splitted parts:
[0 6 7 8 8]
[3 5 5 11 15 17 17]
[1 2 3 8 9 12 16 19]

Splitted parts:
[1 2 3 8 9 12 16 19]
[0 3 5 5 6 7 8 8 11 15 17 17]

Splitted parts:
[0 1 2 3 3 5 5 6 7 8 8 8 9 11 12 15 16 17 17 19]

After  sort:
[0 1 2 3 3 5 5 6 7 8 8 8 9 11 12 15 16 17 17 19]
https://ideone.com/pb7FXG
language:
C++14 (gcc 8.3)
created:
5 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!