정렬 - 버블 정렬(bubble sort)

1. 버블 정렬(Bubble Sort) 란?

 🖐 인접한 데이터 두개를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

▲ 눈으로 보기

 

2. 단순하게 생각하기

👉 데이터의 갯수보다 한 번 작게 비교

👉 앞의 데이터가 더 크다면 swap !

data = [4, 1]

for idx in range(len(data) - 1):
	if data[idx] > data[idx+1]:
    	data[idx], data[idx+1] = data[idx+1], data[idx]

# 출력 결과: [1, 4]

👉 슈도코드

Bubble(a, N)
    for i : N-1 -> 1
         jor j : 0 -> i-1
             if a[j] > a[j+1]
                 a[j] <-> a[j+1]

 

3. 알고리즘 구현

✍  n개의 리스트가 있는 경우 최대 n-1번 반복

✍  한 번 반복할 때마다 뒤에서 하나씩 결정됨 ( 가장 큰 숫자 결정 -> 그 다음 큰 숫자 결정 -> ,,, )

✍  만약 교환이 한번도 일어나지 않으면 다 정렬된 것 ( 더 이상 반복할 필요 X )

def bubble(data):
    for t in range(len(data)-1):
        swap = False
        for idx in range(len(data) - t - 1):  # 뒤에서 부터 숫자가 하나씩 결정되므로 t를 빼줌
            if data[idx] > data[idx + 1]:
                data[idx], data[idx + 1] = data[idx + 1], data[idx]  # 스왑 !
                swap = True
        
        if swap == False: # 루프에서 스왑이 일어나지 않았다면 break!
            break
    return data
    
    bubble([9, 7, 5, 3, 1])
    # 출력 결과: [1, 3, 5, 7, 9]

 

4. 복잡도

👉 반복문이 두 개  O(n**2)

👉 완전 정렬되어 있는 상태라면 최선은 O(n) /  최악의 경우 n*(n-1) / 2