[알고리즘] 거품 정렬(Bubble Sort)

거품 정렬(Bubble Sort)

거품 정렬은 버블 정렬이라고도 불리는 알고리즘이다. 거품 정렬은 두 인접한 데이터의 대소를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘이다.

 

이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.

 

 

정렬 과정

1. 1회전에 첫번째 원소와 두번째 원소를 비교, 두번째 원소와 세번째 원소를 비교, ... (마지막-1)번째 원소와 마지막 원소의 대소를 비교하며 정렬
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동한다. 따라서 2회전에서는 맨 마지막 원소를 제외하고 1번 과정을 다시 수행하여 두번째로 큰 수를 맨 뒤에서 두번째로 정렬한다. 이렇게 정렬을 1회전씩 수행하다 보면 모든 수는 정렬이 되어있다.

 

 

파이썬 코드

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

print(bubble_sort([5, 3, 7, 9, 1]))
# 1, 3, 5, 7, 9

 

 

 

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

거품 정렬(Bubble Sort) | 👨🏻‍💻 Tech Interview