[Algorithm]Sort-Radix Sort

출처 : https://www.codingeek.com/wp-content/uploads/2017/02/radix.png

Radix Sort()

Radix Sort()은 숫자나 숫자를 기준으로 요소를 그룹화하여 정렬하는 비비교 정렬 알고리즘입니다. 기수 또는 기저를 기준으로 요소를 정렬합니다. 컴퓨터 과학에서, 기수(radix)는 숫자 체계가 갖는 고유한 숫자 또는 기호의 개수로, 10진수 체계에서는 0에서 9까지, 16진수 체계에서는 0에서 F까지 포함한다. 이번 블로그 게시물에서는 자바스크립트를 이용한 기수 정렬 알고리즘에 대해 알아보겠습니다.

Radix Sort Algorithm

Radix Sort Algorithm은 요소의 각 자릿수 또는 숫자를 오른쪽에서 왼쪽으로 비교하여 요소를 정렬하고, 최하위 숫자부터 시작하여 비교 중인 현재 숫자를 기준으로 버킷에 그룹화합니다. 요소를 현재 숫자로 정렬한 후 알고리즘이 다음 숫자로 이동하여 프로세스를 반복합니다. 알고리즘은 요소의 모든 자릿수가 정렬될 때까지 이 프로세스를 반복합니다.

Radix Sort Algorithm은 다음과 같은 두 가지 접근법을 사용하여 수행할 수 있다:

Least Significant Digit (LSD) Radix Sort(최하위 숫자 정렬): 이 접근법은 최하위 숫자에서 시작하여 최상위 숫자로 이동하는 각 숫자를 비교하여 요소를 정렬합니다.

Most Significant Digit (MSD) Radix Sort(최상위 숫자 정렬): 이 접근법은 최상위 숫자에서 시작하여 최하위 숫자로 이동하는 각 숫자를 비교하여 요소를 정렬합니다.

LSD Radix Sort Algorithm Implementation(최하위 숫자 정렬)

LSD Radix Sort Algorithm을 구현하기 위해 버킷 정렬 알고리즘을 사용하여 현재 숫자를 기준으로 요소를 정렬할 수 있습니다. 버킷 정렬은 요소를 여러 버킷으로 분산시킨 다음 삽입 정렬과 같은 다른 정렬 알고리즘을 사용하여 각 버킷을 개별적으로 정렬함으로써 작동하는 정렬 알고리즘입니다. 버킷 정렬을 사용하여 현재 숫자를 기준으로 요소를 정렬한 다음 정렬된 버킷을 연결하여 현재 숫자에 대한 정렬된 요소를 가져올 수 있습니다.

코드는 아래와 같습니다.

function radixSortLSD(arr) {
  const radix = 10;
  let maxLength = false;
  let placement = 1;

  while (!maxLength) {
    maxLength = true;
    let buckets = Array.from({length: radix}, () => []);

    for (let i = 0; i < arr.length; i++) {
      const num = arr[i];
      const digit = Math.floor(num / placement) % radix;
      buckets[digit].push(num);
      if (maxLength && buckets[digit].length > 1) {
        maxLength = false;
      }
    }

    let j = 0;
    for (let i = 0; i < radix; i++) {
      const bucket = buckets[i];
      for (let k = 0; k < bucket.length; k++) {
        arr[j++] = bucket[k];
      }
    }

    placement *= radix;
  }

  return arr;
}

위의 코드에서, 우리는 Radix를 십진법을 나타내는 10으로 정의한다. maxLength 변수는 모든 요소가 정렬되었는지 여부를 추적하는 데 사용됩니다. 배치 변수는 비교 중인 현재 숫자를 추적하는 데 사용됩니다. while 루프는 요소의 모든 자릿수가 정렬될 때까지 정렬 프로세스를 반복하는 데 사용됩니다.

while 루프 안에서, 우리는 기수와 같은 길이의 빈 버킷 배열을 정의한다. 그런 다음 입력 배열의 각 요소에 대해 반복하고 요소를 배치 변수로 나눈 다음 Math.floor() 방법을 사용하여 가장 가까운 정수로 내림으로써 현재 숫자를 얻습니다. 그런 다음 현재 숫자에 해당하는 버킷에 요소를 추가합니다.

현재 숫자에 대한 요소를 정렬한 후 정렬된 버킷을 연결하여 현재 숫자에 대한 정렬된 요소를 가져옵니다. 그런 다음 배치 변수에 기수를 곱하여 다음 자리로 이동합니다.

그래서 아래와 같은 결과를 가지고 올 수 있습니다.

const arr = [326, 453, 608, 835, 751, 435, 704, 690];
console.log(radixSortLSD(arr)); // [325, 453, 453, 608, 690, 704, 751, 835]

Radix Sort algorithm을 자바스크립트에서 사용 하는 방법에 대해 설명 드렸습니다. algorithm의 요소에 각 자릿수 또는 숫자를 오른쪽에서 왼쪽으로 비교하고 가장 유의하지 않은 자릿수에서 시작하여 비교 중인 현재 숫자를 기준으로 버킷에 그룹화함으로써 요소를 정렬하는 방법을 보았습니다. 또한 버킷 정렬 알고리즘을 사용하여 LSD Radix 정렬 알고리즘을 구현하여 현재 숫자를 기준으로 요소를 정렬하는 방법을 확인했습니다. 그런 다음 입력 배열을 사용하여 알고리듬을 테스트하고 요소를 오름차순으로 정렬하는 방법을 보았습니다.