버블 정렬 알고리즘은 간단한 정렬 알고리즘으로, 반복적으로 정렬할 리스트를 훑어가면서 인접한 요소들을 비교하고, 만약 순서가 잘못되어 있다면 이를 교환합니다. 이 알고리즘은 각 패스마다 더 작은 요소들이 리스트의 위쪽으로 이동하는 모습이 흡사 거품이 일어나는 모습과 흡사하여 '버블 정렬'이라는 이름을 얻었습니다.
파이썬 예제를 통해 버블 정렬 알고리즘을 설명하겠습니다:
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]
# 예제 사용:
nums = [64, 34, 25, 12, 22, 11, 90]
print("원본 리스트:", nums)
# bubble_sort 함수를 호출하여 리스트를 정렬합니다.
bubble_sort(nums)
print("정렬된 리스트:", nums)
설명:
bubble_sort 함수는 리스트 arr를 인자로 받아와서 버블 정렬 알고리즘을 사용하여 요소들을 오름차순으로 정렬합니다.
바깥쪽 루프 for i in range(n)는 i = 0부터 i = n-1까지 반복되며, 여기서 n은 리스트의 길이입니다. 이 루프는 리스트를 훑는 패스의 횟수를 제어합니다.
안쪽 루프 for j in range(0, n - i - 1)는 인접한 요소들을 비교하고 교환하는 작업을 수행합니다. 리스트를 한 번 훑을 때마다 가장 큰 요소가 자리를 잡아서 정렬이 이루어집니다.
만약 arr[j]의 요소가 arr[j + 1]의 요소보다 크다면, 이들을 올바른 순서로 교환합니다.
숫자 리스트 nums를 인자로 bubble_sort 함수를 호출한 후에, nums의 요소들이 오름차순으로 재배열됩니다. 결과 출력은 다음과 같을 것입니다:
원본 리스트: [64, 34, 25, 12, 22, 11, 90]
정렬된 리스트: [11, 12, 22, 25, 34, 64, 90]
정렬된 리스트는 원래 리스트를 버블 정렬 알고리즘에 따라 정렬한 결과입니다. 리스트를 훑으면서 가장 큰 요소가 자리를 잡아가면서, 오름차순으로 정렬된 리스트가 생성됩니다.
버블 정렬 알고리즘은 특히 큰 리스트에 대해서는 가장 효율적이지 않은 정렬 알고리즘으로, 시간 복잡도는 O(n^2)입니다. 그러나 이해하고 구현하기 쉬운 편이므로 정렬 알고리즘을 배우는 첫 단계로 좋은 출발점이 됩니다.
