Sorting Stability and When to Use Which Sort in DSA Java - Build from Scratch

Sorting Stability and When to Use Which Sort

📖 Scenario: You work in a bookstore that keeps a list of books. Each book has a title and a year it was published. Sometimes, you want to sort the books by year, but if two books have the same year, you want to keep their original order.This is called stable sorting. You will learn how to sort the list of books by year while keeping the order of books with the same year.

🎯 Goal: You will create a list of books, then sort them by year using a stable sort. You will also see what happens if you use an unstable sort. Finally, you will print the sorted list to understand sorting stability and when to use which sort.

📋 What You'll Learn

Create a list of Book objects with exact titles and years

Create a variable to hold the sorting method choice

Sort the list by year using the chosen sorting method

Print the sorted list showing title and year

💡 Why This Matters

🌍 Real World

Sorting books or products by attributes like year or price while keeping the original order of items with the same attribute is common in inventory systems, online stores, and databases.

💼 Career

Understanding sorting stability helps software developers choose the right sorting method to avoid bugs and maintain data order, especially when sorting complex data structures.

1

Create the list of books

Create a class called Book with two fields: String title and int year. Then create a List<Book> called books with these exact entries: ("The Hobbit", 1937), ("1984", 1949), ("Animal Farm", 1945), ("Brave New World", 1932), ("Fahrenheit 451", 1953), ("The Catcher in the Rye", 1951), ("Lord of the Flies", 1954), ("The Great Gatsby", 1925), ("To Kill a Mockingbird", 1960), ("The Hobbit", 1937) (note the duplicate title and year).

DSA Java

// Define the Book class and create the books list with given entries
// Your code here

Hint

Define the Book class with a constructor. Then create an ArrayList and add the books exactly as given.

2

Add a variable to choose sorting method

Add a String variable called sortMethod and set it to "stable". This variable will decide which sorting method to use later.

DSA Java

import java.util.*;

class Book {
    String title;
    int year;

    Book(String title, int year) {
        this.title = title;
        this.year = year;
    }
}

public class Main {
    public static void main(String[] args) {
        List books = new ArrayList();
        books.add(new Book("The Hobbit", 1937));
        books.add(new Book("1984", 1949));
        books.add(new Book("Animal Farm", 1945));
        books.add(new Book("Brave New World", 1932));
        books.add(new Book("Fahrenheit 451", 1953));
        books.add(new Book("The Catcher in the Rye", 1951));
        books.add(new Book("Lord of the Flies", 1954));
        books.add(new Book("The Great Gatsby", 1925));
        books.add(new Book("To Kill a Mockingbird", 1960));
        books.add(new Book("The Hobbit", 1937));

        // Add a String variable sortMethod and set it to "stable"
        // Your code here
    }
}

Hint

Just add String sortMethod = "stable"; inside the main method after creating the list.

3

Sort the list by year using the chosen method

Use an if statement to check if sortMethod equals "stable". If yes, use Collections.sort with a Comparator.comparingInt on book.year to sort the list stably by year. Otherwise, use books.sort with a custom comparator that compares years but swaps order if years are equal (to simulate an unstable sort).

DSA Java

import java.util.*;

class Book {
    String title;
    int year;

    Book(String title, int year) {
        this.title = title;
        this.year = year;
    }
}

public class Main {
    public static void main(String[] args) {
        List books = new ArrayList();
        books.add(new Book("The Hobbit", 1937));
        books.add(new Book("1984", 1949));
        books.add(new Book("Animal Farm", 1945));
        books.add(new Book("Brave New World", 1932));
        books.add(new Book("Fahrenheit 451", 1953));
        books.add(new Book("The Catcher in the Rye", 1951));
        books.add(new Book("Lord of the Flies", 1954));
        books.add(new Book("The Great Gatsby", 1925));
        books.add(new Book("To Kill a Mockingbird", 1960));
        books.add(new Book("The Hobbit", 1937));

        String sortMethod = "stable";

        // Use if to check sortMethod and sort accordingly
        // Your code here
    }
}

Hint

Use if (sortMethod.equals("stable")) to choose sorting. For stable, use Collections.sort with Comparator.comparingInt. For unstable, use books.sort with a comparator that returns 1 when years are equal.

4

Print the sorted list

Use a for loop with variable book to iterate over books. Inside the loop, print the book's title and year in this exact format: title + " (" + year + ")".

DSA Java

import java.util.*;

class Book {
    String title;
    int year;

    Book(String title, int year) {
        this.title = title;
        this.year = year;
    }
}

public class Main {
    public static void main(String[] args) {
        List books = new ArrayList();
        books.add(new Book("The Hobbit", 1937));
        books.add(new Book("1984", 1949));
        books.add(new Book("Animal Farm", 1945));
        books.add(new Book("Brave New World", 1932));
        books.add(new Book("Fahrenheit 451", 1953));
        books.add(new Book("The Catcher in the Rye", 1951));
        books.add(new Book("Lord of the Flies", 1954));
        books.add(new Book("The Great Gatsby", 1925));
        books.add(new Book("To Kill a Mockingbird", 1960));
        books.add(new Book("The Hobbit", 1937));

        String sortMethod = "stable";

        if (sortMethod.equals("stable")) {
            Collections.sort(books, Comparator.comparingInt(book -> book.year));
        } else {
            books.sort((b1, b2) -> {
                if (b1.year == b2.year) {
                    return 1; // swap order to simulate unstable sort
                } else {
                    return Integer.compare(b1.year, b2.year);
                }
            });
        }

        // Use a for loop to print each book's title and year in the format: title (year)
        // Your code here
    }
}

Hint

Use for (Book book : books) to loop through the list. Print each book's title and year exactly as shown.

Practice

1. Which sorting algorithm is stable by default, meaning it keeps the original order of equal elements?

easy

A. Heap Sort

B. Merge Sort

C. Quick Sort

D. Selection Sort

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of equal elements unchanged after sorting.

2. Step 2: Identify stable sorting algorithms

   Merge Sort is stable because it merges sorted subarrays without changing order of equal elements. Heap Sort, Quick Sort, and Selection Sort are not stable by default.

3. Final Answer:

   Merge Sort -> Option B

4. Quick Check:

   Stable sort = Merge Sort [OK]

Hint: Stable sorts keep equal items in original order [OK]

Common Mistakes:

• Thinking Quick Sort is stable
• Confusing Heap Sort as stable
• Assuming Selection Sort preserves order

2. Which of the following is the correct Java syntax to call a stable sorting method on an array named arr?

easy

A. Collections.stableSort(arr);

B. Collections.sort(arr);

C. Arrays.stableSort(arr);

D. Arrays.sort(arr);

Solution

1. Step 1: Identify Java sorting methods

   Java's Arrays.sort() method sorts arrays and uses a stable sort for objects.

2. Step 2: Check method availability

   There is no stableSort method in Java's standard libraries. Collections.sort() works on lists, not arrays.

3. Final Answer:

   Arrays.sort(arr); -> Option D

4. Quick Check:

   Correct syntax for array sort = Arrays.sort(arr); [OK]

Hint: Use Arrays.sort for arrays, Collections.sort for lists [OK]

Common Mistakes:

• Using Collections.sort on arrays
• Assuming stableSort method exists
• Confusing array and list sorting methods

3. What is the output of the following Java code snippet?

class Item {
  int value;
  String name;
  Item(int v, String n) { value = v; name = n; }
  public String toString() { return name; }
}

Item[] arr = {
  new Item(2, "apple"),
  new Item(1, "banana"),
  new Item(2, "cherry"),
  new Item(1, "date")
};

Arrays.sort(arr, Comparator.comparingInt(i -> i.value));
for (Item i : arr) System.out.print(i + " ");

medium

A. banana date apple cherry

B. date banana cherry apple

C. apple cherry banana date

D. banana date cherry apple

Solution

1. Step 1: Understand sorting criteria and stability

   The array is sorted by value using Arrays.sort with a comparator. Java's TimSort is stable, so equal values keep original order.

2. Step 2: Trace sorting and output

   Items with value 1 are "banana" then "date" (original order). Items with value 2 are "apple" then "cherry". Sorted order: banana, date, apple, cherry.

3. Final Answer:

   banana date apple cherry -> Option A

4. Quick Check:

   Stable sort keeps equal values order: banana date apple cherry [OK]

Hint: Stable sort keeps original order for equal keys [OK]

Common Mistakes:

• Assuming unstable sort changes order of equal values
• Mixing up item names in output
• Ignoring stability of Java's Arrays.sort with comparator

4. The following code tries to sort an array of integers but does not preserve the order of equal elements. What is the main issue?

int[] arr = {4, 2, 4, 3};
Arrays.sort(arr);
// Expected stable sort but order of equal 4s changed

medium

A. Arrays.sort on primitives is not stable

B. Comparator is missing for stability

C. Array contains duplicates causing error

D. Arrays.sort cannot sort integers

Solution

1. Step 1: Check sorting method on primitive arrays

   Java's Arrays.sort on primitive types (like int[]) uses a dual-pivot quicksort which is not stable.

2. Step 2: Understand stability for primitives vs objects

   For objects, Java uses TimSort which is stable. For primitives, stability is not guaranteed, so equal elements may reorder.

3. Final Answer:

   Arrays.sort on primitives is not stable -> Option A

4. Quick Check:

   Primitive sort = unstable Arrays.sort [OK]

Hint: Primitive array sort in Java is unstable [OK]

Common Mistakes:

• Expecting stability on primitive arrays
• Thinking missing comparator causes instability
• Assuming duplicates cause errors

5. You have a list of employee records with fields id and salary. You want to sort by salary ascending but keep employees with the same salary in the order they were added. Which sorting approach is best?

hard

A. Use Heap Sort to guarantee order of equal salaries

B. Use Quick Sort for faster average performance ignoring stability

C. Use a stable sort like Merge Sort on the list by salary

D. Sort by id first, then by salary using unstable sort

Solution

1. Step 1: Understand requirement for stability

   We want to keep original order of employees with same salary, so stability is required.

2. Step 2: Choose sorting algorithm with stability

   Merge Sort is stable and sorts by salary while preserving order of equal salaries. Quick Sort and Heap Sort are not stable by default.

3. Final Answer:

   Use a stable sort like Merge Sort on the list by salary -> Option C

4. Quick Check:

   Stable sort needed for preserving order = Merge Sort [OK]

Hint: Stable sort keeps equal keys in original order [OK]

Common Mistakes:

• Choosing unstable sorts ignoring order preservation
• Sorting by id first without stable sort
• Assuming Heap Sort is stable