Implementazione (Parte 1)

Lezione 5 di 9 del corso Ordinamento Radix - Serie DSA di Coddy.

Costruiremo Radix Sort partendo dalla sua operazione fondamentale.

Sfida

Medio

Ogni passaggio di Radix Sort è un ordinamento per conteggio stabile su una singola cifra. Iniziamo a implementarlo.

Scrivi una funzione chiamata countingSortByDigit che accetta un array di interi non negativi arr e un valore posizionale exp (1 per le unità, 10 per le decine, 100 per le centinaia, ...) e restituisce un nuovo array ordinato in base alla cifra (x / exp) % 10. L'ordinamento deve essere stabile: gli elementi con la stessa cifra mantengono il loro ordine originale.

Ad esempio, countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) restituisce [170, 90, 2, 802, 24, 45, 75, 66] (ordinato in base alla cifra delle unità).

Provalo tu

#include <stdlib.h>

int* countingSortByDigit(int* arr, int arr_size, int exp, int* returnSize) {
    // Write code here
    *returnSize = arr_size;
    return arr;
}