Sorting Algorithms

Concept Quizzes

Insertion/Bubble Sorting
Merge/Quicksort
Heap Sort
Counting Sort
Binary Search

Challenge Quizzes

Sorting Algorithms: Level 2 challenges
Sorting Algorithms: Level 3 challenges

Counting Sort

Let $n$ be the size of an input array made up of positive integers and suppose that your algorithm is given $V_{max}$ , the maximum value of all elements within the input array. Which of the following describes the correct space complexity of counting Sort in this case?

\Theta(n^2)

\Theta(V_{max}*n )

\Theta(V_{max} + n)

\Theta(n)

Show explanation

View wiki

by Brilliant Staff

Suppose we have an array with $n$ elements and $k$ is the size of the largest key. When would it be a bad idea to use counting sort to sort this array?

Details and assumptions

$k = O(f(n))$ means $k$ is bounded by the function $f(n)$ .

k = O(n^2)

k = O(n)

k = O(1)

k = O(\lg(n)^3)

Show explanation

View wiki

by Brilliant Staff

Assume we want to sort an array of ints. In which scenario is the use of counting sort the most sensible?

An array of ints that is completely random. An array of ints that is sorted except for a certain number of randomly located anomalies. ints that are sorted except for certain randomly pairs of adjacent elements that have been swapped. An array of randomly arranged ints that are each within a specific range.

Show explanation

View wiki

by Brilliant Staff

Problem Loading...

Note Loading...

Set Loading...