[Algorithm] 퀵 정렬 (Quick-sort)

퀵 정렬 (Quick-sort) 🤔

퀵 정렬이란 찰스 앤터니 리처드 호어가 개발한 분할 정복 알고리즘의 하나로, 평균적으로 타 정렬 방식에 비해 빠른 수행 속도를 자랑하는 정렬 방법이다. 여기서 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이며, 대개 순환 호출(재귀)을 이용하여 구현한다.
또한 n개의 데이터를 정렬할 때 평균적으로 O(nlogn)의 시간복잡도를 가지며, 최악의 경우 O(n^2)의 시간복잡도를 가지게된다.

과정 ✍️

• 일반적으로 퀵정렬에는 특정 기준값이 필요하다. 이를 피벗(pivot)이라 한다.

• 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗을 중심으로 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.

• 피벗을 제외한 양쪽 리스트들을 순환 호출을 이용하여 위 방법대로 다시 정렬한다.

• 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

예제 📝

이미지 출처 - https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html -

• 먼저 [5, 3, 8, 4, 9, 1, 6, 2,7]이란 배열을 오름차 순으로 정렬 시 배열의 0번째 인덱스 값을 pivot으로 지정해준다. 그 후 pivot의 오른쪽 방향으로 pivot보다 큰 값을 탐색하고, 배열의 마지막 인덱스 에서부터 왼쪽 방향으로 pivot보다 작은 값을 탐색한다.
• 첫 탐색 시 pivot(5) 보다 큰 값은 8, 그리고 작은값은 2로 탐색이 끝났으면 두값의 위치를 교환해준다.
  그 후에도 pivot은 여전히 5이며, 다시 위의 방법처럼 탐색을 시작한다.
• 이번엔 큰값 9와 작은값 1이 탐색됬으므로, 둘의 위치를 교환한다.
• 또 다시 탐색을 시작하게되고, 이번에도 큰값 9와 작은값 1이 탐색됬지만, 큰 값의 인덱스가 작은 값의 인덱스보다 크므로 이를 엇갈림이라 표현하고, 작은값과 pivot의 위치를 교환한다.
• 이제 pivot의 위치가 맨 앞이 아니므로 pivot을 기준으로 양 옆 리스트의 각각 첫 인덱스를 pivot으로 칭한 후 위와 같은 과정을 반복시킨다.

구현 🔥

const quickSort = function (arr, cb) {
  const sort = (start, end) => {
    if (start > end) { //계속 분할되어 pivot(start)가 end보다 커지는 시점에 탈출.
      return;
    }
    let pivot = arr[start]; //배열의 0번째 값을 pivot으로 지정
    let left = start + 1; //큰 값을 탐색 할 첫 지점
    let right = end; // 작은 값을 탐색할 첫 지점

    while (left <= right) { // 엇갈릴 때 까지 반복
      while (left <= end && pivot >= arr[left]) {
        // 큰 값 탐색
        left++;
      }
      while (right > start && pivot <= arr[right]) {
        // 작은 값 탐색
        right--;
      }

      if (left > right) {
        curr = arr[right];
        arr[right] = arr[start];
        arr[start] = curr;
      } else {
        curr = arr[left];
        arr[left] = arr[right];
        arr[right] = curr;
      }
    }
    sort(start, right - 1);
    sort(right + 1, end);
  };
  sort(0, arr.length - 1);
  return arr;
};