Поразрядная сортировка с использованием динамического массива

Введение

В этом лабе мы реализуем алгоритм поразрядной сортировки на C++ для сортировки массива с использованием динамического массива. Порожрядная сортировка - это алгоритм сортировки, который сортирует элементы, обрабатывая отдельные цифры в различных позициях.

Подключить библиотеки и настроить функцию

Начните с создания файла на C++ в директории ~/project с именем main.cpp. Подключите библиотеки iostream и vector и настройте функцию radix_sort, которая принимает std::vector целых чисел.

#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, которая принимает вектор целых чисел, целое значение для текущего разряда и вектор целых чисел для вывода. Функция отсортирует вектор на основе текущего разряда с использованием алгоритма сортировки подсчетом.

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);
    }
}

Тестирование

Протестируйте функцию radix_sort, создав функцию main, которая создает и выводит на печать тестовый вектор.

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

Резюме

В этом практическом занятии мы узнали, как реализовать алгоритм поразрядной сортировки (radix sort) на C++ с использованием динамических массивов. Алгоритм поразрядной сортировки работает путем обработки отдельных цифр в различных позициях и является широко используемым алгоритмом сортировки для целых чисел и строк.