Implementation (Part 1)
Leçon 5 sur 9 du cours Radix Sort - Série DSA de Coddy.
Nous allons construire le Radix Sort à partir de son opération de base.
Défi
MoyenChaque passage du Radix Sort est un tri par comptage stable sur un seul chiffre. Commençons par construire cela.
Écrivez une fonction nommée countingSortByDigit qui prend un tableau d'entiers non négatifs arr et une valeur de position exp (1 pour les unités, 10 pour les dizaines, 100 pour les centaines, ...), et renvoie un nouveau tableau trié par le chiffre (x / exp) % 10. Le tri doit être stable : les éléments ayant le même chiffre conservent leur ordre d'origine.
Par exemple, countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) renvoie [170, 90, 2, 802, 24, 45, 75, 66] (trié par le chiffre des unités).
Essayez vous-même
#include <stdlib.h>
int* countingSortByDigit(int* arr, int arr_size, int exp, int* returnSize) {
// Écrire le code ici
*returnSize = arr_size;
return arr;
}
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Radix Sort - Série DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity