참고문헌

퀵소트란

  • 과정

    1. 리스트 안에 있는 한 요소를 선택한다. 이 요소를 피벗이라 한다.
    2. 좌측과 우측 포인터가 각각 가장자리부터 시작해서 점진적으로 진행해 나가는데
    3. 두 포인터가 서로 교차할 때까지 다음을 반복한다.
      1. 이때 좌측 포인터는 피벗보다 큰 수를 만난 경우 멈추고 해당 숫자를 가리키고
      2. 우측 포인터는 피벗보다 작은 수를 만난 경우 멈추고 해당 숫자를 가리킨다.
      3. 두 포인터가 가리키는 숫자의 위치를 바꾼다.
    4. 피벗을 마지막에 두 포인터가 교차했던 위치에 끼워 넣는다
    5. 피벗을 기준으로 좌측 리스트(피벗보다 작은 요소들)와 우측 리스트(피벗보다 큰 요소들)에 대해서 1~4를 반복한다.
    6. 피벗 하나만 남는 상황까지 분할-정복(divide & conquer)가 끝나면 요소들을 이어 붙이면 정렬이 끝난다

  • 특징

    1. 피벗을 기준으로 나눠지는 리스트의 크기가 불균등하다는 점에서, merge-sort와 구별된다.

    2. 장점 : 속도가 빠르다

      • 시간복잡도가 O(n log2n)인 다른 정렬 알고리즘과 비교했을 때에도 가장 빠르다
      • 왜 빠를까?
        • 먼 거리의 데이터를 교환할 수 있어서 불필요한 데이터 이동을 줄일 수 있고, 각 depth별 선택된 피벗들은 추후 연산에서 제외되기 때문이다
      • 이때 시간 복잡도는 depth인 n log2n, 각 depth별 비교횟수인 n을 곱한 값이다
      • depth는 왜 log2n인가
        • 첫번째 피벗 피킹 시 : 요소개수가 n개인 그룹에 대한 n번의 비교
        • 두번째 피벗 피킹 시 : 요소개수가 n/2인 두 그룹에 대해 각각 피벗 피킹하여 n/2번씩 비교
        • …
        • 결국 요소개수가 1인 그룹으로 분할될 때까지, 즉 정렬이 끝날때까지이므로 2로 거듭해서 나누었을 때 나눌 수 있는 횟수, log2n이 depth가 되는 것이다.
        • 그리고 그룹이 작아져서 m개의 그룹이 되더라도 총 비교횟수는 n/m * m = n 으로 동일하다 (물론 이전까지의 피벗들은 연산에서 제외되기 때문에, 엄밀히 말하면 n보다 점차 작아지게 된다)
    3. 단점 : 최악의 경우 (이미 정렬된 리스트) 시간이 오래 걸린다.
      • 불균등 분할의 단점이라고도 할 수 있다.
      • 정렬된 리스트의 경우, 피벗을 맨앞의 수로 잡는다고 가정할 때 맨앞의 하나를 계속 잡고 나머지 n개와 비교해나가야 한다 : depth도 n, 비교횟수도 n이라 O (n^2)이 걸리게 된다.

  • 요약

    • 평균 시간복잡도 : O(nlog2n)
    • 최악의 경우 : O(n^2)