7.6 Sorting

Imagine your music playlist, book collection, or a list of high scores - wouldn't it be nice if they were organized? That's what sorting is all about! In Java, we often need to arrange the elements in arrays and ArrayLists in a specific order (like alphabetically or numerically). This guide covers how sorting algorithms work and how to implement them in Java using iteration (loops) and selection (if-statements).

What is Sorting?

Sorting is the process of arranging elements in a specific order. Think of it like organizing books on a shelf - you might arrange them:

• Alphabetically by title
• By author's last name
• By publication date
• By height or color

Arrays vs ArrayLists

Before we dive into sorting, let's clarify what we're sorting:

• Array: A fixed-size collection of elements of the same type (like int[] or String[]). Arrays have a predetermined size that can't change after creation.

• ArrayList: A dynamic-sized collection from Java's built-in library that can grow and shrink as needed. An ArrayList stores objects (not primitives directly) and provides helpful methods for managing data. You need to import it with: import java.util.ArrayList;

In Java, we commonly sort both arrays and ArrayLists to:

• Make information easier to read and understand
• Help find things faster (some search algorithms only work on sorted data)
• Prepare data for further processing

Types of Sorting Algorithms

In this unit, we focus on two main sorting algorithms:

Selection Sort

Selection sort works like this:

1. Find the smallest value in the unsorted portion
2. Swap it with the element at the beginning of the unsorted portion
3. Move the boundary between sorted and unsorted portions one element to the right
4. Repeat until all elements are sorted

Selection Sort in Java for Arrays

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        // Find the minimum element in the unsorted portion
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap the found minimum element with the first element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Selection Sort in Java for ArrayLists

public static void selectionSort(ArrayList<Integer> list) {
    for (int i = 0; i < list.size() - 1; i++) {
        // Find the minimum element in the unsorted portion
        int minIndex = i;
        for (int j = i + 1; j < list.size(); j++) {
            if (list.get(j) < list.get(minIndex)) {
                minIndex = j;
            }
        }
        
        // Swap the found minimum element with the first element
        int temp = list.get(minIndex);
        list.set(minIndex, list.get(i));
        list.set(i, temp);
    }
}

Visual Example of Selection Sort

Consider sorting [5, 3, 8, 1, 2]:

1. Find smallest (1) and swap with first element: [1, 3, 8, 5, 2]
2. Find smallest in remaining elements (2) and swap with second element: [1, 2, 8, 5, 3]
3. Find smallest in remaining elements (3) and swap with third element: [1, 2, 3, 5, 8]
4. Find smallest in remaining elements (5) and swap with fourth element: [1, 2, 3, 5, 8]
5. Only one element remains, so we're done!

Insertion Sort

Insertion sort works like this:

1. Start with the second element
2. Compare it with the elements before it and insert it into its correct position
3. Move to the next element and repeat
4. Continue until the entire array is sorted

Think of it like sorting cards in your hand as you pick them up!

Insertion Sort in Java for Arrays

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int currentElement = arr[i];
        int j = i - 1;
        
        // Move elements that are greater than currentElement
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > currentElement) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = currentElement;
    }
}

Insertion Sort in Java for ArrayLists

public static void insertionSort(ArrayList<Integer> list) {
    for (int i = 1; i < list.size(); i++) {
        int currentElement = list.get(i);
        int j = i - 1;
        
        // Move elements that are greater than currentElement
        // to one position ahead of their current position
        while (j >= 0 && list.get(j) > currentElement) {
            list.set(j + 1, list.get(j));
            j--;
        }
        list.set(j + 1, currentElement);
    }
}

Visual Example of Insertion Sort

Consider sorting [5, 3, 8, 1, 2]:

1. Start with [5] as sorted and 3 as current element
2. Insert 3 before 5: [3, 5, 8, 1, 2]
3. Keep 8 where it is (already in right position): [3, 5, 8, 1, 2]
4. Insert 1 at beginning: [1, 3, 5, 8, 2]
5. Insert 2 between 1 and 3: [1, 2, 3, 5, 8]
6. Done!

Using Built-in Sorting Methods

Java provides built-in methods to sort arrays and ArrayLists:

For Arrays

import java.util.Arrays;

// Sorting an array of primitives
int[] numbers = {5, 3, 8, 1, 2};
Arrays.sort(numbers);  // Now numbers = [1, 2, 3, 5, 8]

// Sorting an array of objects
String[] names = {"Charlie", "Alice", "Bob"};
Arrays.sort(names);  // Now names = ["Alice", "Bob", "Charlie"]

For ArrayLists

import java.util.Collections;
import java.util.ArrayList;

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(3);
numbers.add(8);
numbers.add(1);
numbers.add(2);

Collections.sort(numbers);  // Now numbers = [1, 2, 3, 5, 8]

Sorting Objects

When sorting custom objects, Java needs to know how to compare them. There are two ways to do this:

1. Make your class implement the Comparable interface

public class Student implements Comparable<Student> {
    private String name;
    private double gpa;
    
    // Constructor and other methods...
    
    @Override
    public int compareTo(Student other) {
        // Sort by GPA (highest first)
        return Double.compare(other.gpa, this.gpa);
    }
}

// Now you can sort students
ArrayList<Student> students = new ArrayList<>();
// ... add students to the list
Collections.sort(students);  // Sorts by GPA (highest first)

2. Create a separate Comparator

import java.util.Comparator;

// Sort by name
class NameComparator implements Comparator<Student> {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.getName().compareTo(s2.getName());
    }
}

// Now you can sort using this comparator
Collections.sort(students, new NameComparator());  // Sorts alphabetically by name

Measuring Sorting Efficiency

How do we know which sorting algorithm is better? We measure:

Time Complexity

We use statement execution counts to measure how many steps a sorting algorithm takes. This is an informal way to understand efficiency.

Space Complexity

This measures how much extra memory the algorithm uses:

• Both selection and insertion sort use O(1) space - only a few extra variables regardless of list size

• Some other algorithms (not covered here) use more space

When to Use Which Algorithm

• Selection Sort: Simple cases where code simplicity is more important than speed
• Insertion Sort: When data is already mostly sorted or for small datasets
• Built-in Methods: For most real-world applications (they use more advanced algorithms)

Common Mistakes to Avoid

• Off-by-one errors: Be careful with array indices and loop conditions
• Modifying a collection while sorting: Avoid adding/removing elements during sorting
• Comparing objects incorrectly: Make sure compareTo() or compare() methods are correctly implemented
• Forgetting that sorting modifies the original collection: If you need to preserve the original order, make a copy first

Summary

Sorting is a fundamental operation that helps us organize data in a useful way. While selection sort and insertion sort might not be the fastest algorithms out there, understanding how they work builds a foundation for learning more complex sorting techniques. Remember, Java's built-in sorting methods are usually the best choice for real applications, but knowing how sorting works "under the hood" is valuable for any programmer. Now you're ready to keep your data nice and organized!