[C++] Bubble Sort 버블 정렬

동작 원리

배열의 모든 인덱스를 돌며 정해진 규칙에 따라 자리를 바꿔 정렬

 

시간 복잡도

O(N^2)

 

// n - 1 + n - 2 + ... + 2 + 1 = n * (n - 1) / 2

 

과정

반복문을 통한 배열 방문 -> 인접한 두 값 비교 - > 기준에 적합할 시 자리바꿈

위 과정 반복

 

코드구현

#include <iostream>

using namespace std;

void swap(int& n1, int& n2) {
    int temp = n1;
    n1 = n2;
    n2 = temp;
}

void bubbleSort(int arr[], int size) {
    for(int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - 1 - i; j++) {
            if(arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}