Implementation (Part 1)

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

We will build Counting Sort from its counting phase up.

Challenge

Easy

The first phase of Counting Sort is tallying how often each value appears. Let's build that.

Write a function named countOccurrences that takes an array of non-negative integers arr (every value is between 0 and k - 1) and an integer k, and returns an array of length k where position v holds how many times v appears in arr.

For example, countOccurrences([1, 3, 1, 2, 0], 4) returns [1, 2, 1, 1].

Try it yourself

#include <stdlib.h>

int* countOccurrences(int* arr, int arr_size, int k, 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 CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2