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

Concept Flow - Comparison Based vs Non Comparison Based Sorting

Start with unsorted array

↓

Comparison Based

↓

Compare pairs

↓

Swap if needed

↓

Repeat until sorted

↓

Sorted array

↓

Sorting complete

The flow shows how sorting starts with an array and splits into two types: comparison based sorts that compare and swap elements, and non-comparison based sorts that use counting or bucketing to sort without direct comparisons.

Execution Sample

DSA Rust

let mut arr = vec![4, 2, 7, 1];
// Comparison based: Bubble Sort
for i in 0..arr.len() {
  for j in 0..arr.len()-1-i {
    if arr[j] > arr[j+1] { arr.swap(j, j+1); }
  }
}

This code sorts an array using bubble sort, a comparison based sorting method that swaps elements if they are out of order.

Execution Table

Step	Operation	Array State	Comparison	Swap?	Resulting Array
1	Compare arr[0] and arr[1]	[4, 2, 7, 1]	4 > 2	Yes	[2, 4, 7, 1]
2	Compare arr[1] and arr[2]	[2, 4, 7, 1]	4 > 7	No	[2, 4, 7, 1]
3	Compare arr[2] and arr[3]	[2, 4, 7, 1]	7 > 1	Yes	[2, 4, 1, 7]
4	Compare arr[0] and arr[1]	[2, 4, 1, 7]	2 > 4	No	[2, 4, 1, 7]
5	Compare arr[1] and arr[2]	[2, 4, 1, 7]	4 > 1	Yes	[2, 1, 4, 7]
6	Compare arr[0] and arr[1]	[2, 1, 4, 7]	2 > 1	Yes	[1, 2, 4, 7]
7	Compare arr[0] and arr[1]	[1, 2, 4, 7]	1 > 2	No	[1, 2, 4, 7]
8	No more swaps, array sorted	[1, 2, 4, 7]	-	No	[1, 2, 4, 7]
9	Non-comparison: Counting sort count elements	[4, 2, 7, 1]	-	-	Count: {1:1, 2:1, 4:1, 7:1}
10	Rebuild sorted array from counts	-	-	-	[1, 2, 4, 7]

💡 Bubble sort ends when no swaps occur; counting sort ends after rebuilding array from counts.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	Final
arr	[4, 2, 7, 1]	[2, 4, 7, 1]	[2, 4, 1, 7]	[1, 2, 4, 7]	[1, 2, 4, 7]
swap_occurred	false	true	true	true	false
count_map	{}	{}	{}	{}	{1:1, 2:1, 4:1, 7:1}

Key Moments - 3 Insights

Why does bubble sort keep comparing even after some elements are in place?

Because bubble sort only guarantees the largest element moves to the end each pass, it must repeat comparisons to ensure all elements are sorted, as shown in steps 4-6 where smaller elements are still swapped.

How does counting sort avoid comparing elements?

Counting sort uses a count map to record how many times each element appears (step 9), then rebuilds the sorted array from these counts (step 10), so it never compares elements directly.

Why does bubble sort stop at step 8?

At step 8, no swaps occurred during the last pass, meaning the array is fully sorted, so the algorithm stops.

Visual Quiz - 3 Questions

Look at the execution table at step 3, what swap happened?

A Swapped elements 2 and 4

B Swapped elements 4 and 7

C Swapped elements 7 and 1

D No swap happened

💡 Hint

Check the 'Swap?' and 'Resulting Array' columns at step 3 in the execution table.

At which step does bubble sort confirm the array is sorted?

A Step 6

B Step 8

C Step 7

D Step 9

💡 Hint

Look for the step where 'No more swaps' is noted in the 'Operation' column.

If the array had duplicate elements, which sorting type handles it without comparisons?

A Non comparison based sorting

B Neither can handle duplicates

C Comparison based sorting

D Both handle duplicates the same way

💡 Hint

Refer to the counting sort steps (9 and 10) in the execution table where counts are used.

Concept Snapshot

Comparison Based Sorting:
- Sorts by comparing and swapping elements
- Examples: Bubble, Quick, Merge Sort
- Usually O(n log n) average time

Non Comparison Based Sorting:
- Sorts by counting or bucketing keys
- Examples: Counting, Radix, Bucket Sort
- Can be faster for limited range data

Key: Comparison sorts rely on element comparisons; non-comparison sorts use element properties.

Full Transcript

This lesson compares two main types of sorting: comparison based and non comparison based. Comparison based sorting works by comparing pairs of elements and swapping them if needed, repeating until the array is sorted. Bubble sort is an example, shown step-by-step with swaps and array states. Non comparison based sorting avoids direct comparisons by counting or grouping elements, then rebuilding the sorted array from these counts, as shown with counting sort. Key moments include understanding why bubble sort repeats comparisons even after some elements are sorted, how counting sort avoids comparisons, and when bubble sort stops. Visual quizzes test understanding of swaps, stopping conditions, and handling duplicates. The quick reference summarizes the differences and examples of each sorting type.

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