Comparison Based vs Non Comparison Based Sorting in DSA Java - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Comparison Based Sorting Algorithm

What is the output of the following Java code that uses a comparison based sorting method (Arrays.sort)?

DSA Java

import java.util.Arrays;
public class Main {
  public static void main(String[] args) {
    int[] arr = {5, 3, 8, 1, 2};
    Arrays.sort(arr);
    for (int num : arr) {
      System.out.print(num + " ");
    }
  }
}

A 1 2 3 5 8

B 8 5 3 2 1

C 5 3 8 1 2

D 2 1 3 5 8

💡 Hint

Arrays.sort uses comparison based sorting to arrange elements in ascending order.

The Arrays.sort method in Java uses a comparison based sorting algorithm (Dual-Pivot Quicksort for primitives) which sorts the array in ascending order.

❓ Predict Output

intermediate

Output of Non Comparison Based Sorting Algorithm

What is the output of the following Java code that uses Counting Sort (a non comparison based sorting) on the array?

DSA Java

import java.util.Arrays;
public class Main {
  public static void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    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[] arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);
    for (int num : arr) {
      System.out.print(num + " ");
    }
  }
}

A 8 4 3 3 2 2 1

B 1 2 2 3 3 4 8

C 4 2 2 8 3 3 1

D 1 3 2 2 3 4 8

💡 Hint

Counting sort counts occurrences and places elements in order without comparisons.

Counting sort is a non comparison based sorting algorithm that counts the frequency of each element and reconstructs the sorted array.

🧠 Conceptual

advanced

Time Complexity Difference

Which statement correctly describes the time complexity difference between comparison based and non comparison based sorting algorithms?

A Comparison based sorting algorithms have a best time complexity of O(n), while non comparison based sorting algorithms always have O(n log n).

B Both comparison based and non comparison based sorting algorithms have the same worst case time complexity of O(n log n).

C Comparison based sorting algorithms cannot be faster than O(n log n) in the worst case, while some non comparison based sorting algorithms can achieve O(n) under certain conditions.

D Non comparison based sorting algorithms always have worse time complexity than comparison based sorting algorithms.

💡 Hint

Think about the theoretical lower bound for comparison based sorting.

Comparison based sorting algorithms have a theoretical lower bound of O(n log n) for worst case. Non comparison based algorithms like Counting Sort or Radix Sort can achieve O(n) when input constraints allow.

❓ Predict Output

advanced

Output of Radix Sort on Integer Array

What is the output of the following Java code that implements Radix Sort (a non comparison based sorting) on the array?

DSA Java

import java.util.*;
public class Main {
  public static void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10) {
      countingSortByDigit(arr, exp);
    }
  }
  private static void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];
    for (int i = 0; i < n; i++) {
      count[(arr[i] / exp) % 10]++;
    }
    for (int i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
      int digit = (arr[i] / exp) % 10;
      output[count[digit] - 1] = arr[i];
      count[digit]--;
    }
    System.arraycopy(output, 0, arr, 0, n);
  }
  public static void main(String[] args) {
    int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    for (int num : arr) {
      System.out.print(num + " ");
    }
  }
}

A 2 24 45 66 75 90 170 802

B 802 170 90 75 66 45 24 2

C 170 45 75 90 802 24 2 66

D 24 2 45 66 75 90 170 802

💡 Hint

Radix sort sorts numbers digit by digit starting from least significant digit.

Radix sort is a non comparison based sorting algorithm that sorts numbers by processing individual digits using counting sort as a subroutine.

🧠 Conceptual

expert

Choosing Sorting Algorithm Based on Data Characteristics

Given a large dataset of integers where the maximum value is small compared to the number of elements, which sorting algorithm is most efficient and why?

A Use Bubble Sort because it is simple and efficient for large datasets.

B Use MergeSort because it guarantees O(n log n) time regardless of data.

C Use QuickSort because it has average O(n log n) time and works well on all data.

D Use Counting Sort because it can sort in O(n + k) time where k is the max value, which is small here.

💡 Hint

Consider the relationship between maximum value and number of elements.

Counting Sort is efficient when the range of input values (k) is small compared to the number of elements (n), achieving O(n + k) time, which can be faster than comparison based sorts.

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