fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <sstream>
  5. using namespace std;
  6.  
  7. vector<float> merge(vector<float> firstHalf, vector<float> secondHalf){
  8.     vector<float> combined;
  9.     for(int i = firstHalf.size() + secondHalf.size(); i > 0;  i--){//merge two vectors
  10.         if(firstHalf.back() > secondHalf.back() && !firstHalf.empty()){
  11.             combined.push_back(firstHalf.back());
  12.             firstHalf.pop_back();
  13.         }else if(!secondHalf.empty()){
  14.             combined.push_back(secondHalf.back());
  15.             secondHalf.pop_back();
  16.         }
  17.     }
  18.     vector<float> revCombined;//reverse merged vectors. Vectors don't have pop_front and I didn't want to use lists.
  19.  
  20.     for(int i = 0; i < combined.size(); i++){
  21.         revCombined.push_back(combined[combined.size()-i-1]);
  22.     }
  23.     return revCombined;
  24. }
  25.  
  26. vector<float> mergeSort(vector<float> &inputArray){//for example [9, 8, 1] as input
  27.     if(inputArray.size() > 1){
  28.         vector<float> firstHalf;
  29.         vector<float> secondHalf;
  30.  
  31.         for(int i = 0; i < inputArray.size()/2; i++){//auto round the input array because size() returns int
  32.             firstHalf.push_back(inputArray[i]);
  33.         }//first half = [9, 8]
  34.  
  35.         for(int i = inputArray.size()/2; i < inputArray.size(); i++){
  36.             secondHalf.push_back(inputArray[i]);
  37.         }//second half = [1]
  38.  
  39.         return merge(mergeSort(firstHalf), mergeSort(secondHalf));
  40.     }
  41.     else{
  42.         return inputArray;
  43.     }
  44. }
  45.  
  46.  
  47.  
  48.  
  49.  
  50. vector<string> split(string str, char delimiter) {
  51.     vector<string> internal;
  52.     stringstream ss(str); // Turn the string into a stream.
  53.     string tok;
  54.  
  55.     while(getline(ss, tok, delimiter)) {
  56.         internal.push_back(tok);
  57.     }
  58.  
  59.     return internal;
  60. }
  61. vector<float> floatVectorInput(){
  62.     string inputString;
  63.     getline(cin, inputString);
  64.  
  65.     vector<string> stringArray = split(inputString, ' ');
  66.  
  67.     vector<float> array; 
  68.     for(int i = 0; i < stringArray.size(); i++){
  69.         array.push_back(stof(stringArray[i]));
  70.     }
  71.     return array;   
  72. }
  73.  
  74.  
  75. int main(){
  76.     cout << "Array to sort (separate by spaces): " << endl;
  77.     vector<float> inputArray = floatVectorInput();
  78.  
  79.     vector<float> sorted = mergeSort(inputArray);
  80.  
  81.     cout << endl << "Sorted Array:" << endl;    
  82.     for(int i = 0; i < sorted.size(); i++){
  83.         cout << sorted[i];
  84.         if(i == sorted.size()-1){
  85.             cout << endl << endl;
  86.         }else{
  87.             cout << ", ";
  88.         }
  89.     }
  90.     return 0;
  91. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
32 1 4 7 3 12 9 2 21 56 44
stdout
copy 
Array to sort (separate by spaces): 

Sorted Array:
1, 2, 3, 4, 7, 9, 12, 21, 32, 44, 56
https://ideone.com/rWbAsl
language:
C++14 (gcc 8.3)
created:
7 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!