🔍버블 정렬 알고리즘이란?
버블 정렬(Bubble Sort)은 배열의 처음부터 끝까지 인접한 두 숫자를 비교하며,
더 큰 숫자를 오른쪽으로 이동시키는 방식의 정렬 알고리즘입니다
📌버블 정렬의 동작 방식
실제 예시를 통해 버블 정렬의 동작방식을 살펴보겠습니다
예를 들어, [7, 5, 3, 1] 배열을 오름차순으로 정렬할 것입니다
🎈 1회차 비교 과정:
- 7과 5 비교 → 7이 더 크므로 교환합니다 (
[5, 7, 3, 1]) - 7과 3 비교 → 교환합니다 (
[5, 3, 7, 1]) - 7과 1 비교 → 교환합니다 (
[5, 3, 1, 7])
첫 번째 반복을 마치면, 배열의 가장 큰 값인 7이 맨 끝에 위치하게 됩니다.
🎈 2회차 비교 과정:
- 5와 3 비교 → 교환합니다 (
[3, 5, 1, 7]) - 5와 1 비교 → 교환합니다 (
[3, 1, 5, 7]) - 5와 7 비교 → 교환하지 않습니다 (
[3, 1, 5, 7])
두 번째 반복 후 두 번째로 큰 값인 5가 끝에서 두 번째 자리에 정렬됩니다.
🎈 3회차 비교 과정:
- 3과 1 비교 → 교환합니다 (
[1, 3, 5, 7]) - 3과 5 비교 → 교환하지 않습니다
- 5와 7 비교 → 교환하지 않습니다
이제 모든 숫자가 오름차순으로 정렬되었습니다 ([1, 3, 5, 7]).
🚀 실제 코드로 구현하기
위에서 설명한 동작 방식을 코드로구현하면 다음과 같습니다.
int[] arr = {3,1,5,7};
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1; j++) {
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}이 코드를 실행하면 배열은 [1, 3, 5, 7]의 형태로 오름차순 정렬됩니다
🛠️ 시간 복잡도
정렬 알고리즘을 사용할 때 가장 중요한 고려사항 중 하나가 바로 시간 복잡도입니다
버블 정렬은 배열의 크기(N)가 커질수록 비효율적인 알고리즘입니다.
- 최악의 경우(완전히 역순 정렬) → O(N²)
- 평균적인 경우 → O(N²)
- 최선의 경우(이미 정렬된 배열) → O(N) (최적화 적용 시)
📌 버블 정렬의 장점
- 메모리 절약(In-place 정렬)
추가적인 공간을 사용하지 않고 기존 배열 내에서 정렬합니다
따라서 메모리 사용이 적습니다
📌 버블 정렬의 단점
- 느린 연산 속도
데이터의 크기가 커질수록 연산 시간이 증가합니다 - 이미 정렬된 배열도 반복 확인
최적화하지 않으면 이미 정렬된 배열도 계속해서 확인하기 때문에 불필요한 연산이 반복됩니다
✨ 정렬 알고리즘 관련 추가 개념
- In-place 정렬 : 별도의 추가 공간 없이 기존 배열 내에서 정렬을 진행하는 방식입니다
- 안정 정렬(Stable Sort) : 정렬 이후에도 값이 동일한 원소들의 기존 순서가 유지되는 정렬 방식입니다 버블 정렬은 안정 정렬에 해당합니다
🚀 버블 정렬 최적화
이전에 구현한 버블 정렬 알고리즘은
이미 정렬된 배열에서도 끝까지 반복해서 확인하는 문제가 있습니다
이 문제를 해결하기 위해 다음과 같이 최적화할 수 있습니다
int[] arr = {3,1,5,7};
for (int i = 0; i < arr.length-1; i++) {
boolean isSwap = false;
for (int j = 0; j < arr.length-1; j++) {
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
isSwap = true;
}
}
if(!isSwap){
break;
}
}isSwap이라는 boolean 변수를 사용하여 한 번의 순회에서 교환이 발생했는지 체크합니다
만약 교환이 한 번도 일어나지 않았다면 더 이상 반복하지 않고 종료합니다
✍️ 결론
버블 정렬은 인접한 원소의 크기를 비교하며 정렬하는 알고리즘입니다
별도의 추가 공간 없이 배열 내에서 정렬(In-place)이 가능하며,
안정 정렬이라는 장점도 있지만, 시간 복잡도가 좋지 않다는 단점도 존재합니다
Software Developer