Quick Sort

• 배열을 입력 받았을 때 기준이 되는 요소를 정해서 기준이 되는 요소보다 작은 요소들은 왼쪽에 배치, 기준 요소보다 큰 요소들은 오른쪽에 배치하며 오름차순으로 정렬하는 알고리즘.

시간복잡도를 고려하지 않은 퀵소트 구현

const quickSort = function (arr) {
  // 기준 요소 만들기
  let mid = [arr[0]];
  // 기준요소보다 왼쪽에 갈 배열, 오른쪽에 갈 배열 생성
  let left = [];
  let right = [];

  // arr 탐색 -> 기준요소를 arr[0]번째로 설정했으니까 1번째부터 탐색
  for(let i=1; i < arr.length; i++) {
    // 미드보다 작으면 왼쪽에 집어넣는다.
    if(arr[i] < mid) {
      left.push(arr[i]);
    } else if(arr[i] > mid) {
      // 미드보다 크면 오른쪽에 집어넣는다.
      right.push(arr[i]);
    } else {
      // 그 외
      mid.push(arr[i]);
    }
  }

  // for문이 다 돌고나면 left + mid + right 형태로 만들어준다.
  return quickSort(left).concat(mid, quickSort(right));
};

In Place를 이용한 퀵소트 구현

const quickSort = function (arr, left = 0, right = arr.length - 1) {

  if(left >= right) {
    return;
  }

  let mid = Math.floor((left + right) / 2);
  // 기준 요소
  let pivot = arr[mid];

  let divide = (arr, left, right, pivot) => {
		
    while(left <= right) {
      // 기준요소랑 비교해서 작으면 계속 한칸씩 옮긴다.
      while(arr[left] < pivot) {
        left++;
      }

      // 기준요소랑 비교해서 크면 계속 한칸씩 옮긴다.
      while(arr[right] > pivot) {
        right--;
      }

      // left요소랑 right요소 자리 바꿈
      if(left <= right) {
        let swap = arr[left];
        arr[left] = arr[right];
        arr[right] = swap;

        left++;
        right--;
      }
    }
    return left;
  }

  const partition = divide(arr, left, right, pivot);

  quickSort(arr, left, partition-1);
  quickSort(arr, partition, right);

  return arr;
};