Implementation (Part 1)

Lesson 5 of 9 in Coddy's Radix Sort - DSA Series course.

We will build Radix Sort from its core operation up.

Challenge

Medium

Each pass of Radix Sort is a stable counting sort on a single digit. Let's build that first.

Write a function named countingSortByDigit that takes an array of non-negative integers arr and a place value exp (1 for ones, 10 for tens, 100 for hundreds, ...), and returns a new array sorted by the digit (x / exp) % 10. The sort must be stable: elements with the same digit keep their original order.

For example, countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) returns [170, 90, 2, 802, 24, 45, 75, 66] (sorted by the ones digit).

Try it yourself

#include <stdlib.h>

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

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

All lessons in Radix Sort - DSA Series

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2