Sorting and Binary Search

Selection sort splits the array into a sorted part on the left, which starts empty, and an unsorted part on the right. Each pass scans the unsorted part for its smallest value and swaps it into the first unsorted slot, so the sorted part grows by one element per pass. After pass 1 the smallest value is at index 0 and never moves again; after pass 2 the second smallest is at index 1, and so on. With n elements you need n − 1 passes, because once all but one element are in place the last one has nowhere else to go. Notice that the swap is the same three-line save, copy over, restore you already know.

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;                       // assume the first unsorted slot is smallest
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;                   // remember WHERE the smaller value is
            }
        }
        int temp = arr[i];                      // swap it into position i
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Bubble sort works only with neighbours. Each pass walks along the array comparing arr[j] with arr[j + 1] and swaps them whenever they are out of order. The largest value gets carried along like a bubble rising and lands in the last slot at the end of pass 1, so each later pass can stop one element earlier — that is what the - pass in the inner loop bound does. Bubble sort has one genuine advantage: if a whole pass makes no swaps, every neighbour pair is already in order, so the array is sorted and the method can stop early. On nearly sorted data that early exit can save almost all of the work. Selection sort has no such test; it always performs every pass, even on an array that was sorted to begin with.

public static void bubbleSort(int[] arr) {
    for (int pass = 0; pass < arr.length - 1; pass++) {
        boolean swapped = false;
        for (int j = 0; j < arr.length - 1 - pass; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;               // a pass with no swaps means it is sorted
        }
    }
}

Both sort methods return void, yet after selectionSort(scores); the caller's scores array is sorted. That seems to contradict what you learned about parameters, so look closely. Java always passes arguments by value: the method receives a copy of whatever the variable holds. For an int the variable holds the number itself, so the method gets its own copy of the number and changing it does nothing outside. An array variable, however, does not hold the elements. It holds a reference — the address of the one array object in memory. Copying the reference gives the method a second arrow pointing at the same array, so arr[0] = 5 inside the method writes into the caller's array. What the method cannot do is make the caller's variable point at a different array: assigning arr = new int[3] just swings the method's own copy of the arrow.

public static void resetToZero(int n) {
    n = 0;                       // changes the method's own copy
}

public static void replace(int[] arr) {
    arr = new int[] {0, 0, 0};   // points the local copy somewhere new
}

public static void main(String[] args) {
    int count = 6;
    int[] scores = {29, 10, 14, 37, 13, 5};

    resetToZero(count);
    selectionSort(scores);       // writes through the shared reference
    replace(scores);

    System.out.println(count);       // 6
    System.out.println(scores[0]);   // 5
}

Binary search keeps two markers, low and high, around the part of a sorted array that could still contain the target. It checks the middle element. If that is the target, it is done. If the middle value is too small, the target can only be to the right, so low moves to mid + 1; if it is too large, high moves to mid - 1. Either way, half of the remaining elements are discarded with one comparison. When low passes high the range is empty and the target is not there, so the method returns −1. Because mid = (low + high) / 2 uses integer division, the middle of an even-sized range rounds down. The halving is what makes it so fast. The worst case is the number of halvings needed to shrink the range to one element, plus one last check: floor(log₂ n) + 1. That is 4 checks for 10 elements, 7 for 100, 10 for 1,000 and only 20 for 1,000,000, where a linear search could need all million — and doubling the data adds just one more check. One warning before you use it: the whole method rests on the assumption that everything left of mid is smaller and everything right of mid is larger. On an unsorted array that is false, so binary search can discard the half that holds the target and confidently return −1 for a value that is present — and Java will not warn you. Sort first or search linearly, and remember that sorting costs time too, so it pays off when you search the same data many times.

public static int binarySearch(int[] data, int target) {
    int low = 0;
    int high = data.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (data[mid] == target) {
            return mid;
        } else if (data[mid] < target) {
            low = mid + 1;           // target is in the right half
        } else {
            high = mid - 1;          // target is in the left half
        }
    }
    return -1;                       // range is empty: not found
}