[알고리즘] 정렬알고리즘 #3 버블정렬 (Bubble Sort)

📍 버블정렬 (Bubble Sort) 🫧

버블 정렬은 정렬되는 모습이 버블버블하다.

앞에서부터 계속 바로 이웃한 원소와 스왑스왑스왑스왑해서 맨 뒤에 가장 큰 원소를 넣어둔다. 그 다음엔 다시 처음부터 스왑스왑스왑스왑해서 n-2에도 가장 큰 원소를 넣는다. 계속 이웃한 원소에서 swap을 진행하면서 나아가기 때문에 전반적으로 앞에서부터 뒤까지 정렬이 조금씩 조금씩 진행되고, 정확한 정렬은 맨 뒤에서부터 하나씩 진행된다. 전반적으로 정렬이 되기 때문에 버블버블하게 거품이 올라오는 듯하다.

 

📍 C++ 구현 코드

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for(int i=n-2;i>=0;i--){
            for(int j=0;j<=i;j++){
                if(nums[j]>nums[j+1]){
                    swap(nums[j],nums[j+1]);
                }
            }
        }
        return nums;
    }
};

https://leetcode.com/problems/sort-an-array/ 에서 위의 코드를 실행시킬 수 있습니다. (testcase는 통과하지만 시간초과 발생)

 

📍 코드 동작 원리

인덱스 j를 기준으로 생각하면 편하다. 0부터 n-2까지 스왑스왑, 0부터 n-3까지 스왑스왑, 0부터 n-4까지 스왑스왑, ..., 0부터 0까지 스왑을 하는 것이다. 뒤에서부터 가장 큰 원소 순서대로 정렬된다.

 

📍 시간복잡도(time complexity)

O(n^2)을 따른다.

 

📍 Stable / In-Place

버블 정렬은 Stable한 알고리즘이다. 또한 추가적인 메모리를 필요로 하지 않는 In-Place 알고리즘이다.

 

---

 

간단하면서도 약간 헷갈리기도 하고 어쨌든 버블버블 귀엽다. 작년에 들었던 자료구조 시간에 버블정렬을 시각화한 것을 본 적이 있는데 그걸 떠올리면 이해가 쉬운 것 같다.