Implementation (Part 2)

Lesson 6 of 9 in Coddy's Counting Sort - DSA Series course.

Now we count every value and rebuild the array in order.

Challenge

Easy

Now put it all together into the full algorithm.

Write a function named countingSort that takes an array of non-negative integers and returns it sorted in ascending order.

Find the largest value, build a count array of size max + 1, tally every element, then rebuild the result by writing each value v into the output count[v] times, from smallest to largest.

Reuse the counting idea from the previous lesson.

Try it yourself

#include <stdlib.h>

int* countingSort(int* arr, int arr_size, 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 Counting Sort - DSA Series

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) Project lesson

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2