버블 정렬(Bubble sort)

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 정렬 방식이다.

바로 가까이(오른쪽)에 있는 두 숫자를 비교해서 더 작은 숫자를 앞으로 보내주는 것을 반복 연산하는 것이다.

예시 문제:

1 10 5 4 3 2 9 6 7 8

해당 숫자를 오름차순으로 정렬하시오.

1번째 실행:
1 10 5 4 3 2 9 6 7 8
-> 1과 10 비교. 변화 없음.
-> 10과 5 비교. 5를 앞으로 -> 1 5 10 4 3 2 9 6 7 8
-> 10과 4 비교. 4를 앞으로 -> 1 5 4 10 3 2 9 6 7 8
-> 10과 3 비교. 3을 앞으로 -> 1 5 4 3 10 2 9 6 7 8
-> 10과 2 비교. 2을 앞으로 -> 1 5 4 3 2 10 9 6 7 8
-> 10과 9 비교. 9을 앞으로 -> 1 5 4 3 2 9 10 6 7 8
-> 10과 6 비교. 6을 앞으로 -> 1 5 4 3 2 9 6 10 7 8
-> 10과 7 비교. 7을 앞으로 -> 1 5 4 3 2 9 6 7 10 8
-> 10과 8 비교. 8을 앞으로 -> 1 5 4 3 2 9 6 7 8 10

2번째 실행:
1 5 4 3 2 9 6 7 8 10
-> 1과 5 비교. 변화 없음.
-> 5와 4 비교. 4를 앞으로. -> 1 4 5 3 2 9 6 7 8 10
-> 5와 3 비교. 3을 앞으로. -> 1 4 3 5 2 9 6 7 8 10
-> 5와 2 비교. 2을 앞으로. -> 1 4 3 2 5 9 6 7 8 10
-> 5와 9 비교. 변화 없음.
-> 9와 6 비교. 6을 앞으로. -> 1 4 3 2 5 6 9 7 8 10
-> 9와 7 비교. 7을 앞으로. -> 1 4 3 2 5 6 7 9 8 10
-> 9와 8 비교. 8을 앞으로. -> 1 4 3 2 5 6 7 8 9 10

3번째 실행:
1 4 3 2 5 6 7 8 9 10
-> 1과 4비교. 변화 없음.
-> 4와 3비교. 3을 앞으로. -> 1 3 4 2 5 6 7 8 9 10
-> 4와 2비교. 2를 앞으로. -> 1 3 2 4 5 6 7 8 9 10
-> 이후 비교 수행 하지만 변화 없음.

4번째 실행:
1 3 2 4 5 6 7 8 9 10
-> 1과 3 비교. 변화 없음.
-> 3과 2 비교. 2를 앞으로 -> 1 2 3 4 5 6 7 8 9 10
-> 이후 비교 수행 하지만 변화 없음.
오름차순 정렬 완료.

#include<stdio.h>

int main(){
	int i, j, temp;
    int arr[10] = {1, 10, 5, 4, 3, 2, 9, 6, 7, 8};
	for(i=0;i<10;i++){
    	for(j=0;j<10;j++){
        	if(arr[j]>arr[j+1]){
            	temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
for(i=0;i<10;i++){printf("%d", arr[i]);}
return 0;
}

def bubble_sort:
	

이 정렬 방식은 가장 가까운 인덱스 끼리 비교하여 점차 큰 수를 오른쪽으로 이동시킨다. 그러면, 가장 큰 수가 맨 뒤로 옮겨져 정렬하게 된다. 이를 반복문 수행 횟수로 보면,
10 , 9, 8, 7, 6, ... 3, 2, 1 번 수행하게 되는 것이다.(숫자가 위의 풀이처럼 4번째 수행에서 정렬되어도 계속 실행된다.)
이는 10(10+1)/2 = 55 로 등차수열 합과 같다.

따라서, 시간 복잡도 또한 선택 정렬과 똑같이 O(N^2) 이 되는 것이다.

그러나, 버블 정렬은 정렬 알고리즘 중...가장 효율성이 떨어지는 방법이다.
선택 정렬보다 효율성이 떨어진다. 그 이유는, 선택정렬에 비해서 컴퓨터가 연산에 처리해야하는 경우의 수가 많기 때문이다. 선택 정렬의 경우 min 선택과 해당 인덱스와의 비교(2번)만 처리하면 되지만, 버블 정렬의 경우 가까운 수와의 비교 연산을 여러번 해주어야 하기 때문이다.