Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Insertion Sort for Object Sorting

Problem Statement

Write a Java program that extends the Insertion Sort implementation to sort an array of objects, specifically Student objects with a grade field, in ascending order based on a custom comparator that compares grades. The program should count the number of shifts performed (the number of times elements are moved to make space for insertion) and test with a sample dataset containing Student objects with varied grades, including duplicates and edge cases like empty arrays. Insertion Sort will build a sorted portion of the array, inserting each Student object into its correct position based on the comparator, shifting objects with higher grades. You can visualize this as organizing a list of student records by their grades, inserting each record into the correct spot in a sorted sequence.

Input:

  • An array of Student objects, each with a name (String) and grade (double) field. Output: The sorted array (by grade in ascending order), the number of shifts performed, and a string representation of the input and sorted arrays for clarity. Constraints:
  • The array length n is between 0 and 10^5.
  • Grades are doubles in the range [0.0, 100.0]. Example:
  • Input: array = [Student("Alice", 85.5), Student("Bob", 92.0), Student("Charlie", 78.5)]
  • Output:
    • Input Array: [Student(name=Alice, grade=85.5), Student(name=Bob, grade=92.0), Student(name=Charlie, grade=78.5)]
    • Sorted Array: [Student(name=Charlie, grade=78.5), Student(name=Alice, grade=85.5), Student(name=Bob, grade=92.0)]
    • Shifts: 3
  • Explanation: Insertion Sort sorts by grade, requiring 3 shifts to place students in ascending order.
  • Input: array = [Student("Eve", 90.0), Student("Eve", 90.0)]
  • Output:
    • Input Array: [Student(name=Eve, grade=90.0), Student(name=Eve, grade=90.0)]
    • Sorted Array: [Student(name=Eve, grade=90.0), Student(name=Eve, grade=90.0)]
    • Shifts: 0
  • Explanation: Duplicate grades require no shifts as order is preserved.

Pseudocode

FUNCTION insertionSort(arr, comparator)
    SET n to length of arr
    CREATE shifts as integer, initialized to 0
    FOR i from 1 to n-1
        SET key to arr[i]
        SET j to i - 1
        WHILE j >= 0 AND comparator.compare(arr[j], key) > 0
            SET arr[j + 1] to arr[j]
            INCREMENT shifts
            DECREMENT j
        ENDWHILE
        SET arr[j + 1] to key
    ENDFOR
    RETURN shifts
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element.toString() to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of Student arrays
    SET gradeComparator to new Comparator comparing Student grades
    FOR each testCase in testCases
        PRINT test case details
        CREATE copy of testCase array
        SET shifts to insertionSort(copy, gradeComparator)
        PRINT input array, sorted array, and shifts
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define Student class: a. Fields: name (String), grade (double). b. Include toString for readable output.
  2. Define insertionSort (generic): a. Accept an array of type T and a Comparator<T>. b. Initialize a counter shifts to 0. c. For each index i from 1 to n-1:
    • Store arr[i] as key.
    • Shift elements arr[j] where comparator.compare(arr[j], key) > 0, incrementing shifts.
    • Insert key at the correct position. d. Return the number of shifts.
  3. Define toString: a. Convert the array to a string, e.g., "[Student(name=Alice, grade=85.5), ...]".
  4. In main, test with: a. Mixed grades (n=5). b. Duplicate grades (n=4). c. Empty array (n=0). d. Single-element array (n=1). e. Sorted grades (n=6).

Java Implementation

import java.util.*;

public class InsertionSortObjectSorting {
    // Student class
    static class Student {
        String name;
        double grade;

        Student(String name, double grade) {
            this.name = name;
            this.grade = grade;
        }

        @Override
        public String toString() {
            return "Student(name=" + name + ", grade=" + grade + ")";
        }
    }

    // Performs Insertion Sort with custom comparator and counts shifts
    public <T> int insertionSort(T[] arr, Comparator<T> comparator) {
        int n = arr.length;
        int shifts = 0;
        for (int i = 1; i < n; i++) {
            T key = arr[i];
            int j = i - 1;
            while (j >= 0 && comparator.compare(arr[j], key) > 0) {
                arr[j + 1] = arr[j];
                shifts++;
                j--;
            }
            arr[j + 1] = key;
        }
        return shifts;
    }

    // Converts array to string
    public <T> String toString(T[] arr) {
        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            result.append(arr[i].toString());
            if (i < arr.length - 1) {
                result.append(", ");
            }
        }
        result.append("]");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Student[] arr;
        String description;

        TestCase(Student[] arr, String description) {
            this.arr = arr;
            this.description = description;
        }
    }

    // Main method to test object sorting
    public static void main(String[] args) {
        InsertionSortObjectSorting sorter = new InsertionSortObjectSorting();

        // Comparator for sorting by grade
        Comparator<Student> gradeComparator = (s1, s2) -> Double.compare(s1.grade, s2.grade);

        // Test cases
        TestCase[] testCases = {
            new TestCase(new Student[]{
                new Student("Alice", 85.5),
                new Student("Bob", 92.0),
                new Student("Charlie", 78.5),
                new Student("David", 95.0),
                new Student("Eve", 88.0)
            }, "Mixed grades (n=5)"),
            new TestCase(new Student[]{
                new Student("Frank", 90.0),
                new Student("Grace", 90.0),
                new Student("Hannah", 90.0),
                new Student("Ivy", 90.0)
            }, "Duplicate grades (n=4)"),
            new TestCase(new Student[]{}, "Empty (n=0)"),
            new TestCase(new Student[]{new Student("Jack", 75.0)}, "Single element (n=1)"),
            new TestCase(new Student[]{
                new Student("Kate", 70.0),
                new Student("Liam", 75.0),
                new Student("Mia", 80.0),
                new Student("Noah", 85.0),
                new Student("Olivia", 90.0),
                new Student("Peter", 95.0)
            }, "Sorted grades (n=6)")
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ": " + testCases[i].description);
            Student[] arr = testCases[i].arr.clone(); // Copy to preserve original
            System.out.println("Input Array: " + sorter.toString(arr));
            int shifts = sorter.insertionSort(arr, gradeComparator);
            System.out.println("Sorted Array: " + sorter.toString(arr));
            System.out.println("Shifts: " + shifts + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1: Mixed grades (n=5)
Input Array: [Student(name=Alice, grade=85.5), Student(name=Bob, grade=92.0), Student(name=Charlie, grade=78.5), Student(name=David, grade=95.0), Student(name=Eve, grade=88.0)]
Sorted Array: [Student(name=Charlie, grade=78.5), Student(name=Alice, grade=85.5), Student(name=Eve, grade=88.0), Student(name=Bob, grade=92.0), Student(name=David, grade=95.0)]
Shifts: 6

Test case 2: Duplicate grades (n=4)
Input Array: [Student(name=Frank, grade=90.0), Student(name=Grace, grade=90.0), Student(name=Hannah, grade=90.0), Student(name=Ivy, grade=90.0)]
Sorted Array: [Student(name=Frank, grade=90.0), Student(name=Grace, grade=90.0), Student(name=Hannah, grade=90.0), Student(name=Ivy, grade=90.0)]
Shifts: 0

Test case 3: Empty (n=0)
Input Array: []
Sorted Array: []
Shifts: 0

Test case 4: Single element (n=1)
Input Array: [Student(name=Jack, grade=75.0)]
Sorted Array: [Student(name=Jack, grade=75.0)]
Shifts: 0

Test case 5: Sorted grades (n=6)
Input Array: [Student(name=Kate, grade=70.0), Student(name=Liam, grade=75.0), Student(name=Mia, grade=80.0), Student(name=Noah, grade=85.0), Student(name=Olivia, grade=90.0), Student(name=Peter, grade=95.0)]
Sorted Array: [Student(name=Kate, grade=70.0), Student(name=Liam, grade=75.0), Student(name=Mia, grade=80.0), Student(name=Noah, grade=85.0), Student(name=Olivia, grade=90.0), Student(name=Peter, grade=95.0)]
Shifts: 0

Explanation:

  • Test case 1: Mixed grades require 6 shifts to sort by grade in ascending order.
  • Test case 2: Duplicate grades (all 90.0) require 0 shifts as order is preserved.
  • Test case 3: Empty array requires 0 shifts.
  • Test case 4: Single-element array requires 0 shifts.
  • Test case 5: Already sorted by grade, 0 shifts.

How It Works

  • Student Class:
    • Contains name (String) and grade (double).
    • Includes toString for readable output.
  • insertionSort:
    • Uses generics with Comparator<T> to sort any object type.
    • Inserts each element into the sorted portion, shifting elements where comparator indicates, counting shifts.
  • toString: Formats array as a string, handling Student objects.
  • Example Trace (Test case 1):
    • i=1: key=Bob(92.0), shift Alice(85.5): [Alice(85.5), Bob(92.0), Charlie(78.5), David(95.0), Eve(88.0)] (1 shift).
    • i=2: key=Charlie(78.5), shift Bob(92.0), Alice(85.5): [Charlie(78.5), Alice(85.5), Bob(92.0), David(95.0), Eve(88.0)] (2 shifts).
    • i=3: key=David(95.0), no shift: [Charlie(78.5), Alice(85.5), Bob(92.0), David(95.0), Eve(88.0)].
    • i=4: key=Eve(88.0), shift David(95.0), Bob(92.0): [Charlie(78.5), Alice(85.5), Eve(88.0), Bob(92.0), David(95.0)] (3 shifts).
    • Total shifts: 6.
  • Main Method: Tests mixed grades, duplicates, empty, single-element, and sorted arrays using a grade comparator.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
insertionSortO(n²) worst, O(n) bestO(1)
toStringO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n²) for insertionSort in worst/average cases; O(n) in best case (sorted); O(n) for toString.
  • Space complexity: O(1) for insertionSort (in-place); O(n) for toString (string builder).
  • Comparator comparisons depend on the field (e.g., double for grades), but complexity is O(n²) for comparisons.

✅ Tip: Use a Comparator to make Insertion Sort flexible for sorting objects by any field. Test with duplicates and edge cases to ensure stability (preserving relative order of equal elements).

⚠ Warning: Ensure the comparator is consistent to avoid sorting errors. Clone input arrays to preserve the original order for display.