Implementacja (część 1)

Lekcja 5 z 9 w kursie Sortowanie radixowe — seria DSA w Coddy.

Zbudujemy sortowanie Radix Sort, zaczynając od jego podstawowej operacji.

Wyzwanie

Średni

Każde przejście sortowania pozycyjnego to stabilne sortowanie przez zliczanie według pojedynczej cyfry. Zacznijmy od jego implementacji.

Napisz funkcję o nazwie countingSortByDigit, która przyjmuje tablicę nieujemnych liczb całkowitych arr oraz wartość pozycyjną exp (1 dla jedności, 10 dla dziesiątek, 100 dla setek, ...), a następnie zwraca nową tablicę posortowaną według cyfry (x / exp) % 10. Sortowanie musi być stabilne: elementy z tą samą cyfrą zachowują swoją pierwotną kolejność.

Na przykład countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) zwraca [170, 90, 2, 802, 24, 45, 75, 66] (posortowane według cyfry jedności).

Spróbuj swoich sił

#include <stdlib.h>

int* countingSortByDigit(int* arr, int arr_size, int exp, int* returnSize) {
    // Wpisz tutaj kod
    *returnSize = arr_size;
    return arr;
}