Implementation (Part 2)
Урок 6 из 9 курса Сортировка подсчетом — Серия DSA на Coddy.
Теперь мы подсчитываем каждое значение и перестраиваем массив по порядку.
Задание
ЛегкоТеперь объедините всё это в полный алгоритм.
Напишите функцию с именем countingSort, которая принимает массив неотрицательных целых чисел и возвращает его отсортированным по возрастанию.
Найдите наибольшее значение, создайте массив счетчиков размером max + 1, подсчитайте количество каждого элемента, а затем перестройте результат, записывая каждое значение v в выходной массив count[v] раз, от наименьшего к наибольшему.
Повторно используйте идею подсчета из предыдущего урока.
Попробуйте сами
#include <stdlib.h>
int* countingSort(int* arr, int arr_size, int* returnSize) {
// Напишите код здесь
*returnSize = arr_size;
return arr;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Сортировка подсчетом — Серия DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity