[알고리즘] 퀵 정렬

퀵 정렬

- 퀵 정렬은 대표적인 분할 정복 알고리즘 중 하나로 평균적으로 가장 빠른 실행 시간을 가지는 정렬 알고리즘 입니다.

 

- 퀵 정렬은 unstable한 알고리즘으로 호출될 때마다 새로운 리스트를 생성하며 리턴하기 때문에 기본적으로는 not-in-place 정렬이기도 하다.

 

- 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

 

 

Unstable

퀵 정렬은 unstable한 알고리즘으로 unstable한 알고리즘이란, 정렬 후 같은 값들의 순서가 원래의 순서와 다를 수 있는 것을 말합니다.

 

예를 들어, [3, 1, 3, 4, 2]와 같은 배열을 퀵 정렬로 정렬하면 [1,2,3,3,4]와 같이 3이 중복되서 나타나는데 여기서 3의 순서가 원래의 순서와 다를 수 있다는 것을 의미합니다. 

 

stable한 정렬은 정렬 후 같은 값들의 순서가 원래의 순서와 동일하게 유지되는 정렬을 의미하고 예시들로는 병합 정렬, 삽입 정렬 등등이 있습니다.

 

과정

1. 기준점(Pivot)을 선택합니다. 일반적으로 배열의 첫 번째 또는 마지막 값을 기준점으로 선택합니다.

2. 배열을 기준점을 기준으로 두 개의 서브 배열로 분할합니다. 기준점보다 작은 값은 왼쪽 배열로, 기준점보다 큰 값은 오른쪽 배열로 이동합니다.

3. 왼쪽 서브 배열과 오른쪽 서브 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.

4. 재귀적인 호출이 끝나면, 각 서브 배열은 정렬된 상태입니다.

 

 

💡 이 과정에서 기준점의 선택 방법이 중요합니다. 만약 기준점이 최소값이나 최대값일 경우 분할이 제대로 이루어지지 않아 시간 복잡도가 높아지게 됩니다. 따라서 일반적으로 기준점을 선택할 때는 배열의 중간값을 사용하는 중앙 피벗방법이 많이 사용됩니다.

 

 

 

퀵 정렬 동작 예시

 

 

파이썬에서 사용할 때 장점

1. 파이썬 내장 정렬 함수인 sorted() 와 list.sort()함수는 퀵 정렬 알고리즘을 기반으로 작동합니다. 따라서 파이썬에서는 이미 내장된 함수를 사용하여 간단하게 정렬을 사용할 수 있습니다.

 

2. 파이썬에서는 퀵 정렬 알고리즘이 다른 정렬 알고리즘과 비교하여 상대적으로 빠른 실행 시간을 가집니다. 이는 파이썬이 동적 타이핑언어이므로 배열의 요소들이 서로 다른 데이터 타입을 가지는 경우에도 적용됩니다.

 

3. 파이썬에서는 리스트 자료형을 사용하여 배열을 표현할 수 있습니다. 이 리스트는 퀵 정렬 알고리즘에서 사용되는 분할과 병합 작업에 적합한 자료형입니다.

 

4. 파이썬에서는 재귀 호출과 같은 복잡한 알고리즘을 쉽게 구현할 수 있는 함수형 프로그래밍 기능을 제공합니다. 따라서 파이썬에서 퀵 정렬 알고리즘을 구현하는 것은 상대적으로 쉽습니다.

 

퀵 정렬을 가장 많이 쓰는 이유

1. 평균 시간복잡도가 O(nlogn)으로, 다른 대부분의 정렬 알고리즘보다 빠릅니다.

2. 분할 정복 알고리즘을 사용하여 구현이 간단합니다.

3. 대부분의 경우, 추가적인 메모리 공간을 필요로하지 않으므로, 메모리 사용량이 적습니다.

4. 최악의 경우에도 O(n^2)의 시간 복잡도를 가지지만, 대부분의 경우에는 O(nlogn)보다 빠른 시간 안에 정렬이 완료됩니다.

 

 

💡또한, 퀵 정렬은 unstable한 정렬 알고리즘이지만, 정렬하려는 데이터가 객체나 레코드와 같이 여러 필드를 가진 경우, 하나의 필드를 기준으로만 정렬하는 것이 아니라 다른 필드에 대해서도 정렬이 필요한 경우가 있습니다. 이러한 경우, stable한 정렬 알고리즘을 사용하면 되지만, 이 경우에는 기준 필드를 여러 개로 지정할 수 있으므로 퀵 정렬도 사용될 수 있습니다.

 

 

 

 

Reference

- 퀵 정렬 동작 예시 사진 : https://freedeveloper.tistory.com/377