Comparison Based vs Non Comparison Based Sorting in DSA Java - Build Both Approaches

Comparison Based vs Non Comparison Based Sorting

📖 Scenario: You work in a warehouse where you need to organize boxes by their weight. Some boxes have weights that can be compared directly, while others have weights represented as categories. You want to learn two ways to sort these boxes: by comparing weights directly and by using a counting method when weights are limited.

🎯 Goal: Build two sorting methods in Java: one that sorts an array of integers by comparing elements (comparison based), and another that sorts an array of integers using counting (non-comparison based). Then print the sorted arrays to see the difference.

📋 What You'll Learn

Create an integer array called weightsComparison with values 4, 2, 7, 1, 3

Create an integer array called weightsCounting with values 4, 2, 7, 1, 3

Create a method comparisonSort that sorts an integer array using Arrays.sort()

Create a method countingSort that sorts an integer array using counting sort logic

Print the sorted arrays after applying each sorting method

💡 Why This Matters

🌍 Real World

Sorting is used everywhere: organizing items, searching efficiently, and preparing data for reports.

💼 Career

Understanding different sorting methods helps in choosing the right algorithm for tasks in software development and data processing.

1

Create the initial arrays

Create two integer arrays called weightsComparison and weightsCounting with these exact values: 4, 2, 7, 1, 3

DSA Java

// Create the arrays weightsComparison and weightsCounting with values 4, 2, 7, 1, 3
// Your code here

Hint

Use int[] to create arrays and assign the exact values inside curly braces.

2

Add sorting methods

Create two methods: comparisonSort that takes an integer array and sorts it using Arrays.sort(), and countingSort that takes an integer array and sorts it using counting sort logic

DSA Java

int[] weightsComparison = {4, 2, 7, 1, 3};
int[] weightsCounting = {4, 2, 7, 1, 3};

// Create comparisonSort method using Arrays.sort()
// Create countingSort method using counting sort logic
// Your code here

Hint

Use Arrays.sort() for comparisonSort. For countingSort, count occurrences and overwrite the array in order.

3

Apply sorting methods

Call comparisonSort(weightsComparison) and countingSort(weightsCounting) to sort both arrays

DSA Java

import java.util.Arrays;

int[] weightsComparison = {4, 2, 7, 1, 3};
int[] weightsCounting = {4, 2, 7, 1, 3};

public static void comparisonSort(int[] arr) {
    Arrays.sort(arr);
}

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  0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

// Call comparisonSort and countingSort on the arrays
// Your code here

Hint

Call the sorting methods with the exact array names.

4

Print the sorted arrays

Print the sorted arrays using System.out.println(Arrays.toString(weightsComparison)) and System.out.println(Arrays.toString(weightsCounting))

DSA Java

import java.util.Arrays;

public class SortingDemo {
    public static void main(String[] args) {
        int[] weightsComparison = {4, 2, 7, 1, 3};
        int[] weightsCounting = {4, 2, 7, 1, 3};

        comparisonSort(weightsComparison);
        countingSort(weightsCounting);

        // Print the sorted arrays below
        // Your code here
    }

    public static void comparisonSort(int[] arr) {
        Arrays.sort(arr);
    }

    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  0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }
}

Hint

Use System.out.println(Arrays.toString(array)) to print arrays in readable form.

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