알고리즘 : 버블 정렬(Bubble sort)

정렬(sorting) 은?

• 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
• 프로그램 작성 시에 자주 필요로 함

 

버블 정렬(bubble sort)은?

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

출처 : 위키피디아

데이터가 4개일 때 버블 정렬 알고리즘 방식 예시

data_list = [1, 8, 4, 3]
 - 1차 로직 적용
   - 1과 8 비교, 자리바꿈 없음 [1, 8, 4, 3]
   - 8과 4 비교, 자리바꿈 있음 [1, 4, 8, 3]
   - 8과 3 비교, 자리바꿈 있음 [1, 4, 3, 8]

 - 2차 로직 적용
   - 1과 4 비교, 자리바꿈 없음 [1, 4, 3, 8]
   - 4와 3 비교, 자리바꿈 있음 [1, 3, 4, 8]
   - 4와 8 비교, 자리바꿈 없음 [1, 3, 4, 8]

- 3차 로직 적용
   - 1과 3 비교, 자리바꿈 없음 [1, 3, 4, 8]
   - 3과 4 비교, 자리바꿈 없음 [1, 3, 4, 8]
   - 4와 8 비교, 자리바꿈 없음 [1, 3, 4, 8]

 

알고리즘 구현

• n개의 리스트가 있는 경우 최대 n-1번의 로직을 적용
• 로직을 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정됨
• 로직을 적용할 때 한 번도 데이터가 교환된 적이 없다면 이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요가 없음(로직이 경우에 따라 일찍 끝날 수도 있기 때문)

리스트 데이터	1회 로직 적용	2회 로직 적용	3회 로직 적용	4회 로직 적용
10, 1, 8	1, 8, 10	-
10, 8, 1	8, 1, 10	1, 8, 10
1, 10, 3, 2	1, 3, 2, 10	1, 2, 3, 10	-
10, 3, 2, 1	3, 2, 1, 10	2, 1, 3, 10	1, 2, 3, 10
10, 8, 5, 3, 1	8, 5, 3, 1, 10	5, 3, 1, 8, 10	3, 1, 5, 8, 10	1, 3, 5, 8, 10
5, 8, 3, 10, 4	5, 3, 8, 4, 10	3, 5, 4, 8, 10	3, 4, 5, 8, 10	-
1, 10, 3, 2, 8	1, 3, 2, 8, 10	1, 2, 3, 8, 10	-	-

1. for num in range(len(data_list)) 반복

2. swap = 0 (교환이 되었는지 확인하는 변수)

3. 반복문 안에서 for index in range(len(data_list) - num - 1) n - 1번 반복해야 함

4. 반복문 안의 반복문 안에서 if data_list[index] > data_list[index + 1] 이면

5. data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index]

6. swap += 1

7. 반복문 안에서 if swap == 0 이면 break

 

def bubblesort(data):
	for index in range(len(data) - 1):
    	swap = False
        for index2 in range(len(data) - index - 1):
        	if data[index2] > data[index2 + 1]:
            	data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
            if swap == False
            	break
        return data
        

import random
data_list = random.sample(range(100), 50)
print(bubblesort(data_list))

 

알고리즘 분석

• 반복문이 두 개 O(𝑛²)
   최악의 경우, n*(n−1)/2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)