퀵 정렬(quick sort)

•정의

가장 애용되는 정렬 알고리즘. O(nlogn)의 시간 복잡도와 복잡도가 동일한 여타 정렬 알고리즘보다 성능이 낫다.
분할/정복 방식으로 접근, 원소를 하나 가진 배열까지 잘게 쪼개지 않는다.

•코드

const swapQuickSort = (array, index1, index2) => {
      let aux = array[index1];
      array[index1] = array[index2];
      array[index2] = aux;
    };
const partition = (array, left, right) => {
      let pivot = array[Math.floor((left + right) / 2)];
      (i = left), (j = right);
      while (i <= j) {
        //i와 j의 위치가 역전될 때까지 파티션을 반복
        while (array[i] < pivot) {
          //pivot보다 크거나 같은 원소를 찾을 때까지 좌측 포인터를 우측으로 이동
          i++;
        }
        while (array[j] > pivot) {
          //pivot보다 작거나 같은 원소를 찾을 때까지 우측 포인터를 좌측으로 이동
          j--;
        }
        if (i <= j) {
          swapQuickSort(array, i, j);
          i++;
          j--;
        }
      }
    };
const quick = (array, left, right) => {
      let index;
      if (array.length > 1) {
        index = partition(array, left, right);
        if (left < index - 1) {
          quick(array, left, index - 1);
        }
        if (index < right) {
          quick(array, index, right);
        }
      }
    };
 const quickSort = () => {
      quick(array, 0, array.length - 1); //정렬할 배열과 처음/끝 인덱스를 인자로 재귀 호출
    };