알고리즘과 친해지기 (7) - 버블 정렬

• 버블 정렬

  버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식입니다!

  작은 숫자, 큰 숫자 순서로 있으면 내버려두고
  큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경하시면 됩니다!

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4와 6을 비교합니다!
        4 < 6 이면 그대로 둡니다.

2단계 : [4, 6, 2, 9, 1]
           6과 2를 비교합니다!
           6 > 2 이므로 둘을 변경합니다!
       [4, 2, 6, 9, 1] 이렇게요!

3단계 : [4, 2, 6, 9, 1]
              6과 9를 비교합니다!
              6 < 9 이면 그대로 둡니다.

4단계 : [4, 2, 6, 9, 1]
                 9와 1를 비교합니다!
                 9 > 1 이므로 둘을 변경합니다!
       [4, 2, 6, 1, 9] 이렇게요!

자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 가장 큰 숫자인 9가 맨 뒤로 왔습니다.
큰 게 나오면 둘의 자리를 변경했으니 가장 맨 뒤에 갔다는 소리입니다!
그러면, 맨 뒷자리를 제외하고 다시 한 번 돌리면 됩니다!

5단계 : [4, 2, 6, 1, 9]
        4와 2을 비교합니다!
        4 > 2 이므로 둘을 변경합니다.
       [2, 4, 6, 1, 9] 이렇게요!

6단계 : [2, 4, 6, 1, 9]
           4와 6을 비교합니다!
           4 < 6 이면 그대로 둡니다.

7단계 : [2, 4, 6, 1, 9]
              6와 1을 비교합니다!
              6 > 1 이므로 둘을 변경합니다!
       [2, 4, 1, 6, 9] 이렇게요!

그러면 이제 두 번째로 큰 숫자인 6이 맨 뒤에서 두번쨰로 왔습니다!
여기까지만 비교하시면 됩니다. 6과 9을 비교할 필요는 없습니다.
다시 한 번 가볼게요!

8단계 : [2, 4, 1, 6, 9]
        2와 4을 비교합니다!
        2 < 4 이면 그대로 둡니다.

9단계 : [2, 4, 1, 6, 9]
           4와 1을 비교합니다!
           4 > 1 이므로 둘을 변경합니다!
       [2, 1, 4, 6, 9] 이렇게요!

자, 이제 세 번쨰로 큰 숫자인 4가 맨 뒤에서 세번째로 왔습니다!
마지막 비교만 하면 됩니다!

10단계 : [2, 1, 4, 6, 9]
         2와 1을 비교합니다!
         2 > 1 이므로 둘을 변경합니다!
        [1, 2, 4, 6, 9] 이렇게요!

자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?

• python swap

>>> a = 3
>>> b = 4

>>> a, b = b, a
>>> print(a)
4

>>> print(b)
3

• ❓ Q.
  다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 버블 정렬을 이용해서 정렬하시오.

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
    # 이 부분을 채워보세요!
    return array


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))

• 💡 내 코드

  input = [4, 6, 2, 9, 1]
  
  def bubble_sort(array):     # 시간복잡도 O(N^n)
    n = len(array)  # 5
    for i in range(n -1):   # range(4) => 0 1 2 3
        for j in range(n -i -1):
            print(range(n -i -1))   # 5 - 0 - 1 = 4 / 5 - 1 - 1 = 3 / 5 - 2 - 1 = 2
            if array[j] > array[j +1]:
                array[j], array[j +1] = array[j +1], array[j]
    return
  
  bubble_sort(input)
  print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

  • 🚩 해결방법
    위에서 이야기했던 로직 그대로 코드에 옮기면 됩니다!

    우선, 반복되는 구조라서 반복문을 써야 하는데, 어떤 식으로 반복하고 있나요?

    1번째 : [4, 6, 2, 9, 1]
    → → → → 비교!
    2번째 : [4, 2, 6, 1, 9]
    → → → 비교!
    3번째 : [2, 4, 1, 6, 9]
    → → 비교!
    4번째 : [2, 1, 4, 6, 9]
    → 비교!

    즉, 배열의 크기만큼 반복했다가, 1개씩 줄어들면서 반복하게 됩니다.
    이 반복문을 구현하려면 아래처럼 작성하면 됩니다!