Algorithm - Quick Sort, Radix Sort

Quick Sort

• Merge Sort와 같이, 비어 있거나 요소가 1개인 배열은 항상 정렬되어 있다는 사실을 이용함
• 한 요소를 선택해서 pivot 변수에 할당하고, pivot 변수를 기준으로 작은 값들은 pivot 변수 왼쪽으로 이동시키고 큰 값들은 pivot 변수의 오른쪽으로 이동시켜서 pivot 변수의 정렬된 배열에서의 index값을 얻음
• pivot 변수의 왼쪽 또는 오른쪽에서 한 요소를 선택하고 pivot 변수에 할당해서 위 과정을 반복함
• 모두 정렬된 배열을 반환함

Pivot Helper function

• 배열(arr), 시작 index(기본값: 0), 끝 index(기본값: arr.length - 1)를 인자로 받음
• 배열의 첫 번째 요소를 pivot으로 선택함 (가운데, 랜덤 요소를 선택 가능함)
• 현재 pivot index를 변수에 저장함
• 배열의 시작부터 끝까지 순회함
  • pivot이 현재 요소보다 크다면, 변수에 저장한 pivot index값을 증가시키고 현재 요소와 pivot index에 해당하는 요소의 자리를 바꿈
• 시작했을 때의 요소와 pivot index에 해당하는 요소의 자리를 바꿈
• pivot index를 반환함

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
  let pivot = arr[start];
  let swapIdx = start;
  
  for(let i = start + 1; i <= end ; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }
  swap(arr, start, swapIdx);
  return swapIdx;
}

console.log(pivot([4, 8, 2, 1, 5, 7, 6, 3]));

Quick Sort function

• 주어진 배열에 대해 pivot helper 함수를 호출함
• helper 함수가 pivot index를 반환하면, pivot index의 왼쪽에 해당하는 배열과 pivot index의 오른쪽에 해당하는 배열에 대해서 회귀적으로 pivot helper 함수를 호출함
• pivot helper 함수에 들어가는 배열의 길이가 2보다 작을 경우, 회귀를 중단함
• 정렬된 배열을 반환함

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    // left
    quickSort(arr, left, pivotIndex - 1);
    // right
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

console.log(quickSort([4, 6, 9, 1, 2, 5, 3]));

Big O Notation of Quick Sort

• Time Complexity
  • Best : O(NlogN) = O(logN) 배열 분해 + O(N) 분해된 배열 요소 비교
  • Average : O(NlogN)
  • Worst(already sorted) : O(N^2) O(N) 배열 분해 (요소가 1개씩 분해되므로) + O(N) 분해된 배열 요소 비교
    • 최소값 또는 최대값을 pivot으로 고를 때도 시간 복잡도가 O(N)이 걸리므로 배열의 첫 번째 요소보다는 배열의 중간 요소나 랜덤 요소를 고르는 것이 나음
• Space Complexity : O(logN)

Comparison Sorts

• Comparison Sorting Algorithm : Bubble, Selection, Insertion, Merge, Quick Sort
• Comparsion Sort는 주어진 시간에 두 가지 요소를 비교함
• Average Time Complexity of Comparsion Sort
  • Bubble Sort : O(N^2)
  • Insertion Sort : O(N^2)
  • Selection Sort : O(N^2)
  • Merge Sort : O(NlogN)
  • Quick Sort : O(NlogN)

Radix Sort

• 정수들의 배열에서 수행 가능한 특별한 정렬 알고리즘
• Comparision Sort보다 빠름
• 요소들끼리 직접 비교하지 않음
• 숫자의 크기에 대한 정보는 자리수로 전환됨
  • 자리수가 많을 수록 더 큰 숫자임
  • 맨 아래 자리 수부터 맨 위 자리 수까지 올라가면서 각 자리 수에 해당되는 숫자로 그룹화해서 정렬함

Radix Sort Helpers

• radix sort를 수행하기 위해서 몇개의 helper 함수를 만드는 것이 도움이 됨
  • getDigit(num, place) : 숫자 num에서 주어진 자리값 place에 해당하는 자리수를 반환하는 함수
  • digitCount(num) : 숫자 num의 자리수의 개수를 반환하는 함수
  • mostDigits(nums) : 주어진 숫자 배열 nums에서 가장 큰 숫자의 자리수의 개수를 반환하는 함수 (digitCount 함수를 이용함)

function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

getDigit(12345, 0); // 5
getDigit(12345, 1); // 4
getDigit(12345, 2); // 3
getDigit(12345, 3); // 2
getDigit(12345, 4); // 1
getDigit(12345, 5); // 0

function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

digitCount(1); // 1
digitCount(25); // 2
digitCount(324); // 3

function mostDigits(nums) {
  let maxDigits = 0;
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]));
  }
  return maxDigits;
}

mostDigits([1234,56, 7]); // 4
mostDigits([1, 1, 11111, 1]); // 5
mostDigits([12, 34, 56, 78]); // 2

Radix Sort function

• 숫자들의 배열만 받아들이는 함수를 정의함
• 가장 큰 숫자의 자리수 개수를 계산함
• 변수 k가 0부터 가장 큰 숫자의 자리수 개수까지 증가하는 반복문을 실행함
  • 0부터 9까지의 자리수에 해당하는 빈 배열을 생성함
  • k번째 자리수를 기준으로 대응되는 배열에 각 숫자들을 넣음
  • 기존의 배열을 0부터 9까지의 자리수에 해당하는 배열에 담긴 숫자들로 바꿔줌
• 반복문이 종료된 후, 정렬된 배열을 반환함

function radixSort(nums) {
  const maxDigitCount = mostDigits(nums);
  for (let k = 0; k < maxDigitCount; k++) {
    let digitBuckets = Array.from({length: 10}, () => []);
    for (let i = 0; i < nums.length; i++) {
      const digit = getDigit(nums[i], k);
      digitBuckets[digit].push(nums[i]);
    }
    nums = [].concat(... digitBuckets);
  }
  return nums;
}

console.log(radixSort([23, 345, 5467, 12, 2345, 9852]));

Big O Notation of Radix Sort

• Variables in Time Complexity & Space Complexity
  • N : 배열의 길이
  • K : 자리수의 개수
• Time Complexity : O(NK) (Best ~ Average ~ Worst)
  • 랜덤으로 분포된 고유한 데이터를 다룰 때는 O(NlogN)이 됨
• Space Complexity : O(N + K)