버블 정렬(Bubble_Sort)이란 무엇인가?

 

버블 정렬(Bubble SortSort)은 간단하지만 효율성이 떨어지는 정렬 알고리즘입니다. 

버블 정렬을 한 마디로 정의하자면 “맨 뒤부터 정리하는 정렬” 혹은 “옆과 비교하여 왼쪽이 더 크면 좌우 교환하는 정렬”이라고 할 수 있겠습니다. 

 

버블 정렬은 인접한 두 요소를 비교하여 그 순서가 맞지 않으면 교체하는 방식으로 작동합니다. 

 

 

1. 첫 번째 반복 
   • 배열의 첫 번째 요소와 두 번째 요소를 비교합니다. 
   • 첫 번째 요소가 두 번째 요소보다 크면, 두 요소를 교체합니다. 
   • 이 과정을 배열의 마지막 요소까지 반복합니다. 배열의 맨 마지막 요소는 가장 큰 요소가 됩니다.
2. 남은 반복
   • 위의 과정을 반복합니다. 예를 들어, 두 번째 반복에서는 두 번째로 큰 요소가 배열의 두 번쨰 위치에 배치됩니다. 
   • 이러한 과정을 배열의 모든 요소가 정렬될 때까지 계속 반복합니다. 

---

파이썬으로 코드를 구현해 보겠습니다. 

버블 정렬을 구현하는 예시는 다음과 같습니다. 

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

위 코드를 자세히 뜯어보겠습니다. 

 

함수 정의와 변수 초기화 

def bubble_sort(arr): 
    n = len(arr)

• ‘bubble_sort’ 함수는 리스트 ‘arr’을 인자로 받습니다. 
• ‘n’ 변수는 리스트의 길이를 저장합니다. 

 

외부 루프 

    for i in range(n):

• 이 루프는 리스트의 모든 요소를 정렬하기 위해 ‘n’번 반복됩니다.
• 각 반복에서, 리스트의 가장 큰 요소가 리스트의 끝으로 이동하게 됩니다.  

 

내부 루프 

        for j in range(0, n-i-1):

• 이 루프는 리스트의 첫 번째 요소부터 ‘n-i-1'번째 요소까지 비교합니다.
• n-i-1'은 이미 정렬된 마지막 부분을 제외하기 위해 사용됩니다. 따라서, ‘i’번째 패스 이후에는 마지막 ‘i’개의 요소가 이미 정렬되어 있으므로, 이러한 이미 정렬된 부분을 비교할 필요가 없습니다. 
• 첫 번째 패스에서 ‘j’는 ‘0’부터 ‘n-2’까지 비교합니다. (총 ‘n-1’개 비교)
• 두 번째 패스에서 ‘j’는 ‘0’부터 ‘n-3’까지 비교합니다. (총 ‘n-2’개 비교) 

 

 

요소 비교와 교체 

            if arr[j] > arr[j+1]: 
                arr[j], arr[j+1] = arr[j+1], arr[j]

• 이 부분에서 인접한 두 요소 ‘arr[j]’와 ‘arr[j+1]’를 비교합니다. 
• 만약 ‘arr[j]’가 ‘arr[j+1]’보다 크면, 두 요소를 교체합니다. 이로써 더 큰 요소가 오른쪽으로 이동하게 됩니다. 

 

---

 

예를 들어, [3, 7, 1, 4, 1,5]라는 리스트를 정렬하는 과정을 아래와 같습니다.

첫 번째 반복 (i = 0)

• j는 0부터 4까지 반복합니다.
  • arr(3)와 arr(7)를 비교하여 교체하지 않음: [3, 7, 1, 4, 1, 5]
  • arr(7)와 arr(1)를 비교하여 교체: [3, 1, 7, 4, 1, 5]
  • arr(7)와 arr(4)를 비교하여 교체: [3, 1, 4, 7, 1, 5]
  • arr(7)와 arr(1)를 비교하여 교체: [3, 1, 4, 1, 7, 5]
  • arr(7)와 arr(5)를 비교하여 교체: [3, 1, 4, 1, 5, 7]

두 번째 반복 (i = 1)

• j는 0부터 3까지 반복합니다.
  
  • arr(3)와 arr(1)를 비교하여 교체: [1, 3, 4, 1, 5, 7]
  • arr(3)와 arr(4)를 비교하여 교체하지 않음: [1, 3, 4, 1, 5, 7]
  • arr(4)와 arr(1)를 비교하여 교체: [1, 3, 1, 4, 5, 7]
  • arr(4)와 arr(5)를 비교하여 교체하지 않음: [1, 3, 1, 4, 5, 7]

세 번째 반복 (i = 2)

• j는 0부터 2까지 반복합니다.
  
  • arr(1)와 arr(3)를 비교하여 교체하지 않음: [1, 3, 1, 4, 5, 7]
  • arr(3)와 arr(1)를 비교하여 교체: [1, 1, 3, 4, 5, 7]
  • arr(3)와 arr(4)를 비교하여 교체하지 않음: [1, 1, 3, 4, 5, 7]

네 번째 반복 (i = 3)

• j는 0부터 1까지 반복합니다.
  
  • arr(1)와 arr(1)를 비교하여 교체하지 않음: [1, 1, 3, 4, 5, 7]
  • arr(1)와 arr(3)를 비교하여 교체하지 않음: [1, 1, 3, 4, 5, 7]

다섯 번째 반복 (i = 4)

• j는 0부터 0까지 반복합니다.
  
  • arr(1)와 arr(1)를 비교하여 교체하지 않음: [1, 1, 3, 4, 5, 7]

 

최종적으로
리스트는 [1, 1, 3, 4, 5, 7]로 정렬됩니다.