1. 버블 정렬 개념
맨 앞에서부터 맨 뒤까지 인접한 두 원소를 차례대로 비교합니다.
비교한 결과 더 큰 원소가 앞에 있을 경우, 비교한 두 원소의 자리를 바꿔줍니다.(제자리 정렬)
이 과정을 한 번 마치면 배열의 맨 뒤에는 가장 큰 원소가 위치합니다.
따라서 이 과정을 범위를 한 칸씩 줄여가며 계속해서 반복합니다.
2. 버블 정렬 예제
3. 버블 정렬 코드
nums = [5, 3, 4, 1, 2]
def bubble_sort(nums):
for i in range(1, len(nums)):
for j in range(len(nums)-i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
bubble_sort(nums)
print(nums)
# [1, 2, 3, 4, 5]4. 버블 정렬 장점
버블 정렬은 매우 간단하고 이해하기 쉬운 정렬 알고리즘입니다.
게다가 코드 구현이 직관적이어서 초보자들이 배우기에 좋습니다.
추가 메모리 공간을 거의 사용하지 않기 때문에 메모리 사용이 제한적인 환경에서도 사용할 수 있습니다.
동일한 값을 가진 원소들의 상대적 위치가 변하지 않아 안정적인 정렬 알고리즘입니다.
5. 버블 정렬 단점
버블 정렬의 시간 복잡도는 최악과 평균 모두 \(O(n^2)\)입니다.
원소의 개수가 많아지면 성능이 급격히 저하됩니다.
많은 비교와 교환이 필요하여 실제 실행 시간에서 더 비효율적입니다.
6. 정렬 알고리즘 시간 복잡도 비교
| 정렬 알고리즘 | 최악(Worst) | 최선(Best) | 평균(Average) |
| 버블 정렬(Bubble Sort) | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) |
| 선택 정렬(Selection Sort) | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) |
| 삽입 정렬(Insertion Sort) | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) |
| 퀵 정렬(Quick Sort) | \(O(n^2)\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 병합 정렬(Merge Sort) | \(O(n\log{n})\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 힙 정렬(Heap Sort) | \(O(n\log{n})\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 기수 정렬(Radix Sort) | \(O(n)\) | \(O(n)\) | \(O(n)\) |
| 계수 정렬(Counting Sort) | \(O(n)\) | \(O(n)\) | \(O(n)\) |
