fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3.  
  4. #include "Timer.h"
  5.  
  6. using std::cin;
  7. using std::cout;
  8. using std::vector;
  9. using std::endl;
  10. using std::ostream;
  11. using std::ios;
  12.  
  13. struct node{
  14.   int data;
  15.   node* next;
  16.   node* prev;
  17. } *head=0;
  18.  
  19. ostream& operator<<(ostream& out, node* n){
  20.     if ( ! n ){
  21. 		return out;
  22. 	}
  23. 	out<<n->data;
  24. 	if ( n->next ){
  25. 		out<<", ";
  26. 		out<<n->next;
  27. 	}
  28. 	else{
  29. 		out<<endl;
  30. 	}
  31. 	return out;
  32. }
  33.  
  34. typedef node*& node_pref_t;
  35.  
  36. vector<int> data;
  37.  
  38. /**
  39.   * insertion sort, linked list
  40.   */
  41.  
  42. void i_sort(node_pref_t head){
  43. 	//empty list?
  44. 	if ( !head ) return ;
  45.  
  46. 	// start looking for out of order element.
  47. 	node* current = head;
  48. 	while( current->next ){
  49. 		// if out of order, current->next will change place.
  50. 		// rearrange current->next immideately
  51. 		if ( current->data <= current->next->data ){
  52. 			// in order, hopefully for performance the default case.
  53. 			// just move to the	next node
  54. 			current = current->next;
  55. 		}else{
  56. 			// out of order
  57. 			node* extract_this_node = current->next;
  58. 			// complete chain , current->next might here be 0
  59. 			current->next = extract_this_node->next;
  60. 			if( current->next ){
  61. 				current->next->prev= current;
  62. 			}
  63. 			// loop back to correct position
  64. 			node* insertion_point = extract_this_node->prev;
  65. 			// important to check insertion_point is valid before checking the 
  66. 			// contents. Short-circuit evaluation FTW!
  67. 			while( insertion_point && 
  68. 				   insertion_point->data > extract_this_node->data ){
  69. 				insertion_point = insertion_point->prev;
  70. 			}
  71. 			if ( insertion_point ){
  72. 				// rearrange pointers, order matters here A <-> B
  73. 				// will become A<->I<->B
  74. 				extract_this_node->next = insertion_point->next; // I->B
  75. 				extract_this_node->next->prev = extract_this_node; // I<->B
  76. 				insertion_point->next = extract_this_node; // A->I
  77. 				extract_this_node->prev = insertion_point; // A<->I
  78. 			}else{
  79. 				// found the beginning of the list, insert at head.
  80. 				head->prev = extract_this_node;
  81. 				extract_this_node->next = head;
  82. 				head = extract_this_node;
  83. 				head->prev = 0;
  84. 			}
  85. 		}
  86. 	}
  87. }
  88. /**
  89.   * insertion sort, vector
  90.   */
  91. void i_sort(vector<int> & data){
  92. 	for(int i = 0; i < data.size()-1; i++){
  93. 		// out of order element?
  94. 		if ( data[i] > data[i+1] ){
  95. 			// pull data[i+1] to its proper position.
  96. 			// the value needs to be stored.
  97. 			int insert_value = data[i+1];
  98. 			int insert_index = i;
  99. 			// stop at index 0 or at the correct spot.
  100. 			while( insert_index && data[insert_index] > insert_value ){
  101. 				// move up value in list to make room for insertion.
  102. 				data[insert_index+1] = data[insert_index];
  103. 				insert_index--;
  104. 			}
  105. 			data[insert_index+1] = data[insert_index];
  106. 			data[insert_index] = insert_value;
  107. 		}
  108. 	}
  109. }
  110.  
  111. int main(){
  112. 	cout.setf(ios::fixed, ios::floatfield);
  113. 	cout.precision(6);
  114. 	node* next;
  115. 	// fill structures from console
  116. 	int value;
  117. 		while(cin>>value){
  118. 		data.push_back(value);
  119. 		if ( !head){
  120. 			head = new node{value, 0, 0};
  121. 			next = head;
  122. 		}else{
  123. 			next->next = new node{value,0, next};
  124. 			next = next->next;
  125. 		}
  126. 	}
  127. 	// sort
  128. 	// and time
  129. 	Timer timer;
  130. 	timer.start();
  131.  
  132. 	i_sort(head);
  133. 	timer.stop();
  134. 	// debugging check: cout<<head;
  135. 	double list_time = timer.get_duration();
  136. 	// record time linked list
  137. 	cout<<list_time<<endl;
  138.  
  139. 	timer.start();
  140. 	i_sort(data);
  141. 	timer.stop();
  142. 	double vector_time = timer.get_duration();
  143. 	// record time vector
  144. 	cout<<vector_time<<endl;
  145. 	return 0;
  146. }
  147.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:4:19: fatal error: Timer.h: No such file or directory
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/VfeKP8
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

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!