fork(2) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <ctime>
  4. #include <cstdlib>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8. int selectionSort(vector<int> &v);
  9. int insertionSort(vector<int> &v);
  10. void printVector(vector<int> &v);
  11.  
  12. int main()
  13. {
  14.  
  15.     vector<int> myVector;       // to hold 100 values in a vector
  16.     int numCount, numCount2=0;         // to hold comparison numbers
  17.  
  18.     // Get random numbers for vector
  19.     srand(time(0));
  20.     for(int i=0; i<100; i++)
  21.     {
  22.     myVector.push_back(rand()%90+10);
  23.     }
  24.  
  25.     // Make copy of myVector values into myVector2 to use for insertion sorting
  26.     vector<int> myVector2(myVector);
  27.  
  28.     // Print Original Vector
  29.     cout << "Original vector: ";
  30.     printVector(myVector);
  31.  
  32.     // Call selectionSort to sort the original vector and return # of comparisons into numCount
  33.     numCount = selectionSort(myVector);
  34.  
  35.  
  36.     // Print the original vector sorted by selection sort
  37.     cout << endl << endl << "Vector After Selection Sort: ";
  38.     printVector(myVector);
  39.  
  40.     // Print # of comparisons for selection sort
  41.     cout << endl << endl << "Number of comparisons: numcount= " << numCount;
  42.  
  43.     // Call insertionSort to sort the 2nd original vector copy and return # of comparisons into numCount
  44.     numCount2 = insertionSort(myVector2);
  45.  
  46.     // Print the original vector sorted by insertion sort
  47.     cout << endl << endl << "Vector after Insertion Sort: ";
  48.     printVector(myVector2);
  49.  
  50.     // Print # of comparisons for insertion sort
  51.     cout << endl << endl << "Number of comparisons numCount2: " << numCount2;
  52.  
  53.     // Format
  54.     cout << endl << endl;
  55.     cout << "-----------------------------------------------------------------------------" << endl;
  56.  
  57.     // Reverse the original vector after being sorted by selectionSort(myVector)
  58.     reverse(myVector.begin(), myVector.end());
  59.  
  60.     // Reverse the 2nd vector copy to be used for insertion sorting
  61.     reverse(myVector2.begin(), myVector2.end());
  62.  
  63.     // Print original vector in reverse order. Note: it is not sorted at this time.
  64.     cout << endl << "Vector in reverse order: ";
  65.     printVector(myVector);
  66.  
  67.     // Call selectionSort to sort the reverse vector and return the # of comparisons into numCount
  68.     numCount = selectionSort(myVector);
  69.  
  70.     // Print reverse original vector sorted by selectionSort
  71.     cout << endl << endl << "Vector after Selection Sort: ";
  72.     printVector(myVector);
  73.  
  74.     // Print # of comparisons used by selectionSort
  75.     cout << endl << endl << "Number of comparisons: " << numCount;
  76.  
  77.     // Call insertionSort to sort the 2nd copy of reverse vector and return # of comparisons into numCount
  78.     numCount = insertionSort(myVector2);
  79.  
  80.     // Print the 2nd copy of reverse vector sorted by insertionSort
  81.     cout << endl << endl << "Vector after Insertion Sort: ";
  82.     printVector(myVector2);
  83.  
  84.     // Print # of comparisons used by insertionSort
  85.     cout << endl << endl << "Number of comparisons: " << numCount;
  86.     cout << endl << endl;
  87.     return 0;
  88. }
  89.  
  90. /*************************************************************************************************
  91. Function definition: the void printVector function takes a vector as its arguments and prints the
  92. contents of the vector by using a C++11 range based for-loop.
  93. **************************************************************************************************/
  94. void printVector(vector<int> &v)
  95. {
  96.  
  97.     for (int val: v)
  98.     {
  99.         cout << val << " ";
  100.     }
  101. }
  102.  
  103. /*******************************************************************************************
  104. Function definition: the selectionSort function takes a vector as its arguments and sorts
  105. the contents of the vector in ascending order with a selection sort algorithm. The function
  106. will return the counter for number of comparisons it makes.
  107. ********************************************************************************************/
  108.  
  109. int selectionSort(vector<int> &v)
  110. {
  111.     //pos_min is short for position of min
  112. 	int pos_min,temp, counter=0;
  113.  
  114. 	for (int i=0; i < v.size()-1; i++)
  115. 	{
  116. 	    pos_min = i;//set pos_min to the current index of array
  117.  
  118. 		for (int j=i+1; j < v.size(); j++)
  119. 		{
  120.         //counter++; // tracking # of comparisons
  121. 		if (v[j] < v[pos_min])
  122.         {
  123.         pos_min=j;
  124.         counter++;  // tracking # of comparisons
  125.         }
  126.  
  127.  
  128. 	//pos_min will keep track of the index that min is in, this is needed when a swap happens
  129. 		}
  130.  
  131. 	//if pos_min no longer equals i than a smaller value must have been found, so a swap must occur
  132.         if (pos_min != i)
  133.         {
  134.  
  135.         temp = v[i];
  136.         v[i] = v[pos_min];
  137.         v[pos_min] = temp;
  138.         }
  139.  
  140. 	}
  141. return counter;
  142.  
  143. }
  144.  
  145. /*********************************************************************************************
  146. Function definition: the insertionSort function takes a vector as its arguments and sorts the
  147. contents of the vector in ascending order with an insertion sort algorithm. The function will
  148. return the counter for number of comparisons it makes.
  149. *********************************************************************************************/
  150. int insertionSort (vector<int> &v){
  151. 	 	int j, temp, counter = 0;
  152.  
  153. 	for (int i = 1; i < v.size(); i++){
  154. 		j = i;
  155.  
  156. 		while (++counter && j > 0 && v[j] < v[j-1]){
  157. 		//while ( j > 0 && v[j] < v[j-1]){
  158. 			  temp = v[j];
  159. 			  v[j] = v[j-1];
  160. 			  v[j-1] = temp;
  161. 			  j--;
  162.  
  163.  
  164. 			  }
  165. 			  //cout << "counter=  " << " -  " << counter;
  166. 		}
  167. return counter;
  168. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin 
Standard input is empty
stdout 
Original vector: 53 56 87 56 35 31 71 84 58 42 95 76 51 67 83 54 20 88 28 20 87 42 10 70 17 36 70 60 53 64 11 97 72 88 15 97 71 38 81 29 71 38 96 74 95 79 28 67 67 98 78 16 93 40 39 10 67 61 61 72 25 24 69 88 65 36 47 36 65 29 18 88 57 14 62 15 45 43 72 65 93 12 33 86 43 24 87 62 75 10 34 53 24 56 41 79 44 78 68 99 

Vector After Selection Sort: 10 10 10 11 12 14 15 15 16 17 18 20 20 24 24 24 25 28 28 29 29 31 33 34 35 36 36 36 38 38 39 40 41 42 42 43 43 44 45 47 51 53 53 53 54 56 56 56 57 58 60 61 61 62 62 64 65 65 65 67 67 67 67 68 69 70 70 71 71 71 72 72 72 74 75 76 78 78 79 79 81 83 84 86 87 87 87 88 88 88 88 93 93 95 95 96 97 97 98 99 

Number of comparisons: numcount= 293

Vector after Insertion Sort: 10 10 10 11 12 14 15 15 16 17 18 20 20 24 24 24 25 28 28 29 29 31 33 34 35 36 36 36 38 38 39 40 41 42 42 43 43 44 45 47 51 53 53 53 54 56 56 56 57 58 60 61 61 62 62 64 65 65 65 67 67 67 67 68 69 70 70 71 71 71 72 72 72 74 75 76 78 78 79 79 81 83 84 86 87 87 87 88 88 88 88 93 93 95 95 96 97 97 98 99 

Number of comparisons numCount2: 2656

-----------------------------------------------------------------------------

Vector in reverse order: 99 98 97 97 96 95 95 93 93 88 88 88 88 87 87 87 86 84 83 81 79 79 78 78 76 75 74 72 72 72 71 71 71 70 70 69 68 67 67 67 67 65 65 65 64 62 62 61 61 60 58 57 56 56 56 54 53 53 53 51 47 45 44 43 43 42 42 41 40 39 38 38 36 36 36 35 34 33 31 29 29 28 28 25 24 24 24 20 20 18 17 16 15 15 14 12 11 10 10 10 

Vector after Selection Sort: 10 10 10 11 12 14 15 15 16 17 18 20 20 24 24 24 25 28 28 29 29 31 33 34 35 36 36 36 38 38 39 40 41 42 42 43 43 44 45 47 51 53 53 53 54 56 56 56 57 58 60 61 61 62 62 64 65 65 65 67 67 67 67 68 69 70 70 71 71 71 72 72 72 74 75 76 78 78 79 79 81 83 84 86 87 87 87 88 88 88 88 93 93 95 95 96 97 97 98 99 

Number of comparisons: 1517

Vector after Insertion Sort: 10 10 10 11 12 14 15 15 16 17 18 20 20 24 24 24 25 28 28 29 29 31 33 34 35 36 36 36 38 38 39 40 41 42 42 43 43 44 45 47 51 53 53 53 54 56 56 56 57 58 60 61 61 62 62 64 65 65 65 67 67 67 67 68 69 70 70 71 71 71 72 72 72 74 75 76 78 78 79 79 81 83 84 86 87 87 87 88 88 88 88 93 93 95 95 96 97 97 98 99 

Number of comparisons: 4995
https://ideone.com/oybDbD
language:
C++14 (clang 8.0)
created:
8 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!