O(n²)
input 배열을 제외하고 추가로 할당한 메모리는 O(1)이다.
#include <iostream>
#include <vector>
using namespace std;
void bubble_sort(vector<int> &nums) {
for (int i = 0; i < nums.size() -1; i++) {
for (int j = 0; j < nums.size() -1 - i; j++){
if (nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}
int main() {
vector<int> nums = {2,4,8,1,9,5,3,7,6};
bubble_sort(nums);
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
}