오늘은 정렬 알고리즘 중 분할 정복 전략을 활용한 정렬 알고리즘인 버블 정렬에 대해 소개하려고 한다
참고로 퀵 정렬 알고리즘에 퀵(Quick)이 붙은 이유는 다른 여러 정렬 알고리즘에 비해 빠르게”동작한다는 것을 강조하기 위해서 붙여졌다고 한다
퀵 정렬이란?
퀵 정렬은 분할 정복 전략을 사용하는 정렬 알고리즘으로 주어진 배열에서 임의의 원소를 피벗으로 선택한 후
피벗보다 작은 원소들과 큰 원소들로 분할한다 그 후 각 부분 배열에 대해 동일한 방식으로 정렬을 반복하며 전체 배열을 정렬하는 방식을 가진다
퀵 정렬의 작동 방식
글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 오름차순으로 퀵 정렬 알고리즘을 사용한다고 했을 때
정렬해야 하는 리스트: [9, 7, 5, 11, 12, 2]
첫 번째 진행:
피벗 5 선택
1
2
3
9, 7와 피벗 5 비교 → 왼쪽에 그대로
11, 12와 피벗 5 비교 → 오른쪽에 그대로
2와 피벗 5 비교 → 왼쪽에 위치 → [2, 5, 9, 7, 11, 12]
두 번째 진행:
피벗 9 선택
1
7와 피벗 9 비교 → 왼쪽에 위치 → [2, 5, 7, 9, 11, 12]
이와 같은 과정을 통하면 리스트에 전체 원소가 오름차순으로 정렬된다
퀵 정렬의 장단점
마지막으로 퀵 정렬 알고리즘에 장단점을 알아보자
장점:
- 평균적인 경우 매우 빠른 실행 시간을 가졌다
- 추가 메모리를 적게 사용한다 (인플레이스 정렬)
단점:
- 최악의 경우 시간 복잡도가 O(n2)이다
- 안정적이지 않기에 같은 값의 원소의 상대적인 순서가 보장되지 않을 수 있다