거품 정렬(Bubble Sort)

거품 정렬(Bubble Sort)

개념

 

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를,.... n-1 번째 원소와 n 번째 원소를 비교하여 교환하며 자료를 정렬
• 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하고 2회전부터는 맨 마지막 원소 제외 후 같은 과정 반복 

코드

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

1. 내부 반복문에서는 첫 번째 원소부터 이전 회전에서 뒤로 보내놓은 값이 있는 위치 전까지 앞뒤 원소를 비교해나가면서 교대(swap) 진행
2. 외부 반복문에서는 정렬 범위를 n-1에서 1까지 줄여나간다. 

특징

• 장점
  • 구현이 매우 간단하고, 소스코드가 직관적 
  • 정렬하고자 하는 배열 내부에서 교환하는 방식으로 다른 메모리 공간이 필요하지 않다. => in-place sorting
• 단점
  • 시간 복잡도가 최상, 평균, 최악 모두 일정하게 O(N^2)으로 비효율적이다.

시간 복잡도

• (N-1) + (N-2) + ... + 2 + 1 => N(N-1)/2 => O(N^2)

 

참고

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog