Intermediate Sorting Algorithms_RADIX SORT

COMPARISON SORTS

Average Time Complexity

• Bubble Sort - O(n^2)
• Insertion Sort - O(n^2)
• Selection Sort - O(n^2)
• Quick Sort - O(n log (n))
• Merge Sort - O(n log (n))

---

RADIX SORT | 기수 정렬

Radix sort is a special sorting algorithm that works on lists of numbers

It never makes comparisons between elements!

It exploits the fact that information about the size of a number is encoded in the number of digits.  

More digits means a bigger number!

두 요소를 가지고 비교하지 않습니다.
무엇이 더 작은지, 무엇이 더 큰지 묻지 않습니다.
그 대신, 숫자 크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용합니다.

RADIX SORT HELPERS

In order to implement radix sort, it's helpful to build a few helper functions first:

mostDigits(nums) - Given an array of numbers, returns the number of digits in the largest numbers in the list 

RADIX SORT PSEUDOCODE

• Define a function that accepts list of numbers
• Figure out how many digits the largest number has
• Loop from k = 0 up to this largest number of digits
• For each iteration of the loop:

• Create buckets for each digit (0 to 9)
• place each number in the corresponding bucket based on its kth digit

• Replace our existing array with values in our buckets, starting with 0 and going up to 9
• return list at the end!

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++){
        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])

console.log([].concat([[1],[2],[3]])) //[ [ 1 ], [ 2 ], [ 3 ] ]
console.log([].concat(...[[1],[2],[3]])) //[ 1, 2, 3 ]

RADIX SORT BIG O

Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
O(nk)	O(nk)	O(nk)	O(n + k)

• n - length of array
• k - number of digits(average)

Recap

• Merge sort and quick sort are standard efficient sorting algorithms
• Quick sort can be slow in the worst case, but is comparable to merge sort on average
• Merge sort takes up more memory because it creates a new array (in-place merge sorts exist, but they are really complex!)
• Radix sort is a fast sorting algorithm for numbers
• Radix sort exploits place value to sort numbers in linear time (for a fixed number of digits)