counting sort

Flashcards covering key concepts related to Counting Sort and its implementation.

What is Counting Sort?

Counting Sort is a non-comparison based sorting algorithm that sorts lists of non-negative integers.

What is the time complexity of Counting Sort when k is constant?

O(n), where n is the length of the input list.

What does the term 'stable' mean in the context of sorting algorithms?

A stable sorting algorithm maintains the relative order of records with equal keys.

How do you create a cumulative version of the POS array in Counting Sort?

Add previous values iteratively to the non-cumulative POS array.

In Counting Sort, how do you handle the elements while copying back to the sorted array?

Copy elements from the original array to the new array by iterating backwards and using the POS array for indices.

What auxiliary space does Counting Sort use?

O(n + k), where n is the number of elements in the input list and k is the range of the input values.

What is one limitation of Counting Sort mentioned in the notes?

Counting Sort can be inefficient for large k, even if k is constant, due to memory consumption.

Explain how Counting Sort can be adapted for sorting floating point numbers.

If the numbers are all non-negative but have decimal points, multiply by a power of ten, sort with Counting Sort, and then divide by that power of ten.

What must you ensure when using Counting Sort in the context of stability?

Ensure that you copy elements from the original array to the sorted array in a way that preserves the order of equal elements.

What is the significance of the variable 'k' in Counting Sort?

k is the maximum value in the input array and determines the size of the POS array.