Bubble-sort (버블 정렬)

설명

• 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
• 정렬과정
  • 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
  • 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
  • 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 칭함
• 시간 복잡도
  • O($n^2$)

 

예시

• [55, 7, 78, 12, 42]를 버블 정렬하는 과정

- 첫번째 패스

- 두번째 패스

- 세번째 패스

- 네번째 패스

- 정렬 끝

• 배열을 활용한 버블 정렬
  • 앞선 과정을 코드로 구현하면 아래와 같다.

arr = [55, 7, 78, 12, 42]


def bubble_sort(array):  # 정렬할 List
    for i in range(len(array) - 1, 0, -1):  # 범위의 끝 위치
        for j in range(0, i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                
                # 파이썬이 아닌 언어는 밑의 코드로 교환을 진행
                # temp = array[j]
                # array[j] = array[j+1]
                # array[j+1] = temp