[TIL 2024.03. 29] 퀵 정렬 (w. 시간 복잡도)

퀵 정렬

퀵 정렬은 정렬 중에서도 힙 정렬, 병합 정렬 등과 함께 시간 복잡도가 빠른 편에 속하는 정렬 알고리즘이다.

 

퀵 정렬은 병합정렬 처럼 "분할정복" 방식을 사용하는 알고리즘이지만, 퀵 정렬과 병합정렬의 차이는 이 분할이 불균등한지, 균등한지이다.

 

그리고 퀵 정렬은 "in-place"한 알고리즘이다. 즉, 합병정렬처럼 새로운 배열과 이를 저장할 추가적인 공간을 필요로 하지 않는다. 퀵 정렬은 선택정렬, 버블정렬, 삽입정렬과 마찬가지로 정렬하고자 하는 배열내에서 모든 작업이 이뤄진다

 

또 퀵 정렬은 "불안정 정렬"이다. 불안정 정렬과 안정 정렬은 "중복된 값"의 처리를 어떻게 할지에 대한 것이다.

 

즉, 안정정렬은 중복된 값이 있을 때 이를 기존의 입력 순서와 동일하게 정렬하는 것인 반면 불안정 정렬은 중복된 요소가 있을 때 기존의 정렬 순서와 상관없이 무작위로 뒤섞은 상태로 정렬하는 것을 말한다.

 

정리하면, 안정 정렬의 예는 병합정렬이고, 불안정 정렬의 예는 퀵 정렬과 힙 정렬 등이다.

(참고자료_블로그 페이지 바로가기)

 

---

퀵 정렬 동작과정

1. 피벗을 하나 선택한다

2. 피벗 값을 기준으로 양쪽에서 피벗보다 큰 값 혹은 작은 값을 찾는다

이때, 왼쪽(lo)에서는 피벗값보다 큰 값을 찾을 때까지 이동하고, 오른쪽(hi)에서는 피벗값보다 작은 값이 나올 때까지 이동한다.

3. 2번 과정이 끝나면 해당자리의 lo와 hi를 교환한다(swap)

4. 양쪽에서 탐색하는 위치가 엇갈릴 때까지 2번으로 돌아가서 위의 과정을 반복한다.

5. 엇갈린 지점에서는 lo<hi는 조건을 만족하지 못하므로, 해당 lo/hi요소와 피벗값을 교환한다(swap)

이때, 피벗이 왼쪽에 있었다면 lo와 피벗을, 피벗이 오른쪽에 있었다면 hi와 피벗을 교환한다 (-> 피벗값의 위치가 고정된 것임)

6. 위치가 확정된 피벗값을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 될 때까지 1번 과정을 반복한다 (=Divide 분할)

7. 분할되어 정렬을 마친 부분리스트들을 인접한 부분리스트들끼리 합친다 (=Conquer 정복)

 

손으로 그림을 그려가며 직접 해보니 개인적으로 주의해야겠다고 생각했던 부분들!

• 피봇이 왼쪽(lo)에 있다면 hi쪽부터 탐색을 시작하고, 피봇이 오른쪽(hi)에 있다면 lo쪽부터 탐색을 시작한다
• lo, hi는 swap한 후에도 '값'이 아니라 '자리'를 따른다
• lo<hi를 만족하지 못하면 해당 lo/hi값과 피벗을 교환한다(swap)
  
  • lo와 hi에 피벗의 위치에 따라 탐색 우선순위가 있다고 보고_피벗이 왼쪽에 있으면 lo와 피벗을, 피벗이 오른쪽에 있으면 hi와 피벗을 swap한다 (lo와 hi가 이미 엇갈려 지나갔다고 보는 경우에는 왼쪽_hi, 오른쪽_lo로 볼 수 있지만, 최악의 시간 복잡도를 설명할 때는 개인적으로 탐색 순서가 있다고 보는 게 이해가 편해서 이렇게 정리함)
• lo/hi와 피벗값이 swap되고 나면, 해당 피벗은 자리가 고정된 것이다(자기 자리를 찾은 것!)
• 오른쪽과 왼쪽에서의 탐색이 엇갈리기 전까지 여러번의 swap이 있을 수 있다(=3번)
• (피벗이 왼쪽에 있든 오른쪽에 있든) 해당 피벗은 탐색에서 제외한다

 

아래 그림은 개인적으로 구글링 해보던 중에 퀵 정렬에 대해서 가장 자세하게 설명하고 있어 많은 도움을 받은 블로그에 있던 퀵 정렬의 동작 과정을 그림으로 정리한 것이다

피벗이 오른쪽에 있는 경우

 

즉, 4)의 과정에서 피벗값이었던 7의 위치가 고정되었고, 이를 기준으로 다시 부분리 스트가 나눠지고 각자의 피벗이 선택된 후 재귀적으로 동일한 과정을 이어가고 있다. 따라서 분할 과정을 한 번 거칠 때마다 피벗이 제 위치를 찾아가므로, 언젠가는 배열이 정렬될 수밖에 없다. 위 그림이 이해에 가장 큰 도움을 준 그림이다!! (감사합니다 ㅜㅜ)

해당 게시글에는 피벗이 왼쪽/오른쪽/중앙일 때의 동작과정이 상세히 정리되어 있다

(참고자료: 해당 블로그 게시물 바로가기)

---

시간복잡도

 

 

퀵 정렬의 시간복잡도는 평균적으로 O(nlogn)으로 빠른 편에 속한다.

일반적으로 정렬 알고리즘 중에 퀵 정렬이 가장 빠르다고 하며, 위 표의 run-time을 통해서도 그 사실을 확인할 수 있다.

 

사실 해당 표를 보면 최악이 O(n^2)인 퀵 정렬이 어떻게 최악의 경우도 O(nlogn)인 힙 정렬이나 병합정렬보다 빠른 건지 의아할 수 있다.

 

하지만 이때는 우리가 빅오 표기법을 배웠을 때를 상기해야 한다. 즉, 우리는 빅오 표기법을 배울 때 '최고차항을 제외한 나머지는 무시한다'라고 배웠다. 따라서 같은 O(n)이어도 "400*n"일 수도 있고, "100*n"일 수도 있는 것이다.

 

퀵 정렬은 힙 정렬과 병합정렬보다 평균적으로 nlogn에 곱해지는 수가 적어서 결과적으로 실제 연산 속도(평균 시간 복잡도)는 가장 빠른 것으로 알려져 있다.

 

하지만 배열이 정렬(오름차순/내림차순)된 경우에 최솟값 혹은 최댓값(맨 왼쪽 혹은 맨 오른쪽)을 피벗으로 선택해서 퀵 정렬을 사용하는 경우에는 최악의 시간복잡도로 O(n^2)를 얻게 된다.

 

 

하지만 일반적으로 퀵 정렬의 시간 복잡도는 최악의 경우가 아닌 평균적인 경우를 이야기한다.

왜냐하면 최악의 경우가 발생될 확률은 인위적으로 만들지 않는 이상 거의 0에 수렴하므로, 최악의 경우를 따지는 건 큰 의미가 없다.

 

또한 그럼에도 희박한 확률로 발생할 수 있는 최악의 시간 복잡도 O(n^2)는 뒤에 언급하는 방법들로 방지할 수 있다.

 

해결책

1. 랜덤 피벗

피벗을 맨 앞(왼쪽)의 원소나 맨 뒤(오른쪽)의 원소로 선택하지 않고, 랜덤하게 피벗을 선택하는 방법이다.

2. Median of three pivot

피벗을 임의의 한 원소로 선택하는 것이 아니라, 3개의 원소(일반적으로 맨 앞, 중간, 맨 뒤)를 후보로 두고, 그 중간값을 선택하는 방법이다

3. 배열의 랜덤화 (Randomization)

새로운 함수를 정의함으로써 배열에서 랜덤한 인덱스를 뽑고, 그 두 인덱스의 값을 인위적으로 뒤바꿔주는 방식으로 배열이 정렬되는 경우를 방지한다. 앞서 '피벗'을 랜덤하게 선택하는 것과는 달리 '배열' 자체를 랜덤하게 섞어주는 방식이고, 해당 suffle_array()함수를 추가해주기만 하면 되므로 실제 적용이 용이하다

import random

def shuffle_array(arr):
    for i in range(len(arr)):
        rand_index = random.randint(0, len(arr) - 1)
        arr[i], arr[rand_index] = arr[rand_index], arr[i]

 

 

 

 

참고자료

https://st-lab.tistory.com/250 

https://nx006.tistory.com/67?category=994021

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ljy9378&logNo=221508655059

https://readerr.tistory.com/46

https://velog.io/@haero_kim/정렬-세계관-최강자-Quick-Sort

https://loosie.tistory.com/237

https://www.notion.so/b10d21e0bbea41afb1c2fc2229ef3520