Recall & Review
beginner
What is comparison based sorting?
Sorting methods that decide the order by comparing elements with each other, like checking if one number is bigger or smaller than another.
Click to reveal answer
beginner
Name two common comparison based sorting algorithms.
Bubble Sort and Quick Sort are examples of comparison based sorting algorithms.
Click to reveal answer
beginner
What is non comparison based sorting?
Sorting methods that do not compare elements directly but use other properties like counting or digit positions to sort, such as counting sort or radix sort.
Click to reveal answer
intermediate
Why can non comparison based sorting be faster than comparison based sorting?
Because they use special tricks like counting or grouping elements, they can sort in linear time when conditions are right, instead of needing many comparisons.
Click to reveal answer
intermediate
What is the best possible time complexity for comparison based sorting?
The best possible time complexity for comparison based sorting is O(n log n), meaning it cannot be faster than that in general.
Click to reveal answer
Which sorting method uses direct element comparisons?
✗ Incorrect
Comparison based sorting relies on comparing elements to decide order.
Which sorting algorithm is an example of non comparison based sorting?
✗ Incorrect
Counting sort uses counting of elements and does not compare them directly.
What is the lower bound time complexity for comparison based sorting?
✗ Incorrect
Comparison based sorting cannot be faster than O(n log n) in general.
Which sorting method can achieve linear time complexity under certain conditions?
✗ Incorrect
Non comparison based sorting like counting sort can run in O(n) time if input conditions are met.
Radix sort is an example of:
✗ Incorrect
Radix sort sorts numbers by digits without comparing elements directly.
Explain the main difference between comparison based and non comparison based sorting.
Think about how the sorting decides order.
You got /3 concepts.
List examples of comparison based and non comparison based sorting algorithms and their typical time complexities.
Recall common sorting algorithms and their categories.
You got /2 concepts.