알고리즘 08 정렬 | sorting in linear time, Counting Sort, Radix Sort | JS

1. 계수 정렬 | Counting Sort

• n개의 정수를 정렬하라.단, 모든 정수는 0에서 k사이의 정수이다.
  ex) n명의 학생들의 시험점수를 정렬하라.단 모든 점수는 100이하의 양의 정수이다.
• 사전 지식을 이용하기 때문에 Non - comparison Sort에 해당함
  
• 대부분의 경우 정렬할 key 값들은 레코드의 일부분이기 때문에 아래와 같은 작업이 추가로 필요함
  

1. (a) k+1 길이의 countArr를 만들어서 각 요소의 갯수를 카운트
2. (b) countArr를 누적값으로 변환
3. arr를 뒤에서부터 돌면서 해당 값을 index로 가지는 countArr를 찾음
   ex) arr[8] (3) => countArr[3] (7)
4. resultArr에 위에서 찾은 값을 대입함
   ex) countArr[3] (7) => resultArr[7] (3)
5. countArr에서 처리한 값을 -1
   ex) countArr[3]--
6. 3~5 반복

• 시간복잡도: O(n+k) 또는 O(n) if k=O(n)
• k가 클 경우 비실용적
• Counting 정렬은 stable 하다.

Stable 정렬 알고리즘
입력한 동일한 값이 있을 때 입력에서 먼저 나오는 값이 출력에서도 먼저 나온다

function coutingSort(arr, k) {
  const countArr = new Array(k + 1).fill(0)
  arr.forEach(item => {
    countArr[item]++
  })
  console.log(countArr); // [2, 0, 2, 3, 0, 1]


  for (let i = 1; i < countArr.length; i++) {
    countArr[i] = countArr[i] + countArr[i - 1]
  }
  console.log(countArr); // [2, 2, 4, 7, 7, 8]

  const result = []
  for (let j = arr.length - 1; j >= 0; j--) {
    const index = arr[j] // 0
    // resultArr가 0부터 시작하기 때문에 -1 추가 필요
    result[countArr[index] - 1] = index 
    countArr[index]--
  }
  return result
}

const arr = [2, 5, 3, 0, 2, 3, 0, 3]
const k = 5
console.log(coutingSort(arr, k)) // [0, 0, 2, 2, 3, 3, 3, 5]

2. 기수 정렬 | Radix Sort

• n개의 d자리 정수들(반드시 숫자일 필요는 없음)
• 가장 낮은 자리수부터 정렬
• 자릿수별로 정렬을 하면서 넘어갈 때 그 정렬은 stable해야함.
• 시간복잡도: O(d(n+k))

초기 구현 코드

function radixSort(arr, k, d) {
  let radix = d - 1
  const result = []
  while (radix >= 0) {

    const countArr = new Array(k + 1).fill(0)
    arr.forEach(item => {
      const str = item + ''
      countArr[+str[radix]]++
    })
    console.log('1', countArr);

    for (let i = 1; i < countArr.length; i++) {
      countArr[i] = countArr[i] + countArr[i - 1]
    }
    console.log('2', countArr);

    for (let j = arr.length - 1; j >= 0; j--) {
      const value = arr[j] + ""
      const radixValue = +value[radix]
      const index = countArr[radixValue]
      result[index - 1] = +value
      countArr[radixValue]--
    }
    radix--

    console.log('3', result);
    console.log("==========================================");
  }

  return result
}

const arr = [329, 457, 657, 839, 436, 720, 355]
const k = 9
const d = 3
console.log(radixSort(arr, k, d));

개선된 코드

function radixSort(arr, k, d) {
  let radix = 1
  const result = []

  while (radix <= d) {
    const countArr = new Array(k + 1).fill(0)
    arr.forEach(item => {
      const radixValue = getRadixValue(item, radix)
      countArr[radixValue]++
    })
    console.log('1', countArr);

    for (let i = 1; i < countArr.length; i++) {
      countArr[i] = countArr[i] + countArr[i - 1]
    }
    console.log('2', countArr);

    for (let j = arr.length - 1; j >= 0; j--) {
      const value = arr[j]
      const radixValue = getRadixValue(value, radix)
      const index = countArr[radixValue]
      result[index - 1] = +value
      countArr[radixValue]--
    }
    radix++

    console.log('3', result);
    console.log("==========================================");
  }

  return result
}

function getRadixValue(item, radix) {
  return Math.floor((item % Math.pow(10, radix)) / Math.pow(10, radix - 1))
}

const arr = [329, 457, 657, 839, 436, 720, 355]
const k = 9
const d = 3
console.log(radixSort(arr, k, d));

Result

// 1의 자리 수 정렬
1(10)[1, 0, 0, 0, 0, 1, 1, 2, 0, 2]
2(10)[1, 1, 1, 1, 1, 2, 3, 5, 5, 7]
3(7)[720, 355, 436, 457, 657, 329, 839]
==========================================
1(10)[0, 0, 2, 2, 0, 3, 0, 0, 0, 0]
2(10)[0, 0, 2, 4, 4, 7, 7, 7, 7, 7]
3(7)[329, 720, 839, 436, 457, 657, 355]
==========================================
1(10)[0, 0, 0, 2, 2, 0, 1, 1, 1, 0]
2(10)[0, 0, 0, 2, 4, 4, 5, 6, 7, 7]
3(7)[329, 355, 457, 436, 657, 720, 839]
==========================================
(7)[329, 355, 457, 436, 657, 720, 839]

*시간복잡도 비교

📚 참고

YOUTUBE | 2015 봄학기 알고리즘 | 권오흠

Photo by Michael Dziedzic on Unsplash
텍스트