Quick Sort (with JavaScript)

# Quick Sort

이름 그대로 매우 빠른 속도의 정렬 방법이며 divide and conquer algorithm을 사용하는 정렬이다.

Merge sort나 heap sort에 비해서도 살짝 빠르다고 한다.

Quick sort는 in-place algorithm이고 unstable하다. 따라서, 메모리를 크게 요구하지 않으며 같은 값을 가지는 index의 순서 정렬은 보장되지 않는다.

평균적으로 O(nlogn), worst case인 경우 O(n²)의 시간 복잡도를 가진다.

 

# Process

Quick sort는 divide and conquer 방법을 사용한다.

Input의 값 중 임의의 값 하나를 pivot으로 삼아 이것과의 상대적인 크기로 partition을 나누고, 각각의 partition에 대해서 이 동작을 재귀적으로 반복하며 sorting을 진행한다.

pivot을 정하는 방법은 다양하다고 하나, 간편하게 가장 왼쪽 값을 pivot으로 삼도록 한다.

 

• Input의 가장 왼쪽 값을 pivot으로 정하고 그 외 나머지를 기준으로 왼쪽에서 오른쪽으로 이동하며(left mark) pivot보다 큰 값을, 오른쪽에서 왼쪽으로 이동하며(right mark) pivot보다 작은 값을 찾는다.
• 각각 해당하는 값을 찾으면 두 값을 swap 한다.
• 위 동작을 left mark와 right mark가 엇갈리기 전까지 반복한다.
• Left/right mark가 엇갈리면 right mark(pivot보다 작은 값)과 pivot을 swap한다.

• 위 과정을 통해 pivot의 왼쪽 element는 무조건 pivot보다 작은 값을 가지고, 오른쪽 element는 pivot보다 큰 값을 가지게 된다.
• Pivot의 왼쪽 partition과 오른쪽 partition에 대해서도 위 과정을 재귀적으로 반복한다.
• Partition의 크기가 0이거나 1인 경우 종료한다.

 

# JavaScript로 구현

function swap(array, leftIndex, rightIndex) {
  let temp = array[leftIndex];
  array[leftIndex] = array[rightIndex];
  array[rightIndex] = temp;
}

function quickSort(array, start, end) {
  if (start >= end) return; // 종료 조건

  let pivot = array[start];
  let left = start + 1;
  let right = end;

  // left right가 엇갈릴 때까지 swap 반복
  while (left <= right) {
    while(array[left] < pivot && left <= end) {
      left += 1;
    }
    while(array[right] > pivot && right > start) {
      right -= 1;
    }
    if (left < right) {
      // 엇갈리지 않은 경우
      swap(array, left, right);
    } else {
      // 엇갈린 경우
      swap(array, start ,right);
    }
  }

  // 각 sub array에 대해 재귀 함수 호출
  quickSort(array, start, right - 1);
  quickSort(array, right + 1, end);
}