Bubble Sort

• Time : O(n^2)
• Space : O(1)

// best : O(n) time | O(1) space
// avg : O(n^2) time | O(1) space
// worst : O(n^2) time | O(1) space
vector<int> bubbleSort(vector<int> array) {
    int n = array.size();
    bool sorted = false;
    for(int i = 0; i < n and !sorted; i++) {
        sorted = true;
        for(int j = 0; j + 1 < n - i; j++) {
            if(array[j] > array[j + 1]) {
                swap(array[j], array[j + 1]);
                sorted = false;
            }
        }
    }
    return array;
}