1. 문제 정의
주어진 정수 배열을 오름차순으로 정렬하는 함수를 작성하시오.
정렬 알고리즘 중 가장 기본적인 방법인 버블 정렬(Bubble Sort)을 활용하여 구현해야 하며,
시간 복잡도와 공간 복잡도를 고려하여 코드를 최적화하는 과정도 포함해야 합니다.
문제: 임의의 정수 배열이 주어질 때, 버블 정렬 알고리즘을 사용하여
이 배열을 오름차순으로 정렬하는 스위프트 함수를 작성하시오.
2. 버블 정렬 알고리즘 개요
버블 정렬은 인접한 두 원소를 비교하여 정렬된 순서가 아닐 경우 교환하는 방식으로 작동하는 단순한 정렬 알고리즘입니다.
이 과정을 배열의 모든 인덱스에 대해 반복하며, 배열의 크기가 n일 때 최악의 경우 O(n²)의 시간복잡도를 가집니다.
버블 정렬의 주요 특징은 다음과 같습니다:
- 단순하고 이해하기 쉬운 알고리즘
- 보통 구현이 간단하며, 작은 데이터셋에서 유용하게 사용할 수 있음
- 최악의 경우 O(n²), 평균 O(n²), 최선의 경우 O(n) (이미 정렬된 경우)
3. 알고리즘 단계
버블 정렬을 사용하는 기본적인 방법은 다음과 같습니다:
- 배열의 첫 번째 요소부터 시작해 인접한 요소들을 비교합니다.
- 만약 첫 번째 요소가 두 번째 요소보다 크다면, 두 요소를 교환합니다.
- 이 과정을 배열의 끝까지 반복합니다.
- 배열의 끝에 도달하면 가장 큰 요소가 배열의 끝으로 이동합니다.
- 위의 단계를 n-1번 반복합니다.
이 과정을 통해 각 단계에서 가장 큰 요소가 점점 끝으로 이동하게 됩니다.
버블 정렬 구현 (스위프트 코드)
func bubbleSort(_ array: inout [Int]) {
let n = array.count
for i in 0.. array[j+1] {
// Swap
let temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
swapped = true
}
}
// If no two elements were swapped by inner loop, then break
if !swapped {
break
}
}
}
4. 코드 설명
위의 bubbleSort 함수는 인자로 배열을 받아, 배열을 오름차순으로 정렬합니다.
핵심 포인트:
inout키워드는 함수가 배열을 직접 수정할 수 있게 해줍니다.- 두 번째 for 루프에서
n-i-1을 사용하는 이유는 각 반복마다 가장 큰 요소가 배열의 끝으로 이동하기 때문입니다.
따라서 마지막 요소는 이미 정렬되어 있을 것이므로 확인할 필요가 없습니다. swapped변수를 통해 정렬이 이미 완료되었는지 확인하여 불필요한 반복을 줄입니다.
5. 테스트 및 예제
아래는 bubbleSort 함수를 테스트하는 예제입니다.
var myArray = [64, 34, 25, 12, 22, 11, 90]
print("정렬 전: \(myArray)")
bubbleSort(&myArray)
print("정렬 후: \(myArray)")
위의 코드를 실행하면 ‘정렬 전’과 ‘정렬 후’의 배열을 출력할 수 있습니다.
이로써 버블 정렬 알고리즘이 성공적으로 구현되었음을 확인할 수 있습니다.
6. 시간 복잡도 및 최적화
버블 정렬의 시간 복잡도는 최악의 경우 O(n²)입니다.
배열이 이미 정렬된 경우에도 최선의 경우 O(n)의 성능을 보일 수 있습니다.
이를 최적화하기 위해 swapped 변수를 도입하여 불필요한 반복을 피할 수 있습니다.
스위프트의 경우, 배열의 크기가 클 때 버블 정렬을 사용하는 것은 비효율적입니다.
이 경우 고급 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)을 사용하는 것을 권장합니다.
7. 결론
본 강좌에서는 스위프트로 버블 정렬 알고리즘을 구현하는 방법과 그 과정을 살펴보았습니다.
버블 정렬은 이해하기 쉽고 구현이 간단하지만, 실제로 사용할 경우 성능이 떨어질 수 있습니다.
따라서 복잡한 데이터셋을 다룰 때는 다른 알고리즘을 고려해야 합니다.
다음 강좌에서는 보다 효율적인 정렬 알고리즘인 퀵 정렬(Quick Sort)을 다룰 예정입니다.
8. 참고자료
알고리즘에 대한 더 깊은 이해를 위해 아래의 자료를 참고하시기 바랍니다: