이번 포스팅은 버블 정렬에 대해 정리한 내용입니다.
자료구조와 알고리즘을 공부하게 되면서 초반에 배우게 되는 간단한 알고리즘인 버블정렬은
인접한 두 원소를 비교하고 필요한 경우에 위치를 교환하며 정렬을 수행하는 것입니다.
버블 정렬의 동작원리와 개념에 대해 자세히 알아보겠습니다.
| 버블 정렬의 개념
- 버블 정렬은 이름 그대로 배열의 요소들을 반복적으로 비교하면서
큰 값이 "거품"처럼 위로 올라가며 배열을 정리하는 방식입니다.
이 과정은 배열의 길이만큼 반복되며, 한 번의 반복마다 가장 큰 값이 맨 오른쪽으로 이동합니다.
| 버블 정렬의 동작 원리
- 버블 정렬의 동작 원리를 간단히 설명하면 다음과 같습니다 :
1. 리스트를 순회하면서 인접한 두 개의 요소를 비교
2. 첫 번째 요소가 두 번째 요소보다 큰 경우, 두 요소를 교환
3. 리스트 전체에 반복, 한 번의 순회가 끝날 때마다 가장 큰 값이 맨 오른쪽으로 이동
4. 앞 과정 반복
예시) [5, 3, 8, 4, 2] 리스트를 버블 정렬하는 과정
1. 첫 번째 순회 :
- (5, 3) : 5 > 3 이므로 교환 -> [3, 5, 8, 4, 2]
- (5, 8) : 5 < 8 이므로 교환 없음 -> [3, 5, 8, 4, 2]
- (8, 4) : 8 > 4 이므로 교환 -> [3, 5, 4, 8, 2]
- (8, 2) : 8 > 2 이므로 교환 -> [ 3, 5, 4, 2, 8]
- 첫 번째 순회 결과 : [3, 5, 4, 2, 8] -> 가장 큰 값인 8이 맨 오른쪽으로 옮겨짐
2. 두 번째 순회 :
- (3, 5) : 3 > 5 이므로 교환 없음 -> [3, 5, 4, 2, 8]
- (5, 4) : 5 > 4 이므로 교환 -> [3, 4, 5, 2, 8]
- (5, 2) : 5 > 2 이므로 교환 -> [3, 4, 2, 5, 8]
- 두 번째 순회 결과 : [3, 4, 2, 5, 8] -> 두 번째로 큰 값인 5가 오른쪽으로 옮겨짐
계속해서 같은 과정을 반복하여 최종적으로 모든 요소가 올바르게 정렬됩니다.
이번에는 Python 코드를 통해 버블 정렬을 하는 과정을 보겠습니다.
예시) [5, 3, 8, 4, 2] 리스트를 버블 정렬하는 과정 (Python)
def bubble_sort(arr):
n = len(arr)
# 리스트 길이만큼 반복하여 정렬 수행
for i in range(n):
# 각 반복에서 마지막 i개의 원소는 이미 정렬되었으므로 무시
for j in range(0, n-i-1):
# 인접한 두 원소를 비교하여 큰 값을 뒤로 보냄
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# 정렬하고자 하는 리스트
my_list = [5, 3, 8, 4, 2]
# 버블 정렬 수행
bubble_sort(my_list)
# 정렬된 결과 출력
print("정렬된 리스트:", my_list) # Output: [2 ,3 ,4 ,5 ,8]| 버블 정렬의 시간 복잡도와 효율성
- 버블 정렬은 단순한 구조이기 때문에 구현이 쉽지만 효율성 면에서는 다른 알고리즘 보다 낮습니다.
평균적으로 O(n^2)의 시간 복잡도를 가지기 때문에 배열의 크기가 커질수록 성능 저하가 발생합니다.
그러나 데이터셋이 작거나 이미 거의 정렬된 상태라면 성능상 좋은 결과를 보여줍니다.
| 마무리
- 버블 정렬은 알고리즘의 동작 원리와 구현 방법을 익히기 좋은 예인 것 같습니다.
기본적인 개념을 익히기에 쉬운 예시이며 시작하기에 좋은 정렬 알고리즘입니다.
덧붙여 다양한 종류의 다른 정렬 알고리즘이 존재하고 앞으로 정리해 보겠습니다.
버블 정렬에 대해 알아보았습니다.
틀린 점이나 질문이 있으시면 댓글로 남겨주세요!
다음 포스팅으로 찾아오겠습니다.
감사합니다 :)
'Computer Science > Algorithm' 카테고리의 다른 글
| [알고리즘] 병합 정렬(Merge Sort) 이해 with Python (2) | 2023.10.16 |
|---|---|
| [알고리즘] 퀵 정렬(Quick sort) 이해 with Python (0) | 2023.10.10 |
