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

Concept Flow - Comparison Based vs Non Comparison Based Sorting

Start: Unsorted Array

↓

Comparison Based

↓

Compare elements

↓

Swap or reorder

↓

Repeat until sorted

↓

Sorted Array

Sorting starts with an unsorted array, then splits into two main ways: comparison based sorts compare and swap elements repeatedly, while non-comparison sorts use element properties like counting or bucketing to order without direct comparisons.

Execution Sample

DSA Java

int[] arr = {4, 2, 7, 1};
// Comparison based: Bubble Sort
for (int i = 0; i < arr.length - 1; i++) {
  for (int j = 0; j < arr.length - 1 - i; j++) {
    if (arr[j] > arr[j+1]) {
      int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
    }
  }
}

This code sorts an array using bubble sort, a comparison based method that swaps adjacent elements if they are in wrong 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	No more comparisons needed	[1, 2, 4, 7]	N/A	N/A	[1, 2, 4, 7]

💡 All elements are in ascending order after completing n-1 passes; sorting complete.

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]
i (outer loop)	0	0	0	2	2
j (inner loop)	0	1	2	0	N/A

Key Moments - 3 Insights

Why do comparison based sorts need to compare elements multiple times?

Because each comparison can only fix the order of two elements, multiple passes ensure all elements move to correct positions, as shown in steps 1 to 6 where swaps gradually sort the array.

How does non comparison based sorting avoid comparing elements?

It uses element properties like counting occurrences or placing elements into buckets based on value ranges, so it orders elements by position rather than direct comparison.

Why does bubble sort stop after these steps?

The outer loop runs n-1 times (here 3 passes), with each pass bubbling the largest remaining element to its correct position at the end of the array.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 3?

A [2, 4, 7, 1]

B [2, 4, 1, 7]

C [4, 2, 7, 1]

D [1, 2, 4, 7]

💡 Hint

Check the 'Resulting Array' column in row for step 3.

At which step does the first swap occur?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look at the 'Swap?' column to find the first 'Yes'.

If the array was already sorted, how would the execution table change?

A No swaps would occur.

B More swaps would occur to confirm order.

C The array would be reversed.

D The algorithm would not run.

💡 Hint

If already sorted, all 'Swap?' entries would be 'No', but the algorithm completes all passes.

Concept Snapshot

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

Non Comparison Based Sorting:
- Uses element properties (counting, bucketing)
- Examples: Counting Sort, Radix Sort
- Can be faster for specific data types

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

Full Transcript

This lesson shows two main types of sorting: comparison based and non comparison based. Comparison based sorting compares pairs of elements and swaps them if needed, repeating until sorted. Non comparison based sorting uses properties like counting or bucketing to order elements without direct comparisons. The example code uses bubble sort, a comparison based method, showing step-by-step how elements are compared and swapped until the array is sorted. Key moments explain why multiple comparisons are needed, how non comparison sorts work differently, and why sorting stops when no swaps happen. The quiz tests understanding of array states during sorting and differences between the two methods.

Practice

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

easy

A. Quick Sort

B. Merge Sort

C. Counting Sort

D. Heap Sort

Solution

1. Step 1: Understand comparison vs non-comparison sorting

   Comparison based sorting algorithms decide order by comparing elements. Non-comparison sorts use other methods like counting or indexing.

2. Step 2: Identify Counting Sort type

   Counting Sort counts occurrences of elements and places them directly, without comparing elements.

3. Final Answer:

   Counting Sort -> Option C

4. Quick Check:

   Counting Sort is non-comparison based [OK]

Hint: Counting Sort uses counts, no element 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 way to declare a Counting Sort method header in Java?

easy

A. void countingSort(int arr[])

B. public void countingSort(int[] arr)

C. public int countingSort(int[] arr)

D. countingSort(int[] arr) void

Solution

1. Step 1: Recall Java method declaration syntax

   Java methods must specify access modifier, return type, method name, and parameters correctly.

2. Step 2: Check each option

   public void countingSort(int[] arr) uses public access, void return type, and correct parameter syntax. void countingSort(int arr[]) misses access modifier. public int countingSort(int[] arr) returns int incorrectly. countingSort(int[] arr) void has invalid syntax.

3. Final Answer:

   public void countingSort(int[] arr) -> Option B

4. Quick Check:

   Java method header syntax = public void countingSort(int[] arr) [OK]

Hint: Java methods need access modifier and return type first [OK]

Common Mistakes:

• Omitting access modifier
• Wrong return type for void methods
• Incorrect parameter syntax

3. What will be the output of the following Java code snippet using Counting Sort on array [4, 2, 2, 8, 3, 3, 1]?

int[] arr = {4, 2, 2, 8, 3, 3, 1};
countingSort(arr);
System.out.println(Arrays.toString(arr));

// Assume countingSort is correctly implemented

medium

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

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

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

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

Solution

1. Step 1: Understand Counting Sort output

   Counting Sort sorts the array in ascending order by counting occurrences.

2. Step 2: Sort the given array

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

3. Final Answer:

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

4. Quick Check:

   Counting Sort output = sorted array [OK]

Hint: Counting Sort outputs sorted array ascending [OK]

Common Mistakes:

• Confusing original and sorted array
• Assuming reverse order output
• Ignoring duplicates in output

4. Identify the error in the following Counting Sort implementation snippet:

public void countingSort(int[] arr) {
  int max = arr[0];
  for (int i = 1; i <= arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  // rest of the code
}

medium

A. The loop should start from i = 0, not 1.

B. Variable max should be initialized to 0, not arr[0].

C. The if condition should use < max instead of >.

D. Loop condition should be i < arr.length instead of <=.

Solution

1. Step 1: Analyze loop boundary

   Array indices go from 0 to arr.length - 1. Using i <= arr.length causes out-of-bounds error.

2. Step 2: Correct loop condition

   Change loop to i < arr.length to avoid accessing invalid index.

3. Final Answer:

   Loop condition should be i < arr.length instead of <= -> Option D

4. Quick Check:

   Array index out-of-bounds fixed by i < arr.length [OK]

Hint: Array loops use i < length, not <= length [OK]

Common Mistakes:

• Using <= in loop causing runtime error
• Initializing max incorrectly
• Wrong comparison operator in if

5. You want to sort a large array of integers where the values range only from 0 to 1000. Which sorting algorithm is the most efficient choice and why?

hard

A. Counting Sort, because it sorts in O(n + k) time where k is the range.

B. Merge Sort, because it is stable and works well on large data.

C. Quick Sort, because it has average O(n log n) time.

D. Heap Sort, because it uses a heap data structure.

Solution

1. Step 1: Analyze data range and size

   Array values range from 0 to 1000, which is a small fixed range (k = 1001).

2. Step 2: Choose sorting algorithm based on range

   Counting Sort runs in O(n + k), efficient when k is small compared to n, better than comparison sorts O(n log n).

3. Final Answer:

   Counting Sort, because it sorts in O(n + k) time where k is the range. -> Option A

4. Quick Check:

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

Hint: Small range arrays use Counting Sort for best speed [OK]

Common Mistakes:

• Choosing Quick Sort ignoring range advantage
• Assuming Merge Sort always best
• Not considering Counting Sort efficiency