Implementation (Part 1)
Lektion 5 von 9 im Kurs Radix Sort - DSA-Serie von Coddy.
Wir werden Radix Sort ausgehend von seiner Kernoperation aufbauen.
Aufgabe
MittelJeder Durchlauf von Radix Sort ist ein stabiler Counting Sort auf einer einzelnen Ziffer. Lassen Sie uns diesen zuerst erstellen.
Schreiben Sie eine Funktion namens countingSortByDigit, die ein Array von nicht-negativen Ganzzahlen arr und einen Stellenwert exp (1 für Einer, 10 für Zehner, 100 für Hunderter, ...) entgegennimmt und ein neues Array zurückgibt, das nach der Ziffer (x / exp) % 10 sortiert ist. Die Sortierung muss stabil sein: Elemente mit derselben Ziffer behalten ihre ursprüngliche Reihenfolge bei.
Zum Beispiel gibt countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) das Ergebnis [170, 90, 2, 802, 24, 45, 75, 66] zurück (sortiert nach der Einerstelle).
Probier es selbst
#include <stdlib.h>
int* countingSortByDigit(int* arr, int arr_size, int exp, int* returnSize) {
// Schreibe den Code hier
*returnSize = arr_size;
return arr;
}
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Radix Sort - DSA-Serie
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity