← Back to course
Python 11-12 / Week 12 / Tuesday
2/6
Week 12 · Reading Java II and Ship

Tuesday

Algorithms in Java
// ArrayList, sorting, searching and recursion in Java; then a code review and the FieldSim release
⏱ about 30 min

Tuesday: Algorithms in Java

Wren lays the week 9 trace tables for selection sort on the bench. "Same five weights," he says. "What does the evidence say about the Java version?"

Nova projects SortDemo.java and SearchDemo.java beside sorts.py and search.py. "How can I help?" she asks. "The steps are the same. Only the spelling changes."

Comet hunts for the swap. "Python swaps in one line. Java uses a temp variable and three lines."

Wren nods. "Then the passes should match ours exactly. Let us check."

Comet hands you the trace table. "Lead programmer, prove it."

Selection sort in Java

Selection sort repeatedly picks the smallest item left and swaps it into its final place.

SortDemo sorts a Java int array. An array has a fixed length, and .length gives its size.

// SortDemo.java
// Selection sort on an int array, like selection_sort in sorts.py.
import java.util.Arrays;

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

    public static void main(String[] args) {
        int[] grams = {42, 18, 65, 7, 30};
        selectionSort(grams);
        System.out.println(Arrays.toString(grams));
    }
}

This Python copy of selection_sort prints the list after each pass, so you can check the Java trace against a run:

# trace_select.py (a copy of selection_sort that prints each pass)
def selection_sort(nums):
    for i in range(len(nums) - 1):
        smallest = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[smallest]:
                smallest = j
        nums[i], nums[smallest] = nums[smallest], nums[i]
        print(f"after pass {i}: {nums}")


grams = [42, 18, 65, 7, 30]
selection_sort(grams)
after pass 0: [7, 18, 65, 42, 30]
after pass 1: [7, 18, 65, 42, 30]
after pass 2: [7, 18, 30, 42, 65]
after pass 3: [7, 18, 30, 42, 65]
Python (sorts.py)Java (SortDemo.java)
for i in range(len(nums) - 1):for (int i = 0; i < nums.length - 1; i++) {
smallest = iint smallest = i;
nums[i], nums[smallest] = nums[smallest], nums[i]int temp = nums[i]; then two more lines
TRACE THE JAVA SORT
  • Read the question.
  • Tap your answer.
In the first pass (i is 0), which value is swapped into place?
In SortDemo, what does temp hold just after int temp = nums[i]; in that first pass?
Which of these passes leaves the list unchanged?

Binary search in Java

// SearchDemo.java
// Binary search on a sorted int array, like binary_search in search.py.
public class SearchDemo {
    public static int binarySearch(int[] items, int target) {
        int low = 0;
        int high = items.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (items[mid] == target) {
                return mid;
            } else if (items[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] sorted = {7, 12, 18, 25, 30, 39, 42, 51, 65, 88};
        System.out.println(binarySearch(sorted, 39));
        System.out.println(binarySearch(sorted, 40));
    }
}

Binary search needs sorted data. It starts in the middle and removes half of what is left each step.

In Java, (low + high) / 2 with two ints works like Python's //. Last week, 7 / 2 with two ints gave 3.

TRACE THE JAVA SEARCH
  • Read the question.
  • Tap your answer.
binarySearch(sorted, 39): what is mid on the first check?
What does SearchDemo print for 40?
5
-1
At your computer
1. Type algo_twin.py in your fieldsim folder. It uses your sorts.py and search.py.
2. Run it and compare with the SortDemo and SearchDemo output.
3. Change the search for 39 to a search for 88. Predict the index, then run it.
4. Now replace the two lines selection_sort(grams) and print(grams) with one line, print(selection_sort(grams)). Run it and read the result calmly.
5. Put the two lines back and run it again.
# algo_twin.py
# The Python twin of SortDemo.java and SearchDemo.java.
from sorts import selection_sort
from search import binary_search

grams = [42, 18, 65, 7, 30]
selection_sort(grams)
print(grams)
sorted_grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
print(binary_search(sorted_grams, 39))
print(binary_search(sorted_grams, 40))
# algo_twin.py
# The Python twin of SortDemo.java and SearchDemo.java.
from sorts import selection_sort
from search import binary_search

grams = [42, 18, 65, 7, 30]
print(selection_sort(grams))
sorted_grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
print(binary_search(sorted_grams, 88))
print(binary_search(sorted_grams, 40))

With that change, the run shows:

None
9
-1
READ THE SURPRISE
  • Read the question.
  • Tap your answer.
Why does the first line say None?

Same trace, new syntax, lead programmer. Tomorrow FieldSim ships.

← Monday