Comparison Based vs Non Comparison Based Sorting in DSA Rust - Complexity Comparison

Time Complexity: Comparison Based vs Non Comparison Based Sorting

O(n²) for comparison based, O(n + k) for non comparison based

Understanding Time Complexity

Sorting is a common task where we arrange items in order. Different sorting methods take different times depending on how they work.

We want to understand how the time to sort grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of these two sorting approaches.

// Comparison based sorting example: Bubble Sort
fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

// Non-comparison based sorting example: Counting Sort
fn counting_sort(arr: &mut [usize], max_val: usize) {
    let mut count = vec![0; max_val + 1];
    for &num in arr.iter() {
        count[num] += 1;
    }
    let mut idx = 0;
    for num in 0..=max_val {
        for _ in 0..count[num] {
            arr[idx] = num;
            idx += 1;
        }
    }
}
    

Bubble Sort compares and swaps elements repeatedly. Counting Sort counts occurrences and places elements directly.

Identify Repeating Operations

Look at the loops and repeated steps in each method.

• Bubble Sort primary operation: Comparing and swapping pairs inside nested loops.
• Bubble Sort how many times: Outer loop runs n times, inner loop runs up to n - i - 1 times, so about n x n = n² times.
• Counting Sort primary operation: Counting each number once, then placing numbers back.
• Counting Sort how many times: Counting loop runs n times, placement loop runs max_val times (range size).

How Execution Grows With Input

As the list size grows, how does the work increase?

Input Size (n)	Bubble Sort Ops (approx.)	Counting Sort Ops (approx.)
10	100 (10x10)	10 + max_val
100	10,000 (100x100)	100 + max_val
1000	1,000,000 (1000x1000)	1000 + max_val

Bubble Sort grows very fast as n increases (squares). Counting Sort grows mostly with n plus the range size, which can be smaller.

Final Time Complexity

Time Complexity: O(n²) for comparison based (Bubble Sort), O(n + k) for non comparison based (Counting Sort), where k is the range of input values.

This means Bubble Sort gets much slower as the list grows, but Counting Sort can be faster if the range k is not too big.

Common Mistake

[X] Wrong: "All sorting methods take about the same time because they all sort the list."

[OK] Correct: Different methods use different steps. Some compare many times, others count and place directly. This changes how time grows with list size.

Interview Connect

Understanding these differences helps you choose the right sorting method and explain your choice clearly. It shows you know how algorithms behave as data grows.

Self-Check

"What if the input range k in Counting Sort is much larger than n? How would that affect the time complexity?"

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