[Python] 코딩 도장 - Bubble Sort

코딩 도장 사이트의 문제를 직접 풀어본 내용을 정리하여 올립니다.

코딩 도장에서 여러 문제를 확인할 수 있습니다.

난이도 순으로 차근차근 풀어보려 합니다.

---

[문제: Bubble Sort] - Lv.2

배열을 소팅하는 것은 초보 프로그래머에게 유명한 문제이며 전문적인 프로그래밍에서도 매우 중요하게 다루어 진다.

소팅은 비교에 기반을 두어 배열을 재 정렬하는 방법이다. 다음의 배열을 생각해 보자.

a = [3, 1, 4, 1, 5, 9, 2, 6]

우리는 이 배열을 크기 순서대로 정렬하고 싶다. (좌측의 요소는 우측의 요소보다 작거나 같아야 한다.)

수학적으로 표현하자면 다음과 같다.

i < j, a[i] <= a[j]

인덱스 i가 j보다 작은 경우 배열의 값인 a[i]는 a[j]값보다 작거나 같아야 한다.

버블소트(Bubble Sort)는 이러한 소팅을 하기 위한 가장 간단한 방법 중 하나이다.

1. 배열을 따라가며 인접한 쌍을 찾는다. (N개의 배열이 있을 경우 N-1개의 쌍이 존재하게 된다)

2. 만약 a[i] <= a[i+1] 을 만족하지 않는 쌍을 찾게 되면 두 개의 값을 서로 바꾸어준다. (Swap)

3. 더 이상 바꾸어야 할 쌍이 존재하지 않을 때까지 1번, 2번을 반복한다. (Loop)

i와 j라는 인덱스를 가진 두 개의 값을 서로 바꾸기(Swap) 위해서는 몇가지 방법이 있는데 임시 변수를 사용하는 예는 다음과 같다:

t = a[i]
a[i] = a[j]
a[j] = t

입력과 출력

입력 데이터의 첫번째 라인은 배열의 갯수를 의미하며 두번째 라인은 배열의 요소값을 의미한다.

출력 데이터는 두개의 값으로 이루어진다.

첫번째 값은 배열을 따라 진행(Loop)한 횟수이며 두번째 값은 Swap이 발생한 총 횟수이다.

다음은 입출력 예제이다:

input data:
8
3 1 4 1 5 9 2 6

answer:
5 8

출처: https://codingdojang.com/scode/448?answer_mode=hide

---

[풀이]

def BubbleSort(a):
    loop = 0
    swap = 0

    while True:
        b = a.copy()
        for i in range(len(a)-1):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                swap += 1
        loop += 1
        
        if b == a:
            break
        
    return print(loop, swap)

a = [3, 1, 4, 1, 5, 9, 2, 6]
BubbleSort(a)

5 8

이 문제는 다른 점보다 loop가 결국 최종 완성된 배열도 읽어야 배열이 정렬되었는지 확인 한다는 것이다.

def BubbleSort(a):
    loop = 0
    swap = 0

    while True:
        b = a.copy()
        for i in range(len(a)-1):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                swap += 1
        loop += 1
        
        print(b, a)
        if b == a:
            break
        
    return print(loop, swap)

a = [3, 1, 4, 1, 5, 9, 2, 6]
BubbleSort(a)

[3, 1, 4, 1, 5, 9, 2, 6] [1, 3, 1, 4, 5, 2, 6, 9]
[1, 3, 1, 4, 5, 2, 6, 9] [1, 1, 3, 4, 2, 5, 6, 9]
[1, 1, 3, 4, 2, 5, 6, 9] [1, 1, 3, 2, 4, 5, 6, 9]
[1, 1, 3, 2, 4, 5, 6, 9] [1, 1, 2, 3, 4, 5, 6, 9]
[1, 1, 2, 3, 4, 5, 6, 9] [1, 1, 2, 3, 4, 5, 6, 9]
5 8

위와 같이 전 후 비교를 위해선 다 정렬이 되어도 한번 더 읽어야하므로 loop가 1 늘어난다.

---

[추천 풀이]

# bubble sort

def bubble_sort(a):
    pass_count = 0
    swap_count = 0
    while True:
        swap = 0
        for i in range(len(a)-1):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                swap+=1
        pass_count += 1
        if swap:
            swap_count += swap
        else:
            break
    return pass_count, swap_count, a


print (bubble_sort([3, 1, 4, 1, 5, 9, 2, 6]))

(5, 8, [1, 1, 2, 3, 4, 5, 6, 9])

stop 조건을 swap 수로 설정한 것 외에는 동일하다.