Linear Velocity: Counting Sort

HardAcc. 88.5%
+45 XP 20

Distribution Sorting

Counting Sort is a non-comparison based sorting algorithm that uses a frequency array (count array) to determine the position of each element.

The Assignment

Your function receives data (assume non-negative integers).

  1. Find max value in data.
  2. Create count array of size max + 1.
  3. Store frequency of each element.
  4. Accumulate counts (count[i] += count[i-1]).
  5. Build output array and print.

01EXAMPLE 1

Input[1, 4, 1, 2, 7, 5, 2]
Output1 1 2 2 4 5 7

Explanation: Sorted in linear time using frequency mapping.

Constraints

  • O(n + k) time complexity.
  • Only works for non-negative discrete values.
AlgorithmsSorting
JavaScript
Loading...
1 Hidden

Input Arguments

data[1,4,1,2,7,5,2]

Expected Output

1 1 2 2 4 5 7

Click RUN to test your solution