Non - Comparison Sorting Algorithms

Question 1

What are the 2 non-comparison sorting algorithms we have studied?

Answer 1

• Counting sort

- Radix sort

Question 2

What is the Big-Oh complexity of counting sort?

Answer 2

O(n)

Question 3

Requirement of counting sort?

Answer 3

integers in the range of 0 to k. Where k is the size of the structure holding the counts.

Question 4

Is counting sort stable?

Answer 4

Yes

Question 5

Is counting sort in place?

Answer 5

No

Question 6

What is the memory requirement of counting sort?

Answer 6

Linear O(n)

Question 7

Is counting sort used within radix sort?

Answer 7

Yes

Question 8

How does counting sort work?

Answer 8

• Counting sort is a non-comparison sorting algorithm, which works on the basis of counting occurrences of each element and placing the count in a structure (call it C).
• Once the count of the occurrences has been determined, we aim to calculate the cumulative sum within that same structure.
• With this now we can place each value of A (call an individual value As) iterating from the end , in a new array at the index C[As] -1. (occurrence count is updated respectively, so we -1 to C[As] as one occurance has been covered).
• This is repeated until all elements from the original array are accounted for (C is full of 0s and end of original array has been reached).

Question 9

In practice when is counting sort used?

Answer 9

When k = O(n)

Question 10

What is the requirement for radix sort?

Answer 10

That all numbers to be sorted have the same number of digits

Question 11

Is radix sort counting sort based?

Answer 11

Yes

Question 12

How does radix sort work?

Answer 12

• Radix sort is another non-comparison sorting algorithm, which sorts individual digits of the number taking into account only smaller digits (e.g. for sorting tens we take into account the previously sorted units), so that any collisions can be solved by looking at the lower digits sorted beforehand. The sorting happens via counting sort.
• This is repeated until all digits are accounted for, resulting in a final sorted sequence.

Question 13

What is the Big-Oh complexity of radix sort?

Answer 13

O(n), as the amount of digits is linear.

Question 14

Can counting sort be replaced with another sort within radix ?

Answer 14

Yes, any stable sort algorithm.

Question 15

What do we exploit with non-comparison algorithms?

Answer 15

The input properties.