[알고리즘] 퀵 정렬에 관하여

• 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다.
• 병합정렬 (Merge Sort) 알고리즘과 함께 라이브러리 근간이 되는 정렬 알고리즘이다

코드 (자바스크립트)

function quckSort(array, start, end) {
  if (start >= end) {
    return;
  }

  let pivot = start;
  let left = start + 1;
  let right = end;

  while (left <= right) {
    while ((left <= end) && array[left] <= array[pivot]) {
      left += 1;
    }

    while ((right > start) && array[right] >= array[pivot]) {
      right += 1;
    }

    if left > right {
      [array[pivot], array[right]] = [array[right], array[pivot]];
    } else {
      [array[left], array[right]] = [array[right], array[left]];
    }
  }

  quickSort(array, start, right - 1);
  quickSort(array, right + 1, end);
}

 

시간 복잡도

• 퀵 정렬의 시간 복잡도는 보통 O(N * log N) 이다
  • 최악 - O(N2)
  • 최고 - O(N * log N)
• 퀵 정렬은 `이미 정렬되어 있는 경우`에는 매우 느리게 동작한다
  • ‘이미 데이터가 정렬되어 있는 경우’ - O(N2)
  • ‘무작위로 입력된 데이터’ - O(N * log N)
  • 이것은 삽입 정렬과 반대된다

설명

• 파트 1 - 리스트 파티션
  • a) 리스트의 첫 번째 데이터를 pivot으로 설정한다
  • b) Pivot을 기준으로 보다 크고 작은 데이터를 찾는다
    • i) pivot이 아닌 왼쪽 데이터부터 pivot보다 큰 데이터를 찾고 선택한다
    • ii) 오른쪽 데이터부터 pivot보다 작은 데이터를 찾고 선택한다
    • iii) i) 그리고 ii)에서 선택한 데이터의 위치를 바꾼다
  • c) Pivot을 기준으로 그다음 보다 크고 작은 데이터를 찾는다
  • d) 왼쪽 위치 값과 오른쪽 위치 값이 서로 엇갈릴때까지 b)를 반복한다
  • e) d) 에서 두 위치 값이 엇갈렸을때 작은 데이터와 pivot의 위치를 서로 변경한다
• 파트 2 - 왼쪽 리스트 파티션 (재귀 함수 사용)
  • a) 왼쪽 리스트에서는 다음 그림과 같이 정렬이 되며 정렬과정은 동일하다
• 파트 3 - 오른쪽 리스트 파티션 (재귀 함수 사용)
  • a) 오른쪽 리스트에서는 다음 그림과 같이 정렬이 되며 정렬과정은 동일하다

 

 

참고

1. 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈: https://books.google.ca/books?id=vBz-DwAAQBAJ&source=gbs_book_other_versions