퀵 정렬 알고리즘 (Quick sort Algorithm)

 

틀린 내용을 발견하신 경우 말씀 부탁드립니다! 🙇

---

 

퀵 정렬은 분할 정복(Divide and conquer) 전략 중 하나로 재귀적 알고리즘에 해당한다. 분할 정복 전략은 그대로 해결할 수 없는 문제를 작은 문제로 분리하고 결과를 모아 원래의 문제를 해결하는 전략이다. 분할 정복 전략으로 문제를 풀기 위해선 아래 단계를 거친다.

① 문제가 기본단계가 될 때까지 나눈다 (Divide)
② 기본 단계를 해결한다 (Conquer)
③ 기본 단계의 답을 통합해 가장 큰 문제(원래 문제)의 답을 도출한다 (Combine)

 

 

분할 정복 전략 예시

가로 14, 세로 6인 직사각형을 똑같은 크기의 정사각형으로 나누면 총 몇 개의 정사각형이 반환되는가? 정사각형은 최대한 크게 만들도록 한다.

1. 주어진 직사각형을 최대한 큰 정사각형으로 나눈다.

2. 나머지 직사각형을 최대한 큰 정사각형으로 나눈다.

3. 나머지 직사각형에서 구한 정사각형으로 전체 정사각형을 나눈다. 

 

→ 가로 14, 세로 6인 직사각형을 똑같은 크기의 정사각형으로 나누면 총 21개의 정사각형으로 나눌 수 있다. (나머지 크기에 맞는 가장 큰 정사각형을 구하면 해당 정사각형으로 전체 직사각형을 나누는 것도 가능하다. 이는 유클리드 호제법에서 증명된 것이므로 믿고 진행하면 된다.)

 

 

Pseudo code

n개의 요소로 이루어진 (정렬되지 않은) 배열이 있을 경우,
배열에서 기준 원소(Pivot)를 선택한다.
기준 원소 기준으로 왼쪽에는 작은 수의 원소, 오른쪽에는 큰 수의 원소를 정렬한다.
왼쪽과 오른쪽 배열에서 기준 원소를 선택한다.
기준 원소 기준으로 왼쪽에는 작은 수의 원소, 오른쪽에는 큰 수의 원소를 정렬한다.
... 
배열을 쪼갤 수 없다면(원소가 1개) 정렬을 종료한다.

 

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/resources/quick-sort-001.gif

 

 

Python code

def quicksort(array):
    if len(array) < 2:
        return array
    else:
    	pivot = array[0]
    	less = [i for i in array[1:] if i <= pivot]
    	greater = [i for i in array[1:] if i > pivot]

    	return quicksort(less) + [pivot] + quicksort(greater)

quicksort([5,1,6,7,8,3,0,4,9,10,2])
// result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

온라인 컴파일러에서 테스트 해보기

 

 

시간복잡도

퀵정렬은 시간복잡도는 O(NlogN)이다.

 

 

장단점

장점

• 한 번 결정된 피벗들은 이후 연산에서 제외되기 때문에, 시간 복잡도가 O(NlogN)인 다른 정렬 알고리즘들과 비교했을 때도 빠르다.
• 메모리 낭비가 없기 때문에 메모리가 제한적인 경우에 사용하기 좋다.

 

단점

• 불안정(Unstable)하다.
  - 불안정 정렬: 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 ( 퀵 정렬, 선택 정렬 )
• 매 순간 선택되는 Pivot이 최소 or 최댓값이라 한쪽으로만 원소들이 치우쳐져 정렬되는 경우 연산 속도가 느려진다. 즉 이미 정렬된 배열에 대해서는 처리 속도가 더 느리다.
  - 최악의 시간복잡도 O(N^2)

https://www.slideshare.net/imsnj/quick-sort-algorithm-discussion-and-analysis

 

 

---

참고 자료

• https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://www.slideshare.net/imsnj/quick-sort-algorithm-discussion-and-analysis
• https://gyoogle.dev/blog/algorithm/Quick%20Sort.html
• https://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5