Comparison Based vs Non Comparison Based Sorting in DSA Java - 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: [4, 2, 7, 1, 3]
Comparison Based: compare pairs -> swap if needed
Non Comparison Based: use value as index -> place in bins

Dry Run Walkthrough

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

Goal: Show how comparison based sorting and non comparison based sorting organize the array differently

Step 1: comparison based: compare 4 and 2, swap because 4 > 2

[2, 4, 7, 1, 3]

Why: We swap to move smaller elements forward

Step 2: comparison based: compare 4 and 7, no swap because 4 < 7

[2, 4, 7, 1, 3]

Why: No swap needed if order is correct

Step 3: comparison based: compare 7 and 1, swap because 7 > 1

[2, 4, 1, 7, 3]

Why: Move smaller element 1 forward

Step 4: non comparison based: count frequency of each number

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

Why: We use counts to place elements directly

Step 5: non comparison based: place elements in order using counts

[1, 2, 3, 4, 7]

Why: Direct placement avoids comparisons

Result:

Comparison based sorted array: [1, 2, 3, 4, 7]
Non comparison based sorted array: [1, 2, 3, 4, 7]

Annotated Code

DSA Java

import java.util.Arrays;

public class SortingComparison {

    // Comparison based sorting: Bubble Sort
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // Non comparison based sorting: Counting Sort (works for non-negative integers)
    public static void countingSort(int[] arr) {
        if (arr.length == 0) return;
        int max = Arrays.stream(arr).max().orElse(0);
        int[] count = new int[max + 1];

        for (int num : arr) {
            count[num]++;
        }

        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {4, 2, 7, 1, 3};
        int[] arr2 = {4, 2, 7, 1, 3};

        bubbleSort(arr1);
        System.out.println("Comparison based sorted array: " + Arrays.toString(arr1));

        countingSort(arr2);
        System.out.println("Non comparison based sorted array: " + Arrays.toString(arr2));
    }
}

if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; }

swap elements if left is greater than right to sort by comparison

for (int num : arr) { count[num]++; }

count frequency of each element for direct placement

while (count[i] > 0) { arr[index++] = i; count[i]--; }

place elements back into array based on counts without comparing

Output

Comparison based sorted array: [1, 2, 3, 4, 7]

Non comparison based sorted array: [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 max value because it counts and places elements directly

Space: O(1) for comparison based as it sorts in place; O(k) for non comparison based due to count array storage

vs Alternative: Comparison based sorts are general and work on any data but slower; non comparison based sorts are faster but need constraints like integer keys within a range

Edge Cases

empty array

both sorts handle gracefully and return empty array

DSA Java

int n = arr.length;

array with duplicates

both sorts correctly sort and keep duplicates

DSA Java

count[num]++;

array with large max value for counting sort

counting sort uses large extra space, may be inefficient

DSA Java

int[] count = new int[max + 1];

When to Use This Pattern

When sorting integers or keys with limited range, consider non comparison based sorting for efficiency; otherwise, use comparison based sorting for general data.

Common Mistakes

Mistake: Using counting sort on negative numbers without adjustment
Fix: Adjust array values to be non-negative or use a different sorting method

Mistake: Assuming non comparison based sorts always use less time
Fix: Remember non comparison based sorts depend on input constraints like range

Summary

Comparison based sorting uses element comparisons to order data; non comparison based sorting uses element values directly to place them.

Use comparison based sorting for general data types and non comparison based sorting for integers with limited range for better performance.

The key insight is that non comparison based sorting avoids pairwise comparisons by leveraging the data's value properties.

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