#include <iostream>
#include <vector>
#include <chrono>
#include "math.h"
using namespace std;
// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass
vector<int> bubbleSort(vector<int> arr)
{
long len = arr.size();
vector<int> items(arr);
for (long end = len; end > 1; end--) {
bool swapped = false;
for (long j = 1; j < end; j++) {
if (items[j] < items[j - 1]) {
int tmp = items[j];
items[j] = items[j - 1];
items[j - 1] = tmp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
return items;
}
vector<int> items = { 4, 1, 5, 3, 2 };
vector<int>sortItems = bubbleSort(items);
// sortItems is {1, 2, 3, 4, 5}
for (int i : sortItems) cout << i << ", ";
cout << endl;
// *** simplified speed test ***
items = vector<int>(200, 0);
for (int i = 0; i < items.size(); i++) {
items[i] = items.size() - 1 - i;
}
int count = 10000;
auto start = chrono::steady_clock::now();
for (int i = 0; i < count; i++) {
bubbleSort(items);
}
long milliseconds = chrono::duration_cast<chrono::milliseconds>(
chrono::steady_clock::now() - start).count();
cout << milliseconds << " milliseconds";
// about 2210 milliseconds