알고리즘 - 버블 정렬

버블 정렬은 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘입니다.

 

4

1

9

2

5

7

3

 

위와 같은 배열이 있을 때, 오름차순으로 배열을 정렬한다고 생각해봅시다.

 

이렇게 두 수를 비교하면서 작은 수면 자리를 교환 하고 계속 비교해 나갑니다.

 

계속 비교하면 가장 작은 수인 1이 제일 앞으로 오게 되고

다음으로 작은 수들이 오도록 비교, 교환 해줘야하고, 이 배열의 크기가 7이기 때문에

이러한 비교, 교환을 총 7 - 1 = 6번 해줘야 오름차순으로 정렬됩니다.

 

---

이제 코드로 살펴보겠습니다.

 

def bubble_sort(a) -> None:
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
        print(''.join(str(x)))


print('버블 정렬')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

print('정렬 전')
print(''.join(str(x)))
print('정렬 후')
bubble_sort(x)

 

bubble_sort 함수를 볼 때

첫 번째 for문은 비교 교환 횟수고, 두 번째 for문은 비교를 통한 교환 작업입니다.

두 번째 for문에서 n-1부터 시작하는 이유는 배열의 끝에서부터 비교, 교환을 하기 때문입니다.

print문을 통해 각 비교, 교환 사이클이 끝난 뒤 배열을 출력하게 했습니다.

 

결과

결과를 출력해보면 최종적으로 오름차순으로 정렬된 것을 확인할 수 있습니다.

 

---

 

만약 위 와 같은 배열이 있다고 했을 때 1, 2는 버블 정렬을 통해 교환이 진행된 상태입니다.

이제 세 번째 자리에 올 숫자를 버블 정렬 해야되는데

배열을 보시면 이미 오름차순으로 잘 정렬돼있어서 교환이 발생하지 않을 것이고

그럼 비교, 교환을 저 진행할 필요가 없습니다.

 

위와 같은 일이 있을 수도 있기 때문에 코드를 바꿔보겠습니다.

 

def bubble_sort(a) -> None:
    n = len(a)
    for i in range(n - 1):
        print(f'사이클 {i}')
        exchange = 0
        for j in range(n - 1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                exchange += 1
        if exchange == 0:
            break
        print(''.join(str(x)))

print('버블 정렬')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

print('정렬 전')
print(''.join(str(x)))
print('\n정렬 후')
bubble_sort(x)

 

처음 코드와 다른 점은 exchange 변수를 추가하고 조건 문을 넣은 것입니다.

매 사이클이 시작할 때마다 exchange를 0으로 초기화시키고

한 사이클 안에서 교환이 일어날 때마다 exchange에 + 1 해줍니다.

 

만약 교환이 진행되지 않았다면 exchange 값은 0일 것이고 for문을 종료시켜줍니다.

 

결과

 

결과 화면을 보면 제대로 for문이 멈춘 것을 확인할 수 있습니다.

 

---

위 와 비슷한 다른 경우도 있습니다.

 

위 배열은 아직 버블 정렬을 하지 않은 배열입니다.

배열을 보면 1, 2, 4는 이미 오름차순으로 정렬돼 있어서 굳이 정렬할 필요가 없고

10, 7, 12, 11 << 이 4개의 숫자만 해주면 됩니다.

 

코드를 바꿔봅시다.

 

def bubble_sort(a) -> None:
    n = len(a)
    l = 0
    while l < n - 1:
        last = n - 1
        for j in range(n - 1, l, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                last = j
                print(''.join(str(x)))
        l = last

print('버블 정렬')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

print('정렬 전')
print(''.join(str(x)))
print('\n정렬 후')
bubble_sort(x)

 

이번에는 l, last 변수가 생겼고 첫 for문이 사라지고 while문으로 대신했습니다.

l 변수는 어디까지 비교, 교환을 진행할지에 대한 범위라고 생각하시면 됩니다.

last 변수는 교환이 끝날 때마다 오른쪽 인덱스 값을 넣어줍니다.

한 사이클이 끝나면 l을 last로 바꿔주고 for문의 범위를 축소 시켜줍니다.

사이클이 시작하기 전에 last = n - 1을 해주기 때문에

교환이 일어나지 않으면 ㅣ = last(n-1)이기 때문에 while문은 종료됩니다.

 

결과 화면

 

결과 화면을 보면 제대로 종료되는 것을 확인할 수 있습니다.

 

---

마지막으로

7

1

2

3

4

5

6

이러한 배열이 있을 때 

맨 앞에 있는 7을 제외한 나머지 숫자들은 이미 오름차순으로 정렬이 돼있습니다.

하지만 7이 맨 끝에 있기 때문에 7은 한 사이클에 하나씩 뒤로 이동하게 됩니다.

 

이럴 때 사용하는 방법이 셰이커 정렬입니다.

이번 코드에서는 홀수 사이클일 때는 가장 작은 원소를 맨 앞으로 보내고

짝수 사이클 일 때는 가장 큰 원소를 맨 뒤로 보내겠습니다.

 

def bubble_sort(a) -> None:
    left = 0
    right = len(a) - 1
    last = right
    n = len(a)
    while left < right:
        for j in range(right, left, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                last = j
        left = last
        print('작은 수')
        print(''.join(str(a)))

        for j in range(left, right):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                last = j
        right = last
        print('큰 수')
        print(''.join(str(a)))

print('버블 정렬')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

print('정렬 전')
print(''.join(str(x)))
print('\n정렬 후')
bubble_sort(x)

 

right는 배열의 가장 끝이고 left는 배열의 가장 앞입니다. 

첫 번째 for문은 작은 수를 앞으로 이동시킵니다.

그래서 교환을 하면 last 값에 인덱스를 넣어주고

첫 사이클이 끝나면 가장 작은 수의 뒤 인덱스가 j이므로 left = last로 해줍니다.

 

두 번째 for문은 큰 수를 뒤로 이동시킵니다.

그래서 기존 if문과 다르게 앞의 수가 아닌 두의 수와 비교를 해서 교환합니다.

last값과 right값을 바꿔주는 것은 위 이유와 비슷하므로 생략하겠습니다.

 

만약 두 개의 for문에서 모두 교환이 일어나지 않는다면 left와 right 값이 같게되고

while문은 종료됩니다.

 

결과 화면

 

결과 화면을 보면 더 이상 교환이 일어나지 않아 종료된 것을 확인할 수 있습니다.