퀵 정렬 알고리즘이란?

오늘은 정렬 알고리즘 중 분할 정복 전략을 활용한 정렬 알고리즘인 버블 정렬에 대해 소개하려고 한다

참고로 퀵 정렬 알고리즘에 퀵(Quick)이 붙은 이유는 다른 여러 정렬 알고리즘에 비해 빠르게”동작한다는 것을 강조하기 위해서 붙여졌다고 한다

퀵 정렬이란?

퀵 정렬은 분할 정복 전략을 사용하는 정렬 알고리즘으로 주어진 배열에서 임의의 원소를 피벗으로 선택한 후

피벗보다 작은 원소들과 큰 원소들로 분할한다 그 후 각 부분 배열에 대해 동일한 방식으로 정렬을 반복하며 전체 배열을 정렬하는 방식을 가진다

퀵 정렬의 작동 방식

글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 오름차순으로 퀵 정렬 알고리즘을 사용한다고 했을 때

정렬해야 하는 리스트: [9, 7, 5, 11, 12, 2]

첫 번째 진행:

피벗 5 선택

9, 7와 피벗 5 비교 → 왼쪽에 그대로
11, 12와 피벗 5 비교 → 오른쪽에 그대로
2와 피벗 5 비교 → 왼쪽에 위치 → [2, 5, 9, 7, 11, 12]

두 번째 진행:

피벗 9 선택

7와 피벗 9 비교 → 왼쪽에 위치 → [2, 5, 7, 9, 11, 12]

이와 같은 과정을 통하면 리스트에 전체 원소가 오름차순으로 정렬된다

퀵 정렬의 장단점

마지막으로 퀵 정렬 알고리즘에 장단점을 알아보자

장점:

1. 평균적인 경우 매우 빠른 실행 시간을 가졌다
2. 추가 메모리를 적게 사용한다 (인플레이스 정렬)

단점:

1. 최악의 경우 시간 복잡도가 O(n2)이다
2. 안정적이지 않기에 같은 값의 원소의 상대적인 순서가 보장되지 않을 수 있다