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

Recall & Review

beginner

What is comparison based sorting?

Sorting methods that decide the order by comparing elements directly, like checking if one number is bigger than another.

beginner

Name two common comparison based sorting algorithms.

Bubble Sort and Quick Sort are examples where elements are compared to decide their order.

beginner

What is non comparison based sorting?

Sorting methods that do not compare elements directly but use other properties like digits or counts to sort, for example, counting 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 when conditions are right, avoiding many comparisons.

intermediate

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

O(n log n) is the fastest possible average time for comparison based sorting algorithms.

Which sorting type uses direct element comparisons?

A Counting sort

B Comparison based sorting

C Non comparison based sorting

D Bucket sort

Comparison based sorting uses direct comparisons between elements.

Which algorithm is an example of non comparison based sorting?

A Merge sort

B Quick sort

C Counting sort

D Heap sort

Counting sort sorts by counting occurrences, not by comparing elements.

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

A O(n)

B O(n^2)

C O(log n)

D O(n log n)

Comparison based sorting cannot be faster than O(n log n) on average.

Which sorting method can achieve linear time complexity under certain conditions?

A Counting sort

B Bubble sort

C Quick sort

D Insertion sort

Counting sort can run in O(n) time when the range of input is limited.

Which sorting type is generally more flexible for any kind of data?

A Comparison based sorting

B Non comparison based sorting

C Counting sort

D Radix sort

Comparison based sorting works on any data that can be compared.

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

Think about how the sorting decides order.

Describe when you would choose non comparison based sorting over comparison based sorting.

Consider input data properties and speed needs.

Practice

1. Which of the following sorting algorithms is non-comparison based?

easy

A. Heap Sort

B. Merge Sort

C. Quick Sort

D. Counting Sort

Solution

1. Step 1: Understand comparison based sorting

   Comparison based sorting algorithms decide order by comparing elements, like Merge Sort, Quick Sort, and Heap Sort.

2. Step 2: Identify non-comparison based sorting

   Counting Sort uses element values directly to sort without comparing elements.

3. Final Answer:

   Counting Sort -> Option D

4. Quick Check:

   Non-comparison based = Counting Sort [OK]

Hint: Non-comparison sorts use element values, not comparisons [OK]

Common Mistakes:

• Confusing Merge Sort as non-comparison
• Thinking Quick Sort is non-comparison
• Assuming Heap Sort is non-comparison

2. Which of the following is the correct Rust syntax to call a non-comparison based sorting function counting_sort on a mutable vector arr?

easy

A. counting_sort(&mut arr);

B. counting_sort(arr);

C. counting_sort(&arr);

D. counting_sort(mut arr);

Solution

1. Step 1: Understand Rust borrowing rules for mutable vectors

   To modify a vector inside a function, we pass a mutable reference using &mut.

2. Step 2: Identify correct function call syntax

   Calling counting_sort(&mut arr); passes a mutable reference correctly.

3. Final Answer:

   counting_sort(&mut arr); -> Option A

4. Quick Check:

   Mutable reference call = counting_sort(&mut arr); [OK]

Hint: Use &mut to pass mutable vector to sorting function [OK]

Common Mistakes:

• Passing vector without reference
• Passing immutable reference &arr
• Using invalid syntax like mut arr

3. What will be the output of the following Rust code snippet?

let mut arr = vec![4, 2, 2, 8, 3, 3, 1];
counting_sort(&mut arr);
println!("{:?}", arr);

Assuming counting_sort correctly sorts the vector in ascending order.

medium

A. [1, 2, 3, 4, 8]

B. [1, 2, 2, 3, 3, 4, 8]

C. [8, 4, 3, 3, 2, 2, 1]

D. [4, 2, 2, 8, 3, 3, 1]

Solution

1. Step 1: Understand counting sort behavior

   Counting sort sorts elements in ascending order, preserving duplicates.

2. Step 2: Sort the given vector

   Sorted vector is [1, 2, 2, 3, 3, 4, 8].

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option B

4. Quick Check:

   Sorted ascending = [1, 2, 2, 3, 3, 4, 8] [OK]

Hint: Counting sort outputs sorted ascending with duplicates intact [OK]

Common Mistakes:

• Reversing order to descending
• Removing duplicates incorrectly
• Printing original unsorted array

4. The following Rust code attempts to sort a vector using counting sort but causes a compilation error. What is the error?

fn counting_sort(arr: Vec<i32>) {
    // sorting logic
}

fn main() {
    let mut data = vec![3, 1, 4];
    counting_sort(data);
    println!("{:?}", data);
}

medium

A. Missing mutable keyword for data

B. counting_sort function missing return type

C. Cannot print data after move error

D. Syntax error in println! macro

Solution

1. Step 1: Identify ownership move in function call

   Passing data by value moves ownership to counting_sort.

2. Step 2: Understand why println! causes error

   After move, data is invalid in main, so printing causes compilation error.

3. Final Answer:

   Cannot print data after move error -> Option C

4. Quick Check:

   Ownership moved, data invalid after call [OK]

Hint: Passing vector by value moves ownership, invalid after call [OK]

Common Mistakes:

• Assuming mutable keyword fixes ownership move
• Thinking missing return type causes error
• Blaming println! syntax

5. You have a large dataset of integers ranging from 0 to 1000. Which sorting approach is more efficient and why?

hard

A. Counting Sort is best due to O(n + k) time with small range

B. Quick Sort is best due to average O(n log n) time

C. Bubble Sort is best for simplicity

D. Merge Sort is best for stable sorting

Solution

1. Step 1: Analyze dataset characteristics

   Dataset has integers in range 0 to 1000, so k=1001 is small compared to n.

2. Step 2: Compare sorting algorithm complexities

   Counting Sort runs in O(n + k), which is efficient for small k. Quick, Merge are O(n log n). Bubble Sort is slow O(n²).

3. Step 3: Choose best approach

   Counting Sort is more efficient here due to linear time with small range.

4. Final Answer:

   Counting Sort is best due to O(n + k) time with small range -> Option A

5. Quick Check:

   Small range + large data = Counting Sort best [OK]

Hint: Small range data? Use Counting Sort for linear time [OK]

Common Mistakes:

• Choosing Quick Sort ignoring range advantage
• Picking Bubble Sort for large data
• Ignoring Counting Sort's linear time benefit