알고리즘 정리9 : 기수정렬

Kimhojin_Zeno·2023년 3월 15일
0

알고리즘 정리

목록 보기
9/11

정렬 알고리즘4 - 기수정렬

Radix Sort (기수정렬)

앞에까지 정렬은 비교 정렬 알고리즘.

기수 정렬은 비교를 수행하지 않는다.

숫자로 작동되며 이진수를 사용한다.

작동방식

https://visualgo.net/en/sorting

숫자만 가능하며 숫자를 옆에 것과 1:1 로 비교하지 않고

1의 자리만 보고 1-9까지 버켓에 담고, 그 순서대로 다시 배열을 만들고

10의 자리만 보고 동일한 작업을 수행한다. 반복.

가장 큰 수의 자릿수까지 반복하면 결국 모든 정수는 순서대로 정렬된다.

기수정렬 구현

헬퍼함수들

먼저 자릿수를 가져오는 헬퍼 함수를 만든다.

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]));  // 위에 작성한 digitCount 함수를 활용한다.
	}
	return maxDigits;
}

앞에 3개의 헬퍼 함수를 가지고 기수 정렬을 구현한다.

기수정렬 수도코드

  • 수의 배열을 받아 가장 큰 수의 자릿수를 알아낸다
  • 0으로 시작해 가장 큰 자릿수를 max로 하는 루프를 돌린다.
  • 각 루프에서 0-9까지의 빈 버켓을 만들고 해당 루프의 자릿수로 버켓에 넣는다.
  • 기존 배열을 버켓의 값으로 교체.

코드

function radixSort(nums){
    let maxDigitCount = mostDigits(nums);   // 배열에서 가장 큰수의 자릿수.
    for(let k = 0; k < maxDigitCount; k++){    // 그 자릿수까지 루프 돌림
        let digitBuckets = Array.from({length: 10}, () => []);   // 빈배열 10개로 된 배열 생성. 버켓.
        for(let i = 0; i < nums.length; i++){  // 배열의 처음부터 끝까지 루프
            let digit = getDigit(nums[i],k);     // k자릿수의 값을 나타냄.
            digitBuckets[digit].push(nums[i]);   // 해당 자릿수의 숫자 버켓에 담긴다.
        }
        nums = [].concat(...digitBuckets);  // 스프레드 연산자를 쓰면 배열 속 배열까지 하나의 배열로 합쳐짐.
    }
    return nums;
}

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

기수정렬의 Big-O

최선의 경우 → O(nk)

최악의 경우 → O(nk)

평균의 경우 → O(nk)

공간복잡도 → O(n + k)

n은 정렬한 항목 수나 정수의 수,

k는 이러한 수의 길이. 만약 아주아주 긴 수가 있다면 시간에 영향을 크게 준다.

기수정렬의 빅오에 대해 약간의 논란이 있다.

이론적으로 기수 정렬은 모든 비교 정렬보다 빠를 수 있다.

그러나 메모리에 수를 저장하는 방식에 대한 제한으로 인해 실제로는 느릴 수 있다.

profile
Developer

0개의 댓글