Where counting sort places a value

EasyProgramming & DSA~3m

Counting sort is run on the array $[\,3,\ 1,\ 3,\ 2,\ 1,\ 3,\ 0\,]$ whose values lie in $\{0,1,2,3\}$ . After tallying how many times each value occurs, the algorithm takes a prefix sum of those tallies to decide where each value's block begins in the sorted output, then writes elements into a $0$ -indexed output array. At which $0$ -indexed position does the first (leftmost) $2$ get placed?

Show hints (2)+

First tally each value's count, then prefix-sum: a value's block starts at the cumulative count of all smaller values.
The block for $2$ starts at $\text{count}[0]+\text{count}[1]$ .

Answer

Reveal answer →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Hedge Fund Quant, Systematic & Data-Driven Trading

Where counting sort places a value

Answer

Related questions