버블정렬
버블 정렬 (Bubble Sort)은 가장 간단한 알고리즘 중 하나로, 이해하기 쉽지만 효율성 면에서 좋지 않은 알고리즘입니다. 이름에서 알 수 있듯이, 버블 정렬은 각각의 요소가 마치 거품이 올라오는 것처럼 연속적으로 이웃한 값과 비교하며 필요한 경우 위치를 교환합니다.
버블 정렬은 배열의 첫 번째 요소부터 시작하여 이웃하는 요소와 비교하며 가장 큰 값을 배열의 뒤쪽으로 이동시키는 과정을 반복합니다. 이러한 과정을 배열의 끝까지 반복한 후, 마지막으로 가장 큰 값을 제외하고 나머지 요소에 대해 같은 과정을 반복합니다. 이런 과정을 계속 반복하여 전체 배열을 정렬합니다.
주요 용도
버블 정렬은 간단한 정렬이 필요할 때 사용합니다. 또한, 리스트가 이미 거의 정렬된 상태인 경우에는 버블 정렬이 괜찮은 성능을 보일 수 있습니다.
장점
- 구현이 매우 간단합니다.
- 작은 데이터셋에 대해선 효율적일 수 있습니다.
- 안정적인 정렬입니다. 즉, 동일한 값의 원래 순서가 유지됩니다.
단점
- 효율성이 낮습니다. 대규모 데이터셋에 대해선 권장되지 않습니다.
- 시간 복잡도가 최악, 평균, 최선 모두 O(n^2)로 성능이 좋지 않습니다.
시간 복잡도
- 최선의 경우: O(n)
- 평균적인 경우: O(n^2)
- 최악의 경우: O(n^2)
사용에 적합한 상황
- 작은 데이터셋이 있는 경우
- 이미 거의 정렬된 데이터를 정렬하는 경우
사용에 부적합한 상황
- 대규모의 데이터셋이 있는 경우
주의사항
- 대규모의 데이터셋에는 사용하지 않는 것이 좋습니다.
패턴분석
-
n개의 리스트가 있는 경우 최대 n-1번의 로직을 적용한다.
-
로직을 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다.
-
로직이 경우에 따라 일찍 끝날 수도 있다. 따라서 로직을 적용할 때 한 번도 데이터가 교환된 적이 없다면 이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요가 없다.
두 번째 루프 안에서 매 루프마다
가장 큰 수는 마지막 요소로 자리잡기 때문에
두 번째 루프를 마지막까지 모두 돌 필요가 없다.
또한 그 패턴을 보면 하나씩 줄어드는 패턴이므로
두 번째 루프 (데이터 리스트의 length - 1)에서 첫 번째 루프의 인덱스를 뺀다.
for j in range(len(data) - (i + 1)):
구현
JS
function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
let swap = false;
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swap = true;
}
}
if (!swap) break;
}
return arr;
}
let arr = Array.from({ length: 40 }, () => Math.floor(Math.random() * 40));
const result = bubbleSort(arr);
console.log(result);이 bubbleSort 함수의 시간 복잡도는 최악의 경우와 평균적인 경우 모두 O(n^2)입니다. 여기서 n은 배열의 길이입니다.
최악의 경우는 배열이 역순으로 정렬된 경우입니다. 이 경우, 각 라운드에서 최소한 한 번의 교환(swap)이 발생하므로, 루프는 모든 라운드를 수행해야합니다. 두 개의 중첩 루프가 있기 때문에 시간 복잡도는 O(n^2)입니다.
그러나 최적의 경우(즉, 배열이 이미 정렬된 경우)에는 시간 복잡도가 O(n)이 됩니다. 이는 외부 루프가 한 번만 실행되고 내부 루프가 더 이상 실행되지 않기 때문입니다. 이러한 최적의 경우는 실제로는 잘 발생하지 않으므로, 일반적으로 버블 정렬의 시간 복잡도를 O(n^2)라고 합니다.
공간 복잡도는 O(1)입니다. 이는 추가적으로 사용되는 공간이 입력 크기에 의존하지 않고, 변수 'swap'을 위해 상수 공간만 사용하기 때문입니다. 이로 인해 이 알고리즘은 "in-place" 정렬 알고리즘이라고 불립니다.
"In-place" 알고리즘은 입력을 저장하는 데 사용된 메모리 외에 추가적으로 고정된 메모리만을 사용하는 알고리즘을 의미합니다.
다시 말해, 이들 알고리즘은 데이터를 정렬하기 위해 입력 배열 자체를 사용하고, 추가 배열이나 다른 데이터 구조를 필요로 하지 않습니다. 그 결과로 공간 복잡도는 O(1)이 됩니다.
이런 특성은 메모리 사용을 최소화하므로 매우 효율적입니다. 버블 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬 등이 in-place 정렬 알고리즘의 좋은 예입니다.
그러나 주의해야 할 점은 in-place 알고리즘이 원본 데이터를 변경할 수 있다는 것입니다. 이는 알고리즘을 사용하기 전에 고려해야 할 중요한 사항입니다.
Python
def bubbleSort(data):
for i in range(len(data) - 1): # 전체 리스트
swap = False
for j in range(len(data) - (i + 1)): # 정렬된 리스트 제외, 추가설명A 참고
if data[j] > data[j + 1]:
data[j], data[j+1] = data[j+1], data[j]
swap = True
if swap == False: # 더이상 스왑할 대상이 없으므로 루프 탈출
break
return data
# 테스트
import random
for i in range(30):
data = random.sample(range(100), 50)
print(bubbleSort(data))
# 결과
[0, 1, 2, 6, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 25, 27, 30, 33, 34, 38, 43, 44, 46, 47, 48, 52, 53, 54, 55, 56, 60, 61, 65, 67, 70, 71, 74, 76, 77, 78, 79, 83, 84, 85, 93, 94, 95, 96, 97, 99]
[0, 1, 2, 6, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 25, 27, 30, 33, 34, 38, 43, 44, 46, 47, 48, 52, 53, 54, 55, 56, 60, 61, 65, 67, 70, 71, 74, 76, 77, 78, 79, 83, 84, 85, 93, 94, 95, 96, 97, 99]
[0, 1, 2, 6, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 25, 27, 30, 33, 34, 38, 43, 44, 46, 47, 48, 52, 53, 54, 55, 56, 60, 61, 65, 67, 70, 71, 74, 76, 77, 78, 79, 83, 84, 85, 93, 94, 95, 96, 97, 99]
...
[0, 1, 2, 6, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 25, 27, 30, 33, 34, 38, 43, 44, 46, 47, 48, 52, 53, 54, 55, 56, 60, 61, 65, 67, 70, 71, 74, 76, 77, 78, 79, 83, 84, 85, 93, 94, 95, 96, 97, 99]
[0, 1, 2, 6, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 25, 27, 30, 33, 34, 38, 43, 44, 46, 47, 48, 52, 53, 54, 55, 56, 60, 61, 65, 67, 70, 71, 74, 76, 77, 78, 79, 83, 84, 85, 93, 94, 95, 96, 97, 99]
[0, 1, 2, 6, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 25, 27, 30, 33, 34, 38, 43, 44, 46, 47, 48, 52, 53, 54, 55, 56, 60, 61, 65, 67, 70, 71, 74, 76, 77, 78, 79, 83, 84, 85, 93, 94, 95, 96, 97, 99]
[0, 1, 2, 6, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 25, 27, 30, 33, 34, 38, 43, 44, 46, 47, 48, 52, 53, 54, 55, 56, 60, 61, 65, 67, 70, 71, 74, 76, 77, 78, 79, 83, 84, 85, 93, 94, 95, 96, 97, 99]function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
console.log(bubbleSort([5, 3, 8, 4, 2])); // Output: [2, 3, 4, 5, 8]
