[알고리즘] 정렬 - 버블정렬

1. 개념

맨 앞부터 시작. 첫 번째 원소와 그 다음 원소를 비교. 만약 다음 원소가 더 작으면 교환하고 그렇지 않으면 그대로 둠. 그리고 두 번째 원소, 세 번째 원소로 가서 앞에서 진행했던 거를 반복. 이걸 한 싸이클 진행하면 맨 뒤에 가장 큰 수가 남게 되고 그 수는 고정이 된다.

위와 같은 과정을 반복하면 버블정렬이 완료됨

 

2. 특징

1) 장점

• 안정 정렬이 가능함(같은 원소가 있어도 같은 원소의 상대적인 위치, 즉 누가 앞에 있던 거고 누가 뒤에 있던 건지가 바뀌지 않음)
• 구현이 쉬움
• 추가 메모리가 거의 필요하지 않음

2) 단점

• 교환 과정이 많음
• 시간 복잡도가 O(n2)

 

3. 시간복잡도

1) 비교 횟수

항목의 개수가 n이면 (n-1) + (n-2) + (n-3)... + 1 만큼 비교를 한다. 이는 n(n-1)/2 가 된다.

2) 교환 횟수

한 번 비교를 할 때 교환을 하는 경우가 있고, 교환을 안 하는 경우가 있다. 즉 교환 확률은 50프로이다. 그래서 평균 교환 횟수는 n(n-1)/4가 된다.

3) 이동 횟수

교환 할 때 마다 3번의 이동이 이루어지기 때문에 (아래 코드에서 temp 선언부터 아래 3줄) 3n(n-1)/4 번의 교환이 이루어진다.

 

3가지를 고려했을 때 총 시간복잡도는 O(n2)이 된다.

 

4. 코드

// 오름차순
int[] nums = {2, 4, 3, 1, 5};
for(int i = 0; i<nums.length; i++){
    for(int j = 0; j<nums.length - i - 1; j++){
        if(nums[j] > nums[j+1]){
            int temp = nums[j];
            nums[j] = nums[j+1];
            nums[j+1] = temp;
        }
    }
}

5. 적합한 때

1) 배열의 크기가 작을 때

 

6. 관련 문제

백준 2750

백준 1377

GitHub - Lee-Min-Jung/coding_test_practice