Week 3: Arrays Part 2

Selection Sort

Selection sort finds the smallest element in the remaining array and swaps it with the element at the current position. The algorithm repeatedly selects the minimum from the unsorted portion. (Liang, Section 7.11)

How It Works

Algorithm Steps

1. Find the minimum element in the unsorted portion of the array.

2. Swap it with the first element of the unsorted portion.

3. Move the boundary of the sorted portion one element to the right.

4. Repeat until the entire array is sorted.

Time Complexity: O(n²) for all cases.

Implementation (Liang, Listing 7.8)

public static void selectionSort(double[] list) {
    for (int i = 0; i < list.length - 1; i++) {
        // Find the minimum in the list[i..list.length-1]
        double currentMin = list[i];
        int currentMinIndex = i;

        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < currentMin) {
                currentMin = list[j];
                currentMinIndex = j;
            }
        }

        // Swap list[i] with list[currentMinIndex] if necessary
        if (currentMinIndex != i) {
            list[currentMinIndex] = list[i];
            list[i] = currentMin;
        }
    }
}

Step-by-Step Trace

Sort the array: {4, 2, 7, 1, 5}

Pass	Array State	Min Found	Swap
1	[4, 2, 7, 1, 5]	1 at index 3	4 ↔ 1
2	[1, 2, 7, 4, 5]	2 at index 1	No swap
3	[1, 2, 7, 4, 5]	4 at index 3	7 ↔ 4
4	[1, 2, 4, 7, 5]	5 at index 4	7 ↔ 5
Result	[1, 2, 4, 5, 7]

Q1: How many comparisons does selection sort make for an array of n elements?

A) n

B) n(n-1)/2

C) n log n

D) n²

Selection sort makes (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons regardless of the input. (Liang, Section 7.11)

Trace the Code

double[] a = {3, 1, 2};
selectionSort(a);
System.out.println(a[0] + " " + a[1] + " " + a[2]);

What is the output?

Section Score

0 / 0

Insertion Sort

Insertion sort works the way you sort playing cards in your hand. It repeatedly takes the next element and inserts it into its correct position among the already sorted elements. (Liang, Section 7.12)

Implementation (Liang, Listing 7.9)

public static void insertionSort(double[] list) {
    for (int i = 1; i < list.length; i++) {
        // Insert list[i] into a sorted sublist list[0..i-1]
        double currentElement = list[i];
        int k;
        for (k = i - 1; k >= 0 && list[k] > currentElement; k--) {
            list[k + 1] = list[k];
        }
        // Insert the current element into list[k+1]
        list[k + 1] = currentElement;
    }
}

Step-by-Step Trace

Sort the array: {5, 2, 4, 1, 3}

Pass	Current	Shift	Result
1	2	5 shifts right	[2, 5, 4, 1, 3]
2	4	5 shifts right	[2, 4, 5, 1, 3]
3	1	5, 4, 2 shift right	[1, 2, 4, 5, 3]
4	3	5, 4 shift right	[1, 2, 3, 4, 5]

Selection Sort vs Insertion Sort

Selection sort: Always O(n²) comparisons, at most n swaps.

Insertion sort: Best case O(n) when nearly sorted, worst case O(n²). Generally more efficient for small or nearly sorted arrays. (Liang, Section 7.12)

Q1: What is the best-case time complexity of insertion sort?

A) O(n)

B) O(n²)

C) O(n log n)

D) O(1)

When the array is already sorted, insertion sort only makes n-1 comparisons and no shifts, giving O(n) time. (Liang, Section 7.12)

Q2: In insertion sort, the inner loop starts from index:

A) 0

B) i - 1 (going backward)

C) i + 1

D) list.length - 1

The inner loop starts at k = i - 1 and moves backward, shifting elements right until the correct position is found. (Liang, Section 7.12)

Section Score

0 / 0

Linear Search

The linear search approach compares the key element sequentially with each element in the array. It continues until a match is found or the entire array has been searched. (Liang, Section 7.9)

Implementation (Liang, Listing 7.6)

public static int linearSearch(int[] list, int key) {
    for (int i = 0; i < list.length; i++) {
        if (key == list[i])
            return i;
    }
    return -1;
}

Key Points

Time Complexity: O(n) in worst/average case, O(1) in best case.

No sorting required: Works on unsorted arrays.

Returns -1 if the key is not found. (Liang, Section 7.9)

Q1: What does linearSearch return if the key is not in the array?

A) 0

B) -1

C) null

D) ArrayIndexOutOfBoundsException

By convention, search methods return -1 to indicate the key was not found. (Liang, Section 7.9)

Trace the Code

int[] arr = {3, 7, 1, 9, 5};
System.out.println(linearSearch(arr, 9));

What is the output?

Section Score

0 / 0

Binary Search

Binary search is more efficient than linear search, but it requires the array to be sorted. It compares the key with the middle element and eliminates half the array in each step. (Liang, Section 7.10)

Implementation (Liang, Listing 7.7)

public static int binarySearch(int[] list, int key) {
    int low = 0;
    int high = list.length - 1;

    while (high >= low) {
        int mid = (low + high) / 2;
        if (key < list[mid])
            high = mid - 1;
        else if (key == list[mid])
            return mid;
        else
            low = mid + 1;
    }

    return -low - 1;  // key not found
}

Step-by-Step Trace

Search for key 7 in sorted array: {1, 3, 5, 7, 9, 11, 13}

Step	low	high	mid	list[mid]	Action
1	0	6	3	7	key == list[mid], return 3

Search for key 4 in: {1, 3, 5, 7, 9, 11, 13}

Step	low	high	mid	list[mid]	Action
1	0	6	3	7	4 < 7, high = 2
2	0	2	1	3	4 > 3, low = 2
3	2	2	2	5	4 < 5, high = 1
4	high < low, return -3 (not found)

Efficiency

Time Complexity: O(log n) — each comparison eliminates half the remaining elements.

Prerequisite: The array must be sorted before using binary search. (Liang, Section 7.10)

Q1: What is the maximum number of comparisons for binary search on an array of 1024 elements?

A) 1024

B) 512

C) 11

D) 10

Binary search needs at most log₂(1024) + 1 = 11 comparisons. Each step halves the search space. (Liang, Section 7.10)

Q2: What must be true about the array before using binary search?

A) It must have an even number of elements

B) It must be sorted

C) It must contain no duplicates

D) It must be of type int

Binary search requires the array to be pre-sorted. Without sorting, the halving logic does not work correctly. (Liang, Section 7.10)

Section Score

0 / 0

The java.util.Arrays Class

The java.util.Arrays class contains various static methods for manipulating arrays (such as sorting and searching). These methods are convenient shortcuts. (Liang, Section 7.13)

Useful Methods

Method	Description
`Arrays.sort(arr)`	Sorts the array in ascending order
`Arrays.sort(arr, from, to)`	Sorts elements from index `from` to `to-1`
`Arrays.binarySearch(arr, key)`	Searches sorted array for key (returns index or negative)
`Arrays.equals(arr1, arr2)`	Returns true if arrays have same contents
`Arrays.fill(arr, val)`	Fills entire array with the given value
`Arrays.toString(arr)`	Returns a string representation like [1, 2, 3]
`Arrays.copyOf(arr, len)`	Copies array into new array of given length

Examples

import java.util.Arrays;

int[] numbers = {5, 2, 8, 1, 9};

// Sort
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers)); // [1, 2, 5, 8, 9]

// Binary Search (array must be sorted first)
int index = Arrays.binarySearch(numbers, 5);
System.out.println("5 is at index " + index); // 5 is at index 2

// Fill
int[] zeros = new int[5];
Arrays.fill(zeros, 7);
System.out.println(Arrays.toString(zeros)); // [7, 7, 7, 7, 7]

// Equals
int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
System.out.println(Arrays.equals(a, b)); // true

Q1: What does Arrays.toString(new int[]{3, 1, 2}) return?

A) "[3, 1, 2]"

B) "312"

C) "[I@15db9742"

D) "{3, 1, 2}"

Arrays.toString() returns a formatted string with brackets and commas: [3, 1, 2]. Without it, printing an array gives a hash code like [I@15db9742. (Liang, Section 7.13)

Q2: What happens if you call Arrays.binarySearch() on an unsorted array?

A) It sorts the array first, then searches

B) Throws an exception

C) The result is unpredictable

D) Always returns -1

The behavior is undefined if the array is not sorted. The method assumes sorted order and may return incorrect results. (Liang, Section 7.13)

Section Score

0 / 0

Command-Line Arguments

The main method's parameter String[] args receives arguments passed from the command line. (Liang, Section 7.14)

Example (Liang, Listing 7.10)

public class Calculator {
    public static void main(String[] args) {
        // java Calculator 2 + 3
        int result = 0;
        int num1 = Integer.parseInt(args[0]);
        int num2 = Integer.parseInt(args[2]);

        switch (args[1].charAt(0)) {
            case '+': result = num1 + num2; break;
            case '-': result = num1 - num2; break;
            case '.': result = num1 * num2; break;
            case '/': result = num1 / num2; break;
        }
        System.out.println(num1 + " " + args[1] + " " + num2 + " = " + result);
    }
}

Running with Arguments

java Calculator 2 + 3 produces: 2 + 3 = 5

Note: args[0] is "2", args[1] is "+", args[2] is "3". All are Strings and must be parsed for numeric operations. (Liang, Section 7.14)

Q1: If you run java Test one two three, what is args.length?

A) 4

B) 3

C) 0

D) 1

The three arguments "one", "two", "three" are stored in args[0], args[1], args[2]. The class name is not included. (Liang, Section 7.14)

Section Score

0 / 0