Skip to content

Instantly share code, notes, and snippets.

@NathanEpstein
Created February 3, 2015 18:40
Show Gist options
  • Save NathanEpstein/9f5872c6452ba15cde9d to your computer and use it in GitHub Desktop.
Save NathanEpstein/9f5872c6452ba15cde9d to your computer and use it in GitHub Desktop.
bubble sort and merge sort in C++
#include <vector>
#include <math.h>
#include <iostream>
using namespace std;
//BUBBLE SORT IMPLEMENTATION
vector<double> bubbleSort(vector<double> arr){
bool pass = false; //have we passed through the array without a swap?
double temp;
while (!pass){
pass = true;
for (int i=0; i<arr.size()-1; i++){
if (arr[i] > arr[i+1]){
pass = false;
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
}
return arr;
}
//MERGE SORT IMPLEMENTATION
// merge function
vector<double> merge(vector<double> left,vector<double> right){
int leftCount = 0;
int rightCount = 0;
vector<double> results;
bool useLeft;
for (int i=0; i<left.size()+right.size();i++){
if(leftCount<left.size()){
if(rightCount<right.size()){
useLeft = (left[leftCount] < right[rightCount]);
}
else{
useLeft = true;
}
}
else{
useLeft = false;
}
if (useLeft){
results.push_back(left[leftCount]);
if (leftCount < left.size()){
leftCount++;
}
}
else{
results.push_back(right[rightCount]);
if (rightCount<right.size()){
rightCount++;
}
}
}
return results;
}
// merge sort function
vector<double> mergeSort(vector<double> arr){
if (arr.size() <= 1){
return arr;
}
int len = floor(arr.size()/2);
vector<double> left(arr.begin(), arr.begin()+len);
vector<double> right(arr.begin()+len, arr.end());
return merge(mergeSort(left),mergeSort(right));
}
// CALL SORT FUNCTIONS
int main(){
//initialize a vector with random elements
vector<double> myVec;
for (int j=0; j<20; j++){
myVec.push_back(rand() % 100);
}
//sort with both methods
vector<double> msort = mergeSort(myVec);
vector<double> bsort = bubbleSort(myVec);
//check for equality
cout<< (msort == bsort)<<'\n';
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment