HotFoxy
불여우의 전직 이야기
게임 서버 개발자가 되어 보죠!
전체 방문자
오늘
어제
  • 분류 전체보기 (135)
    • 연구한 이야기 (26)
      • 깊게 공부해보기 (7)
      • 문제 해결 이야기 (12)
      • 맡은 업무 이야기 (6)
    • 전직 이야기 (0)
      • 1년이라는 시간 (5)
      • 프로카데미 이야기 (5)
    • 공부한 이야기 (87)
      • 알고리즘 (7)
      • 리눅스 (11)
      • 클라우드 (24)
      • 윈도우 OS (17)
      • 윈도우 소켓 프로그래밍 (11)
      • 네트워크 (16)
      • Docker & K8S (0)
      • 기타 (1)
    • 자격증 이야기 (12)
  • MSB : Mad Square's Brawl
  • GITHUB

인기 글

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
HotFoxy

불여우의 전직 이야기

공부한 이야기/알고리즘

정렬 - 기수정렬

2022. 8. 7. 17:19

기수 정렬

기수 정렬은 값의 자릿수를 이용해서 정렬하는 특이한 정렬인데,

이는 비교를 하지 않고 정렬한다는 또 다른 특징을 가지고 있다.

우선 n진수인지에 따라서 n개의 저장 공간 (일반적으로 스택 등) 을 마련한다.

배열과는 다르게, 이 저장 공간에는 여러 데이터가 들어갔다가 순차적으로 나올 수 있어야 한다.

그리고 나서, n진수의 끝의 자리 숫자 (10진수라면 1의 자리 숫자) 를 기준으로, 해당 값에 맞는 버킷을 값을 push 한다.

예를 들어, 142 라는 값은 2 번째 버킷에 들어가는 형식이다.

이후, 이 모든 버킷들을 첫번재 버킷부터 순차적으로 pop 하면서 배열에 다시 담는다.

그 후, 배열의 값 중 최대 자리 수만큼 이 행위를 반복하면서, 정렬을 만들어내는 과정이다.

generateRandomArray, printArray, swap

static int arrayLength = 20;
int *myArray = generateRandomArray(arrayLength); // 랜덤 값을 가진 배열 생성

printArray(myArray, arrayLength); // 정렬 전 배열 출력

queue<int> myQueue[10]; // 기수정렬을 위한 n진수만큼의 큐 버킷 생성

int radix = 1; // 최대 자리수
int maxValue = myArray[0]; // 배열의 최대 값 찾기
for (int i = 0; i < arrayLength; i ++) {
    if (maxValue < myArray[i]) maxValue = myArray[i];
}
while (true) { // 최대 자리 수 찾기
    if (radix >= maxValue) break;
    radix *= 10;
}

for (int currentRadix = 1; currentRadix < radix; currentRadix *= 10) { // 일의자리부터 최대자리수까지 루프
    for (int i = 0; i < arrayLength; i ++) { // 배열을 순회한다
        myQueue[myArray[i] / currentRadix % 10].push(myArray[i]); // 해당 자리수의 끝자리에 맞는 버킷으로 push
    }

    int arrayIndex = 0; // 배열 인덱스
    for (int j = 0; j < 10; j ++) { // 버킷을 순회한다
        while (myQueue[j].empty() == false) { // 버킷에 값이 존재하면
            myArray[arrayIndex] = myQueue[j].front(); // 배열의 인덱스에 버킷의 맨 첫 값 추가 
            myQueue[j].pop();
            arrayIndex++; // 배열 인덱스 증가
        }
    }
}

printArray(myArray, arrayLength); // 정렬 후 배열 출력

작은 것부터, 점점 커지게, 오름차순으로 정렬한 예제이다.

이러한 기수 정렬은 O(N) 의 복잡도를 가지게 된다. O(N) 이 여러 단계에 걸쳐 존재하므로, 합연산에 의해 계산된다.

하지만 이러한 기수 정렬은, 다른 정렬에 비해 메모리를 추가로 요구하게 되므로 장단점이 있다 할 수 있다.

저작자표시 (새창열림)

'공부한 이야기 > 알고리즘' 카테고리의 다른 글

정렬 - 퀵정렬  (0) 2022.08.07
정렬 - 힙정렬  (0) 2022.08.07
정렬 - 삽입정렬  (0) 2022.08.07
정렬 - 선택정렬  (0) 2022.08.07
정렬 - 버블정렬  (0) 2022.08.07
    '공부한 이야기/알고리즘' 카테고리의 다른 글
    • 정렬 - 퀵정렬
    • 정렬 - 힙정렬
    • 정렬 - 삽입정렬
    • 정렬 - 선택정렬
    HotFoxy
    HotFoxy
    1년 동안의 고군분투 전직 이야기! ..가 완료되어, 게임개발자로 살아남는 이야기!

    티스토리툴바