[Python 자료구조] 버블 정렬 (bubble sort)

💡 Bubble sort ( 버블 정렬 )

버블 정렬은 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 한다

 

💡 설명

 

오름차순으로 먼저 정렬하려고 한다.

오른쪽 끝에 있는 두 원소 7과 8 중 작은 숫자를 좌측으로, 큰 숫자를 우측에 둔다. 

두 숫자는 7이 8보다 작으므로 교환할 필요가 없다.

오름차순으로 정렬 하려 했기 때문에 현재 같은 상황에서도 교환할 필요가 없다. 

이렇게 반복하여 필요한 경우 교환하는 것이 버블 정렬의 기본기이다.

 

 

 

만약 교환해야 되는 대상이 있는 경우 5, 1 ( 4번째)를 보게 되면 1과 5가 바뀌는 경우를 볼 수 있다.

1, 6 / 1. 4 오름차순으로 정렬 한다면 1, 2, 3, 4 ... 8 까지 나와야 하기 때문에 loop 를 돌면서

정렬이 끝날때 까지 반복한다.

 

 

💡 코드

def bubble_sort_search(data):
    
    size = len(data)

    for i in range(size): 
        for j in range(size - 1):
            if data[j] > data[j + 1]:
                data[j], data[j+1] = data[j+1], data[j]
            print ('i=', i, 'j=',j, data)
        
data = [10, 8, 7, 6, 9]
bubble_sort_search(data)

def buubleSort(arr):
    
    size = len(arr)
    
    for _ in range(size):
        for j in range(size - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

arr = [64, 84, 58, 54, 32]
result = buubleSort(arr)
print(result)

 

💡 실행 시 풀이

i= 0 j= 0 [8, 10, 7, 6, 9]
i= 0 j= 1 [8, 7, 10, 6, 9]
i= 0 j= 2 [8, 7, 6, 10, 9]
i= 0 j= 3 [8, 7, 6, 9, 10]
i= 1 j= 0 [7, 8, 6, 9, 10]
i= 1 j= 1 [7, 6, 8, 9, 10]
i= 1 j= 2 [7, 6, 8, 9, 10]
i= 1 j= 3 [7, 6, 8, 9, 10]
i= 2 j= 0 [6, 7, 8, 9, 10]
i= 2 j= 1 [6, 7, 8, 9, 10]
i= 2 j= 2 [6, 7, 8, 9, 10]
i= 2 j= 3 [6, 7, 8, 9, 10]
i= 3 j= 0 [6, 7, 8, 9, 10]
i= 3 j= 1 [6, 7, 8, 9, 10]
i= 3 j= 2 [6, 7, 8, 9, 10]
i= 3 j= 3 [6, 7, 8, 9, 10]
i= 4 j= 0 [6, 7, 8, 9, 10]
i= 4 j= 1 [6, 7, 8, 9, 10]
i= 4 j= 2 [6, 7, 8, 9, 10]
i= 4 j= 3 [6, 7, 8, 9, 10]