Implementacja (część 2)

Lekcja 6 z 9 w kursie Sortowanie przez zliczanie – seria DSA w Coddy.

Teraz zliczamy każdą wartość i odtwarzamy tablicę w odpowiedniej kolejności.

Wyzwanie

Łatwy

Teraz połącz to wszystko w pełny algorytm.

Napisz funkcję o nazwie countingSort, która przyjmuje tablicę nieujemnych liczb całkowitych i zwraca ją posortowaną w kolejności rosnącej.

Znajdź największą wartość, utwórz tablicę zliczającą o rozmiarze max + 1, zlicz każde wystąpienie elementu, a następnie odtwórz wynik, zapisując każdą wartość v do wyniku count[v] razy, od najmniejszej do największej.

Wykorzystaj pomysł zliczania z poprzedniej lekcji.

Spróbuj swoich sił

#include <stdlib.h>

int* countingSort(int* arr, int arr_size, int* returnSize) {
    // Napisz kod tutaj
    *returnSize = arr_size;
    return arr;
}