Implementation (Part 1)
Урок 5 из 9 курса Поразрядная сортировка — серия DSA на Coddy.
Мы построим поразрядную сортировку (Radix Sort), начиная с её основной операции.
Задание
СреднеКаждый проход поразрядной сортировки (Radix Sort) представляет собой устойчивую сортировку подсчетом по одному разряду. Давайте сначала реализуем ее.
Напишите функцию с именем countingSortByDigit, которая принимает массив неотрицательных целых чисел arr и значение разряда exp (1 для единиц, 10 для десятков, 100 для сотен и т. д.) и возвращает новый массив, отсортированный по цифре (x / exp) % 10. Сортировка должна быть устойчивой: элементы с одинаковой цифрой должны сохранять свой первоначальный порядок.
Например, countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) возвращает [170, 90, 2, 802, 24, 45, 75, 66] (отсортировано по разряду единиц).
Попробуйте сами
#include <stdlib.h>
int* countingSortByDigit(int* arr, int arr_size, int exp, int* returnSize) {
// Напишите код здесь
*returnSize = arr_size;
return arr;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Поразрядная сортировка — серия DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity