Sorting in Java: Selection Sort for Integers and Employee Objects (Lab 9 Guide)

Introduction to Sorting in Java

Sorting is a fundamental concept in programming that organizes data in a specific order. In this tutorial, you will learn how to implement the selection sort algorithm for both primitive integers and custom Employee objects. This guide aligns with the ICS 141 Lab 9 assignment, helping you understand sorting mechanics and the Comparable interface. Whether you're preparing for exams or building real-world applications, mastering sorting is essential for efficient data handling.

What is Selection Sort?

Selection sort works by repeatedly finding the minimum (or maximum) element from the unsorted part and moving it to the beginning. It has a time complexity of O(n²), making it suitable for small datasets. The algorithm divides the array into a sorted and an unsorted region. Each iteration selects the smallest element from the unsorted region and swaps it with the first element of the unsorted region.

Part 1: Sorting an Array of Integers

Step 1: Create the SortingDriver Class

Start by creating a new Java class named SortingDriver with a main method. This class will contain the selection sort methods and demonstrate sorting an integer array.

public class SortingDriver {
    public static void main(String[] args) {
        // Your code here
    }
}

Step 2: Implement Selection Sort (Ascending)

Copy the selectionSort method from your lecture slides. It should accept an int[] array and sort it in ascending order.

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Step 3: Main Method Logic

In the main method, declare and initialize an unsorted integer array. Then print it, sort it, and print again.

int[] myNumbers = {45, 12, 89, 3, 67, 24};

// Print original array
for (int num : myNumbers) {
    System.out.print(num + "\t");
}
System.out.println();

selectionSort(myNumbers);

// Print sorted array
for (int num : myNumbers) {
    System.out.print(num + "\t");
}

Step 4: Descending Order Selection Sort

Copy the selectionSort method and rename it to selectionSortDescending. Modify the comparison to find the maximum element instead of the minimum.

public static void selectionSortDescending(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int maxIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j;
            }
        }
        int temp = arr[maxIndex];
        arr[maxIndex] = arr[i];
        arr[i] = temp;
    }
}

Call this method in main after resetting the array to its original order or creating a new array. This demonstrates sorting in descending order.

Part 2: Sorting an Array of Employee Objects

Step 1: Create the Employee Class with Comparable

Implement the Comparable interface to enable sorting. The compareTo method should compare employees by name first, then by hours if names are equal.

public class Employee implements Comparable<Employee> {
    private String name;
    private int hours;

    // Constructor, getters, setters

    @Override
    public int compareTo(Employee other) {
        int nameCompare = this.name.compareTo(other.name);
        if (nameCompare != 0) {
            return nameCompare;
        }
        return Integer.compare(this.hours, other.hours);
    }
}

Step 2: Create ObjectSortingDriver

Create a new class ObjectSortingDriver with a main method. Copy the selectionSort method and adapt it to work with Employee[] using compareTo.

public static void selectionSort(Employee[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j].compareTo(arr[minIndex]) < 0) {
                minIndex = j;
            }
        }
        Employee temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Step 3: Test the Sorting

In the main method, create an array of 6 Employee objects with various names and hours. Print the array before and after sorting.

Employee[] employees = new Employee[6];
employees[0] = new Employee("Alice", 40);
employees[1] = new Employee("Bob", 35);
employees[2] = new Employee("Charlie", 40);
employees[3] = new Employee("Alice", 30);
employees[4] = new Employee("David", 45);
employees[5] = new Employee("Eve", 38);

// Print original
for (Employee e : employees) {
    System.out.println(e.getName() + " " + e.getHours());
}

selectionSort(employees);

// Print sorted
System.out.println("After sorting:");
for (Employee e : employees) {
    System.out.println(e.getName() + " " + e.getHours());
}

Real-World Analogy: Sorting a Music Playlist

Imagine you have a playlist of songs, each with a title and duration. Sorting by title (alphabetically) and then by duration (shortest first) is similar to sorting Employees by name and hours. This is how streaming apps like Spotify organize your library.

Common Mistakes and Tips

• Off-by-one errors: Ensure your loops cover the entire array correctly.
• Forgetting to implement Comparable: The compareTo method is required for object sorting.
• Not resetting the array: When testing descending order, use a fresh copy of the original array.
• Using == for string comparison: Always use equals() or compareTo() for strings.

Conclusion

You have now implemented selection sort for integers and Employee objects. This lab reinforces your understanding of sorting algorithms, the Comparable interface, and method overloading. Practice by sorting other types like strings or custom objects. Sorting is a key skill for coding interviews and real-world applications, from organizing student records to ranking gaming leaderboards.