앞서 이야기한 버블, 삽입, 선택 정렬은 규모가 큰 규모에는 맞지 않는다. 그에 비해 앞으로 이야기할 알고리즘들은 시간 복잡도를 O(N^2)에서 O(NlogN)으로 향상시킬 수 있다. 효율적이지만 복잡한 합병 정렬, 퀵 정렬, 지수 정렬 알고리즘들을 살펴보자!

📖 합병 정렬(Merge Sort)

합병 정렬에서의 기본적인 개념은 말 그대로 Merging - Sorting, 즉 합병과 정렬이라는 두 가지 조합의 개념으로 이루어져 있다. 합병 정렬은 0개 혹은 1개 요소의 배열이 이미 정렬되어있다는 것을 활용한다. 그리고 이는 배열을 더 작은 배열로 나누는 방식을 택한다. 그렇기 때문에 분할 정복 알고리즘이라 불리기도 한다.

합병 정렬은 다음과 같이 동작한다.

[8, 3, 5, 4, 7, 6, 1, 2]

[8, 3, 5, 4] [7, 6, 1, 2] //아직 1개나 0개 요소 배열이 아니다

[8, 3] [5, 4] [7, 6] [1, 2]//아직 1개나 0개 요소 배열이 아니다

[8] [3] [5] [4] [7] [6] [1] [2] //1개나 0개 요소 배열임 이제 합친다

[3, 8] [4, 5] [6, 7] [1, 2] //합치면서 정렬해준다

[3, 4, 5, 8] [1, 2, 6, 7] //합치면서 정렬해준다

[1, 2, 3, 4, 5, 6, 7, 8] //정렬 끗

✏️ Merge Solution

function merge(arr1, arr2){
    let results = [];
    let i = 0; //포인터 i와 j
    let j = 0;
    //포인터가 배열 끝까지 도는거임
    while(i < arr1.length && j < arr2.length){
    	//두 배열의 값 비교해서 작은값을 넣음(오름차순하기 위해)
        if(arr2[j] > arr1[i]){
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j])
            j++;
        }
    }
    
    //여기까지는 [1, 2, 10, 14, 50, 99] 이렇게 들어갈것
     
    while(i < arr1.length) {
        results.push(arr1[i])
        i++;
    }
    //여기까지는 [1, 2, 10, 14, 50, 99]
    
    while(j < arr2.length) {
        results.push(arr2[j])
        j++;
    }
    return results;     //[1, 2, 10, 14, 50, 99, 100]
}

merge([1, 10, 99], [2, 14, 50, 100]); //이 처럼 두 배열은 정렬되어있어야함

✏️ Merge Sort Solution

function merge(arr1, arr2){
    let results = [];
    let i = 0;
    let j = 0;
    while(i < arr1.length && j < arr2.length){
        if(arr2[j] > arr1[i]){
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j])
            j++;
        }
    }
    while(i < arr1.length) {
        results.push(arr1[i])
        i++;
    }
    while(j < arr2.length) {
        results.push(arr2[j])
        j++;
    }
    return results;
}


function mergeSort(arr){
	//얼리리턴 해주기
    if(arr.length <= 1) return arr;
    //배열의 절반에 적용
    let mid = Math.floor(arr.length/2);
    //왼쪽 오른쪽을 절반 기준으로 잘라 넣기
    //그 뒤 재귀적 호출
    let left = mergeSort(arr.slice(0,mid));
    let right = mergeSort(arr.slice(mid));
    //자르고 합치는것 반복하기
    return merge(left, sright);
}

mergeSort([10,24,76,73])

✏️ Big O of Merge Sort

합병 정렬에서는 최적, 평균, 최악의 케이스가 O(NlogN)으로 모두 같다. 합병 정렬에서는 예외 케이스가 없다. 모두 분할한 뒤 합치기 때문이다.

그렇다면 왜 O(NlogN)일까?

배열에서 n의 길이가 늘어나면 logn의 비율로 분할 횟수가 늘어난다. 그리고 각 분할마다 합병시 O(n)번 비교한다. 그러므로, 각 분할과 합병에 따라 n*logn을 따르게 된다.

📖 퀵 정렬(Quick Sort)

퀵 정렬은 합병 정렬처럼 0개 혹은 1개 요소가 남을때까지 분할하고 정렬하는 방식을 택한다. 퀵 정렬에는 피봇(pivot)이라는 개념이 존재하는데, 이는 피봇에 해당하는 숫자보다 작은 숫자를 왼쪽으로 옮기는 기준점 역할을 한다. 그리고 이를 반복한다.

[5, 2, 1, 8, 4, 7, 6, 3] //피봇을 5라고 해보자 이때 5보자 작은 숫자를 피봇의 왼쪽으로 옮긴다.

3, 2, 1, 4 |5| 7, 6, 8 //왼쪽과 오른쪽에서 같은것을 반복한다 3을 피봇으로 삼아보자

2, 1 |3| 4 |5| 7, 6, 8 //2를 피봇으로 삼아보자

1 |2| |3| 4 |5| 7, 6, 8 //이번엔 오른쪽의 7을 피봇으로 삼아보자

2, 1 |3| 4 |5| 6 |7| 8 //정렬이 되게 된다

✏️ Pivot Solution

배열이 주어지면 피봇 포인트로 지정해 배열 속 요소를 재배치하는 함수를 작성해보자.
피봇보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동한다. 그렇지만 피봇을 기준으로 양쪽의 요소들이 정렬되어 있는지는 중요하지 않다. 그리고 이 함수는 피봇을 반환해야한다. 새로운 배열을 만드는 것이 아니다.

피봇을 선택하는 방법은 중요한데, 이상적으로는 데이터 집합의 중간값이 되도록 선택해야한다. 그렇지만 여기서는 단순하게 첫번째 요소를 선택할 것이다.

// Version with ES2015 Syntax
function pivot(arr, start = 0, end = arr.length - 1) {
  //swap 함수
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  //피봇은 항상 첫번째 인덱스 값이라고 가정
  let pivot = arr[start];
  //swapIdx 초기화
  let swapIdx = start;

  
  for (let i = start + 1; i <= end; i++) {
    //만약 피봇의 값이 현재 인덱스의 값보다 크면
    if (pivot > arr[i]) {
      //swapIdx를 증가시키고
      swapIdx++;
      //현재 인덱스와 swapIdx의 값을 바꾼다
      swap(arr, swapIdx, i);
    }
  }

  //그러고나서 피봇(start의 값)과 피봇보다 작은 값이 몇개인지 카운트한 swapIdx의 값을 바꿔준뒤 swapIdx를 리턴해줌으로 피봇 재설정하기
  swap(arr, start, swapIdx);
  return swapIdx;
}

pivot([4,8,2,1,5,7,6,3])

✏️ Quick Sort Solution

//피봇함수
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;
}

//퀵정렬
function quickSort(arr, left = 0, right = arr.length -1){
  //왼쪽이 오른쪽보다 작을때 코드를 계속 실행
    if(left < right){
      	//피봇 인덱스를 반환한다.
        let pivotIndex = pivot(arr, left, right) //3
        //피봇 기준 왼쪽 정렬
        quickSort(arr,left,pivotIndex-1);
        //피봇 기준 오른쪽 정렬
        quickSort(arr,pivotIndex+1,right);
      }
     return arr;
} 
           
quickSort([100,-3,2,4,6,9,1,2,5,3,23])


// [4,6,9,1,2,5,3]
// [3,2,1,4,6,9,5]
//        4
//  3,2,1    6,9,5
//      3      6
//  2,1      5  9
//    2
//  1

퀵정렬은 재귀적으로 함수를 수행한다.

✏️ Big O of Quick Sort

최상의 경우와 평균은 모두 O(nlogn)을 따른다. 이는 요소의 갯수에 따라 O(logn)의 분해를 수행하고, 각 단계마다 O(n)의 비교를 수행하므로 n*logn이 된다.

최악의 경우에는 O(n^2)이 되는데, 이는 값이 모두 정렬되어있는 경우다. 그래서 가장 작은 요소만 피봇으로 선택하거나 가장 큰 요소만 선택하는 경우엔 문제가 발생한다.
그러므로 정렬된 배열에서는, 피봇을 무작위 항목으로 고르면 된다.

📖 기수 정렬(Radix Sort)

기수 정렬은 여태 배운 정렬들과 다르다. 이 수가 큰지 작은지를 비교하지 않는다. 그리고 기수 정렬은 숫자 크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용한다. 이는 네자리 수가 있다면 두자리수보다 크다는 사실을 이용한 다는 말이다.

예시를 살펴보자.
[1556, 4, 3556, 593, 408, 4386, 902, 7, 8157, 86, 9637, 29]
가 있다고 하자.
이때 일의 자리 수를 기준으로 0~9까지의 버킷에 담는다.

그렇게 한다음, 이를 다시 정렬해준다.
[902, 593, 4, 1556, 3556, 4386, 86, 7, 8157, 9637, 408, 29]
이번에는 십의 자리 수를 기준으로 0~9까지의 버킷에 담아준다.

이 배열을 다시 담아준다.
[902, 4, 7, 408, 29, 9637, 1556, 3556, 8157, 4386, 86, 593]

이번에는 백의자리 수를 기준으로 담아준다.

[4, 7, 29, 86, 8157, 4386, 408, 1556, 3556, 593, 9637, 902]

마지막으로 위 버킷처럼 담을 수 있다.

✏️ getDigit, digitCount, mostDigits Solution

이는 각 자리에 어떤 수가 있는지(예를 들어 23의 십의 자리엔 2)를 알아내는 함수다.

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

Math.abs() : 절대값 계산
Math.pow() : i 제곱수
Math.floor() : 버림

이는 자리수가 몇자리인지를 알아내는 함수다.

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

Math.log10() : 밑이 10인 로그를 취함

그리고 마지막은 숫자들 중 가장 큰 자리수를 구해주는 함수다.

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

mostDigits([23,567,89,12234324,90])

✏️ Radix Sort Solution

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

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

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

//기수정렬
function radixSort(nums){
  	//최대 자리수를 구해준다.(최대 자릿수 만큼의 반복을 위함)
    let maxDigitCount = mostDigits(nums);
    for(let k = 0; k < maxDigitCount; k++){
      	//0~9까지의 버킷을 생성
        let digitBuckets = Array.from({length: 10}, () => []);
      	//각 숫자들의 자리수를 토대로 버켓에 넣어줌
        for(let i = 0; i < nums.length; i++){
            let digit = getDigit(nums[i],k);
            digitBuckets[digit].push(nums[i]);
        }
      	//새로운 배열로 반환
        nums = [].concat(...digitBuckets);
    }
    return nums;
}

radixSort([23,345,5467,12,2345,9852])

✏️ Big O of Radix Sort

기수 정렬의 일반적으로 인정되는 최상, 평균, 최악의 시간 복잡도는 O(nk)다.
n은 배열의 길이로 정렬하려는 수의 갯수, k는 자릿수를 의미한다.
만약 정렬하려는 수들의 목록에서 모든 수의 차이가 뚜렷하다면, k는 logn을 따른다.
이론적으로 기수 정렬은 모든 비교 정렬보다 빠를 수 있지만, 메모리적인 부분에서는 수를 저장하는 방식으로 인해 빠르지 않을 수 있으며 비교 정렬과 비슷할 수 있다.