정렬 알고리즘 - Bubble

버블정렬(Bubble) 이란?

두 인접한 원소를 검사하여 정렬하는 방법이다.

시간복잡도는 O(n^2)으로 느리지만, 구현하기 매우 쉽다.

def bubble(array):
    print("bubble")
    for i in range(len(array)-1):
        for j in range(len(array)-1-i):
            if array[j] > array[j+1]:
                array[j],array[j+1] = array[j+1],array[j]

맨 앞 숫자부터 다음 숫자로 가면서 바로 뒤에 있는 숫자들과 비교하여, 뒤에 있는 숫자가 더 작을때마다 서로 교환하는 방식이다.

위 코드가 돌아가는 단계를 세세히 뜯으면 아래와 같다.

Array = [3,4,5,2,1] 일때

1번째 큰 루프 시작

1번째 숫자 3 비교 (1번째 숫자 == 0번 인덱스 숫자 일때)
3 > 4 : 뒤에 있는 숫자가 더 크다. 변화 없음

2번째 숫자 4 비교
4 < 5 : 뒤에 있는 숫자가 더 크다. 변화 없음

3번째 숫자 5 비교
5 > 2 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,4,2,5,1]

4번째 숫자 5 비교
5 > 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,4,2,1,5]

첫번째 큰 루프 끝. (for i)

2번째 큰 루프 시작
Array = [3,4,2,1,5]

1번째 숫자 3 비교
3 < 4 : 뒤에 있는 숫자가 더 크다. 변화 없음

2번째 숫자 4 비교
4 < 2 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,2,4,1,5]

3번째 숫자 4 비교
4 < 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,2,1,4,5]

두번째 큰 루프 끝. 5까지 비교하지 않는 이유는 첫번째 큰 루프때 제일 큰 숫자 자리가 정해진다. 같은 원리로 두번째 루프가 끝나면 2번째로 큰 숫자 자리가 정해진다.

3번째 큰 루프 시작
Array = [3,2,1,4,5]

1번째 숫자 3 비교
3 < 2 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [2,3,1,4,5]

2번째 숫자 3 비교
3 < 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [2,1,3,4,5]

3번째 큰 루프 종료.

4번째 큰 루프 시작
Array = [2,1,3,4,5]

1번째 숫자 2 비교
2 < 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [1,2,3,4,5]

4번째 큰 루프 종료.

큰 루프 종료