Radix Sort mit dynamischem Array

Einführung

In diesem Lab werden wir einen Radix-Sort-Algorithmus in C++ implementieren, um ein Array mit Hilfe eines dynamischen Arrays zu sortieren. Radix Sort ist ein Sortieralgorithmus, der die Sortierung durch die Verarbeitung einzelner Ziffern in verschiedenen Positionen vornimmt.

Skills Graph

Bibliotheken einbinden und Funktion einrichten

Beginnen Sie, indem Sie in das Verzeichnis ~/project eine C++-Datei namens main.cpp erstellen. Fügen Sie die Bibliotheken iostream und vector hinzu und legen Sie eine Funktion radix_sort an, die einen std::vector von ganzen Zahlen annimmt.

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

void radix_sort(vector<int>& nums) {

}

Definiere die getMax-Funktion

Definieren Sie eine Funktion get_max, die einen Integer-Vektor als Eingabe nimmt und den maximalen Wert zurückgibt.

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

Definiere die CountingSort-Funktion

Definieren Sie eine Funktion counting_sort, die einen Integer-Vektor, einen ganzzahligen Wert für den aktuellen Stellenwert und einen Integer-Vektor für die Ausgabe annimmt. Die Funktion wird das Vektor basierend auf dem aktuellen Stellenwert mit dem Counting-Sort-Algorithmus sortieren.

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

Definiere die RadixSort-Funktion

Definieren Sie eine Funktion radix_sort, die einen Integer-Vektor als Eingabe annimmt. Diese Funktion wird den maximalen Wert aus dem Eingabevektor ermitteln und die counting_sort-Funktion verwenden, um den Vektor basierend auf jedem Stellenwert zu sortieren.

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

Testen

Testen Sie die radix_sort-Funktion, indem Sie eine main-Funktion erstellen, die einen Testvektor erstellt und ausgibt.

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

Kompilieren und Ausführen

Kompilieren und führen Sie das Programm im Terminal mit dem folgenden Befehl aus:

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

Sie sollten die folgende Ausgabe sehen:

1 23 45 121 432 564 788

Zusammenfassung

In diesem Lab haben wir gelernt, wie man einen Radix-Sort-Algorithmus in C++ mit dynamischen Arrays durchführt. Der Radix-Sort-Algorithmus funktioniert, indem er einzelne Ziffern in verschiedenen Positionen verarbeitet, und ist ein häufig verwendeter Sortieralgorithmus für Integer und Strings.