fork download
copy 
  1. void i_sort(node_pref_t head){
  2.     //empty list?
  3. 	if ( !head ) return ;
  4.  
  5. 	// start looking for out of order element.
  6. 	node* current = head;
  7. 	while( current->next ){
  8. 		// if out of order, current->next will change place.
  9. 		// rearrange current->next immideately
  10. 		if ( current->data <= current->next->data ){
  11. 			// in order, hopefully for performance the default case.
  12. 			// just move to the	next node
  13. 			current = current->next;
  14. 		}else{
  15. 			// out of order
  16. 			node* extract_this_node = current->next;
  17. 			// complete chain , current->next might here be 0
  18. 			current->next = extract_this_node->next;
  19. 			if( current->next ){
  20. 				current->next->prev= current;
  21. 			}
  22. 			// loop back to correct position
  23. 			node* insertion_point = extract_this_node->prev;
  24. 			// important to check insertion_point is valid before checking the 
  25. 			// contents. Short-circuit evaluation FTW!
  26. 			while( insertion_point && 
  27. 				   insertion_point->data > extract_this_node->data ){
  28. 				insertion_point = insertion_point->prev;
  29. 			}
  30. 			if ( insertion_point ){
  31. 				// rearrange pointers, order matters here A <-> B
  32. 				// will become A<->I<->B
  33. 				extract_this_node->next = insertion_point->next; // I->B
  34. 				extract_this_node->next->prev = extract_this_node; // I<->B
  35. 				insertion_point->next = extract_this_node; // A->I
  36. 				extract_this_node->prev = insertion_point; // A<->I
  37. 			}else{
  38. 				// found the beginning of the list, insert at head.
  39. 				head->prev = extract_this_node;
  40. 				extract_this_node->next = head;
  41. 				head = extract_this_node;
  42. 				head->prev = 0;
  43. 			}
  44. 		}
  45. 	}
  46. }
  47. /**
  48.   * insertion sort, vector
  49.   */
  50. void i_sort(vector<int> & data){
  51. 	for(int i = 0; i < data.size()-1; i++){
  52. 		// out of order element?
  53. 		if ( data[i] > data[i+1] ){
  54. 			// pull data[i+1] to its proper position.
  55. 			// the value needs to be stored.
  56. 			int insert_value = data[i+1];
  57. 			int insert_index = i;
  58. 			// stop at index 0 or at the correct spot.
  59. 			while( insert_index && data[insert_index] > insert_value ){
  60. 				// move up value in list to make room for insertion.
  61. 				data[insert_index+1] = data[insert_index];
  62. 				insert_index--;
  63. 			}
  64. 			data[insert_index+1] = data[insert_index];
  65. 			data[insert_index] = insert_value;
  66. 		}
  67. 	}
  68. }
  69.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:13: error: variable or field ‘i_sort’ declared void
prog.cpp:1:13: error: ‘node_pref_t’ was not declared in this scope
stdout
copy 
Standard output is empty
https://ideone.com/cmvEBQ
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!