알고리즘 05 정렬 | 퀵소트 | JS

퀵소트 | Quick sort

이미지 출처

• 분할정복을 통해 구현
• 시간복잡도(최악): O(n^2)
• 시간복잡도(최선): O(n*logn)
• 분할이 극단적으로 일어나지만 않는다면 대체로 n*logn으로 수렴

Pivot 값

• 첫번째 값이나 마지막 값을 pivot으로 선택
  이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우
  현실의 데이터는 랜덤하지 않으므로 (거꾸로) 정렬된 데이터가 입력으로 들어올 가능성은 매운 ㅗㅍ음
  따라서 좋은 방법이라고 할 수 없음

• Median of Three
  첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 pivot으로 선택
  최악의 경우 시간복잡도가 달라지지 않음

• Randomized quickSort
  pivot을 랜덤하게 선택
  no worst case instance, but worst case execution
  평균 시간복잡도 O(NlogN)

구현

// 본인 구현
// 마지막 요소를 pivot으로 두고 앞의 값들과 비교
// pivot값보다 작은 경우와 큰 경우로 나누어 좌측, 우측으로 몰아넣음
// i+1값과 pivot 값을 swap
// 위의 gif 이미지와 동일하게 작업을 수행

unction quickSort(arr) {
  if (arr.length <= 1) return arr

  let i = -1;
  let j = 0;
  let pivot = arr[arr.length - 1]
  let temp = null
  
  while (j < arr.length) {
    if (arr[j] < pivot || j === arr.length - 1) {
      temp = arr[i + 1]
      arr[i + 1] = arr[j]
      arr[j] = temp
      i++
    }
    j++
  }
  return [...quickSort(arr.slice(0, i)), arr[i], ...quickSort(arr.slice(i + 1))]
}

const arr = [31, 8, 48, 8, 73, 11, 3, 20, 8, 29, 65, 15]
console.log(quickSort(arr));

// zerocho 구현
var partition = function(array, left, right, pivotIndex) { // 정렬하는 부분
  var temp;
  var pivot = array[pivotIndex];
  while (left <= right) { // 왼쪽, 오른쪽 수를 규칙과 비교해 다음 수로 넘어갑니다.
    while (array[left] < pivot)
      left++;
    while (array[right] > pivot)
      right--;
    if (left <= right) { // 왼쪽이 기준보다 크고, 오른쪽이 기준보다 작으면
      temp = array[left];
      array[left] = array[right];
      array[right] = temp; // 서로 바꿔줍니다.
      left++;
      right--;
    }
  }
  temp = array[left];
  array[left] = array[pivotIndex];
  array[pivotIndex] = temp; // 마지막으로 기준과 만난 수를 바꿔줍니다. 기준의 위치는 이제 i입니다.
  return left;
};

var quickSort = function(array, left, right) { // 재귀하는 부분
  if (!left) left = 0;
  if (!right) right = array.length - 1;
  var pivotIndex = right; // 배열 가장 오른쪽의 수를 기준으로 뽑습니다.
  pivotIndex = partition(array, left, right - 1, pivotIndex); // right - 1을 하는 이유는 기준(현재 right)을 제외하고 정렬하기 위함입니다.
  if (left < pivotIndex - 1)
    quickSort(array, left, pivotIndex - 1); // 기준 왼쪽 부분 재귀
  if (pivotIndex + 1 < right)
    quickSort(array, pivotIndex + 1, right); // 기준 오른쪽 부분 재귀
  return array;
};

quickSort([4,1,7,6,3,8,2,5]); // [1,2,3,4,5,6,7,8]

📚 참고

YOUTUBE | 2015 봄학기 알고리즘 | 권오흠
퀵 정렬(quick sort) by.zerocho

Photo by Michael Dziedzic on Unsplash