56. Quick Sort (퀵 정렬) 파헤치기

이번 블로그에서는 퀵 정렬의 새롭게 알게된 부분부터, 과거에 잘못알았던 부분까지 총정리한다.

코드는 맨 아래에 자세하게 비교해두었다.

먼저 퀵 정렬(Quick Sort)은 1962년 '호어(C. A. R. Hoare)'가 고안한 알고리즘이다.

일반적인 시간 복잡도는 평균적으로 O(nlogn), 최악의 경우 O(n^2)의 시간이 소요된다.

여기서 말하는 최악의 경우란, 정렬하는 배열이 이미 정렬되어 있거나, 거의 정렬된 상태를 지칭한다.

그래서 어떻게보면 앞서 소개한 Insertion Sort와 반대의 성질을 가지고 있다.

퀵 정렬의 복잡도는 다른 알고리즘 Heap Sort 또는 Merge Sort보다 뛰어난 것은 아니다. 

하지만, 실제로 수행했을 때 다른 정렬 알고리즘보다도 빨라서 가장 많이 쓰이는 알고리즘이 되었다.

퀵 정렬의 알고리즘을 딱 두가지 순서로 요약하면 이렇다.

(1) 기준 원소(pivot)를 선택한다.

(2) 기준 원소에 따라 검사 배열을 두 배열로 나눈다.

(3) 정렬될 때까지 위의 (1)~(2)를 반복한다.

*기준 원소는 어떤 원소이든지 관계없다.

아주 간단하다. 하지만 처음 접하는 사람이 막상 구현하려고 하면 어떤 방식인지 헷갈린다.

결국은 기준에 따라 두 분류로 나누고, 한 번 기준은 다시 검사하지 않는다. <<가장 핵심이지만 원리를 모르면 어렵다.

왜냐하면 한 번 기준 원소로 뽑히면, 그 기준 원소는 정렬되었다고 판단한다.

먼저 간단한 예시이다.

4 8 6 2 3 7 5 1 (4는 pivot이고 8부터 1까지 아래와 같은 순차 검사를 진행한다.)

*

(*은 현재 스왑 위치를 가리키고 최초 스왑 위치는 기준 원소인 pivot을 가리킨다.)

(Step 1) 8은 pivot보다 크므로 두 가지로 나뉘는 배열 중 후반부에 속한다.

(Step 2) 6은 8과 마찬가지이다.

(Step 3) 2는 pivot보다 작으므로 전반부 배열이다. 스왑 위치를 하나 먼저 증가시켜 다음 스왑 위치와 교환한다.

           (2 <-> 8)

4 2 6 8 3 7 5 1

   *

(Step 4) 3은 pivot보다 작으므로 전반부 배열이다. 스왑 위치를 하나 증가시켜 다음 스왑 위치와 교환한다.

           (3 <-> 6)

4 2 3 8 6 7 5 1

     *

(Step 5) 7은 pivot보다 크므로 후반부 배열에 속한다.

(Step 6) 5는 pivot보다 크므로 후반부 배열에 속한다.

(Step 7) 1은 pivot보다 작으므로 전반부 배열이다. 스왑 위치와 교환하고 스왑 위치를 하나 증가시킨다.

     (1 <-> 8)

4 2 3 1 6 7 5 8

        *

(Step 8) 모든 원소를 한번 순회했으면, 마지막으로 기준 원소와 현재 스왑 위치를 교환한다.

1 2 3 4 6 7 5 8

그 이유는 기준 원소대로 두 배열로 나뉜 것이기 때문에 제자리를 찾아준 것이다. <<중요중요

즉, 

1 2 3    4    6 7 5 8

이렇게 나뉜 것이다. 그리고 4는 이제 검사 대상에 포함되지 않는다.

나머지 1 2 3 배열과 6 7 5 8 배열을 각각 (Step 1) ~ (Step 8)까지 반복한다.

그러면 최종적으로 1 2 3 4 5 6 7 8 순으로 정렬된다.

여기까지가 기본 원리이다.

전반적이고 기본적인 퀵 정렬의 원리를 알았다면, 이제부터가 진짜 퀵 정렬의 시작이다.

먼저 기본적인 위의 과정은 기초적이지만 실제로 사용하기에는 제약이 따른다.

크게 4개의 문제가 있다.

(1) 랜덤 배열

(2) 이미 정렬되어 있는 배열

(3) 모두 0인 배열(또는 모든 원소가 같은 배열)

(4) 스택 오버플로우 문제 

아주 중요한 문제다!!! 이번에 알게 된 사실도 이 부분들이다.

이 포스팅의 핵심은 바로 이 부분부터이다.

왜 대부분의 프로그래머들이 정렬 라이브러리가 있고, 그 라이브러리의 정렬이 당신의 요구조건을 만족하면

절대로 직접 만들어 쓰지말라고 한 이유들이 바로 저런 문제들이다.

아래 코드를 보면, 퀵 정렬 알고리즘은 다양한 입력에 대해 빠르고 잘 작동하는 정렬 함수를 만들기가 상당히 어렵다.

여기서 다양한 입력이란 조건의 대표적인 예시들이 바로 위의 4가지 문제이다.

4가지의 코드가 있다.

첫 번째 코드는 위에 소개한 (Step 1) ~ (Step 8) 방식으로 움직이며, 랜덤 배열에서는 잘 동작하지만 이미 정렬되어 있는 배열

또는 모든 원소가 같은 배열 그리고 스택 오버플로우의 문제에 취약하다.

두 번째 코드는 첫 번째 코드에서 기준 원소를 랜덤하게 뽑아나가는 방식이다. 단, 하나의 코드만 추가되었다. 이 경우 랜덤 배열과 이미 정렬되어 있는 배열에서는 잘 동작하지만 나머지 (3) (4) 문제에는 취약하다.

세 번째 코드는 과거에 블로그에 포스팅한 코드로 완성형 코드인 네 번째 코드와 원리는 같다. 하지만 그 때 적었던 것처럼 어떤 문제가 있는 듯, 모든 (1) (2) (3) (4) 문제에 대해 취약하다. 이를 완벽히 보완한 코드가 바로 네 번째 코드이다. 

네 번째 코드는 완성형 코드로 위의 예시 과정과는 조금 다른 방식이다. 아마 일반적인 퀵 정렬 알고리즘이라고 한다면 이 세 번째 코드를 지칭한다. (1) (2) (3) (4) 모든 문제에 대해 가장 강력한 방식이다. 세 번째 코드의 방식과 원리는 똑같지만 훨씬 더 명료하게 작성되어 있다. (세 번째 코드는 뭔가 잘 안보이는 실수를 한 듯하다. 이유를 잘 모르겠다.)

-코드 Part-

(1) Quicksort_Seoul(), Partition_Seoul()

(2) Quicksort_Seoul2(), Partition_Seoul2()

(3) Old_Quicksort(), Old_Partition()

(4) Quicksort_Seoul_Final(), Partition_Seoul_Final()

-출력 Part-

(1) 데이터 크기 2000 - 크게 다르지 않다.

(2) 데이터 크기 3000 - 1번 코드와 2번 코드 4번 코드의 문제가 보인다.

(3) 데이터 크기 4000 - 전반적으로 각 코드마다 어떤 결과가 보이는지 가장 일목요연하다.

(4) 데이터 크기 5000, 10000, 100000, 1000000, 10000000 (3번 코드 제외하고 모든 코드 Stack Overflow 터짐)

여기까지가 퀵 정렬에 대해서 좀 더 자세히 알아보았다.

몇 개월 전에 올렸던 퀵 정렬의 문제가 무엇인지 조금 더 알 수 있는 시간이었고, 퀵 정렬의 구동방식이 이제 머릿속에

완전히 잡혔다.

퀵 정렬 내 인생 첫 면접에서, 

버블 정렬에 대해서 면접관님이 손 코딩 할 수 있냐고 질문하셨는데, 

그건 너무 쉬워서 잘 모르겠고 전 퀵 정렬밖에 안 사용합니다. 라고 말했다가 그대로 화이트보드에 퀵 정렬 손 코딩했다.

그 때, 짰던 코드가 바로 Old_Quicksort() 코드였다. 첫 손 코딩이라 진짜 개판이었는데 그래도 패기를 잘 보아주셔서 

합격했었다. 아마 그 때의 합격이 지금 내가 이렇게 꿈을 찾고 여기에 도달할 수 있게 만들었다.

그래서 더욱 퀵 정렬에 대해서 감사하고, 제대로 포스팅하고 싶었는데 이렇게 일단 마무리지어서 좋다.

더 공부하자.