C++ 에서 동적 배열을 사용한 기수 정렬 구현 방법

소개

이 랩에서는 동적 배열을 사용하여 C++ 로 기수 정렬 (radix sort) 알고리즘을 수행하여 배열을 정렬합니다. 기수 정렬은 각 위치의 개별 숫자를 처리하여 정렬하는 정렬 알고리즘입니다.

라이브러리 포함 및 함수 설정

~/project 디렉토리에 main.cpp라는 C++ 파일을 생성하는 것으로 시작합니다. iostream 및 vector 라이브러리를 포함하고 정수형 std::vector를 입력으로 받는 radix_sort 함수를 설정합니다.

#include <iostream>
#include <vector>
using namespace std;

void radix_sort(vector<int>& nums) {

}

getMax 함수 정의

정수 벡터를 입력으로 받아 최대값을 반환하는 get_max 함수를 정의합니다.

int get_max(vector<int>& nums) {
    int max = nums[0];
    for(int i = 1; i < nums.size(); i++) {
        if(nums[i] > max)
            max = nums[i];
    }
    return max;
}

CountingSort 함수 정의

정수 벡터, 현재 자릿수에 대한 정수 값, 그리고 출력을 위한 정수 벡터를 입력으로 받는 counting_sort 함수를 정의합니다. 이 함수는 계수 정렬 (counting sort) 알고리즘을 사용하여 현재 자릿수를 기준으로 벡터를 정렬합니다.

void counting_sort(vector<int>& nums, int place, vector<int>& output) {
    const int max = 10;
    int count[max];

    for(int i = 0; i < max; i++)
        count[i] = 0;

    for(int i = 0; i < nums.size(); i++)
        count[(nums[i] / place) % 10]++;

    for(int i = 1; i < max; i++)
        count[i] += count[i - 1];

    for(int i = nums.size() - 1; i >= 0; i--) {
        output[count[(nums[i] / place) % 10] - 1] = nums[i];
        count[(nums[i] / place) % 10]--;
    }

    for(int i = 0; i < nums.size(); i++)
        nums[i] = output[i];
}

RadixSort 함수 정의

정수 벡터를 입력으로 받는 radix_sort 함수를 정의합니다. 이 함수는 입력 벡터에서 최대값을 구하고, 각 자릿수를 기준으로 벡터를 정렬하기 위해 counting_sort 함수를 사용합니다.

void radix_sort(vector<int>& nums) {
    int max = get_max(nums);

    for(int place = 1; max / place > 0; place *= 10) {
        vector<int> output(nums.size());
        counting_sort(nums, place, output);
    }
}

테스팅

테스트 벡터를 생성하고 출력하는 main 함수를 생성하여 radix_sort 함수를 테스트합니다.

int main() {
    vector<int> test = {121, 432, 564, 23, 1, 45, 788};
    radix_sort(test);

    for(int num : test)
        cout << num << " ";
    cout << endl;

    return 0;
}

컴파일 및 실행

다음 명령을 사용하여 터미널에서 프로그램을 컴파일하고 실행합니다.

g++ main.cpp -o main && ./main

다음과 같은 출력을 볼 수 있습니다.

1 23 45 121 432 564 788

요약

이 랩에서는 동적 배열을 사용하여 C++ 에서 기수 정렬 (radix sort) 알고리즘을 수행하는 방법을 배웠습니다. 기수 정렬 알고리즘은 각 위치의 개별 자릿수를 처리하여 작동하며, 정수 및 문자열에 일반적으로 사용되는 정렬 알고리즘입니다.