Comparison Based vs Non Comparison Based Sorting in DSA Javascript - Key Differences

Recall & Review

beginner

What is comparison based sorting?

Sorting methods that decide the order of elements by comparing them with each other, like checking if one number is bigger or smaller than another.

beginner

Name two common comparison based sorting algorithms.

Bubble Sort and Quick Sort are examples of comparison based sorting algorithms.

beginner

What is non comparison based sorting?

Sorting methods that do not compare elements directly but use other information like counting or grouping to sort, such as counting sort or radix sort.

intermediate

Why can non comparison based sorting be faster than comparison based sorting?

Because they use special tricks like counting or grouping, they can sort in linear time for certain types of data, unlike comparison based sorting which usually takes longer.

intermediate

What is the best time complexity possible for comparison based sorting?

The best possible time complexity for comparison based sorting is O(n log n), meaning it takes at least that much time to sort n items by comparing.

Which of these is a comparison based sorting algorithm?

A Quick Sort

B Counting Sort

C Radix Sort

D Bucket Sort

Quick Sort sorts by comparing elements, so it is comparison based.

Non comparison based sorting algorithms usually work best when:

A Data is already sorted

B Data is very large and random

C Data has a limited range of values

D Data is strings only

Non comparison based sorting like counting sort works best when data values are within a limited range.

What is the lower bound time complexity for comparison based sorting?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

Comparison based sorting cannot be faster than O(n log n) in the general case.

Which sorting method uses counting to sort elements?

A Merge Sort

B Heap Sort

C Quick Sort

D Counting Sort

Counting Sort counts the number of occurrences of each value to sort.

Radix Sort is an example of:

A Comparison based sorting

B Non comparison based sorting

C Divide and conquer sorting

D In-place sorting

Radix Sort sorts numbers digit by digit without comparing elements directly.

Explain the main difference between comparison based and non comparison based sorting.

Think about how the algorithms decide the order of elements.

Describe a scenario where non comparison based sorting is more efficient than comparison based sorting.

Consider when counting or grouping helps speed up sorting.