[알고리즘] 버블 정렬(bubble sort)

margarin·2021년 2월 21일
0

알고리즘

목록 보기
10/13

시간복잡도

O(n²)

공간복잡도

input 배열을 제외하고 추가로 할당한 메모리는 O(1)이다.

설명

  1. 배열의 첫번째 숫자부터 시작한다.
  2. 현재 위치의 값이 다음 위치의 값보다 크면, 서로 위치를 바꾼다.
  3. 현재 위치를 1 증가하면서 마지막 위치까지 1~2번을 반복한다.
  4. 1~3번을 배열의 모든 수에 대해 순서대로 수행한다.
    (수정중)

code

#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] << " ";
    }
}
profile
화이팅 🥹

0개의 댓글