Comparison Based vs Non Comparison Based Sorting in DSA Rust - Trade-offs & Analysis

Mental Model

Sorting can be done by comparing elements or by using their values directly without comparing.

Analogy: Imagine sorting books by comparing their titles one by one (comparison based) versus sorting mail by zip codes directly into bins (non comparison based).

Array before sorting:
[4, 2, 7, 1, 3]

Comparison based sorting:
Compare pairs and swap -> gradually order array

Non comparison based sorting:
Use value properties (like digits) to place elements directly into positions

Dry Run Walkthrough

Input: array: [4, 2, 7, 1, 3]

Goal: Show how comparison based and non comparison based sorting work differently to sort the array

Step 1: Start comparison based sorting (Bubble Sort): compare first two elements 4 and 2

[4, 2, 7, 1, 3]

Why: We need to find if 4 > 2 to decide if swap is needed

Step 2: Swap 4 and 2 because 4 > 2

[2, 4, 7, 1, 3]

Why: Smaller element moves left to sort array gradually

Step 3: Compare 4 and 7, no swap needed

[2, 4, 7, 1, 3]

Why: 4 < 7 so order is correct here

Step 4: Compare 7 and 1, swap because 7 > 1

[2, 4, 1, 7, 3]

Why: Move smaller element left

Step 5: Compare 7 and 3, swap because 7 > 3

[2, 4, 1, 3, 7]

Why: Move smaller element left

Step 6: Start non comparison based sorting (Counting Sort): count occurrences of each number

Counts: {1:1, 2:1, 3:1, 4:1, 7:1}

Why: Counting sort uses counts to place elements directly

Step 7: Place elements in order using counts

[1, 2, 3, 4, 7]

Why: Direct placement avoids comparisons

Result:

Sorted array:
[1, 2, 3, 4, 7]

Annotated Code

DSA Rust

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); // swap to order elements
            }
        }
    }
}

fn counting_sort(arr: &[i32]) -> Vec<i32> {
    if arr.is_empty() {
        return vec![];
    }
    let max = *arr.iter().max().unwrap();
    let mut count = vec![0; (max + 1) as usize];
    for &num in arr {
        count[num as usize] += 1; // count occurrences
    }
    let mut sorted = Vec::with_capacity(arr.len());
    for (num, &c) in count.iter().enumerate() {
        for _ in 0..c {
            sorted.push(num as i32); // place elements directly
        }
    }
    sorted
}

fn main() {
    let mut arr1 = vec![4, 2, 7, 1, 3];
    bubble_sort(&mut arr1);
    println!("Bubble Sort Result: {:?}", arr1);

    let arr2 = vec![4, 2, 7, 1, 3];
    let sorted_arr2 = counting_sort(&arr2);
    println!("Counting Sort Result: {:?}", sorted_arr2);
}

if arr[j] > arr[j + 1] { arr.swap(j, j + 1); }

compare adjacent elements and swap if out of order

count[num as usize] += 1;

count how many times each number appears

for (num, &c) in count.iter().enumerate() { for _ in 0..c { sorted.push(num as i32); } }

place numbers in sorted order based on counts

Output

Bubble Sort Result: [1, 2, 3, 4, 7]

Counting Sort Result: [1, 2, 3, 4, 7]

Complexity Analysis

Time: O(n^2) for comparison based (bubble sort) because it compares pairs repeatedly; O(n + k) for non comparison based (counting sort) where k is range of input values

Space: O(1) extra space for bubble sort; O(k) extra space for counting sort to store counts

vs Alternative: Comparison based sorts work on any data but can be slower; non comparison based sorts are faster but need special conditions like small integer ranges

Edge Cases

empty array

both sorts return empty array without error

DSA Rust

if arr.is_empty() { return vec![]; }

array with one element

array remains unchanged as it is already sorted

DSA Rust

for i in 0..n { for j in 0..n - i - 1 { ... } }

array with duplicate elements

both sorts correctly handle duplicates and keep them in sorted order

DSA Rust

count[num as usize] += 1;

When to Use This Pattern

When you see sorting problems with numeric keys in a limited range, consider non comparison based sorting for faster results; otherwise, use comparison based sorting for general data.

Common Mistakes

Mistake: Trying to use counting sort on data with large or unknown ranges causing high memory use
Fix: Check input range before using counting sort; use comparison based sort if range is too large

Mistake: Assuming comparison based sorts are always slower without considering input size
Fix: Remember comparison based sorts work well for small or general data

Summary

Comparison based sorting orders elements by comparing pairs; non comparison based sorting uses element values directly to place them.

Use comparison based sorting for general data and non comparison based sorting when input values are integers in a small range.

The key insight is that non comparison based sorting can be faster by avoiding comparisons but needs special input conditions.

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