Chapter 5 · Real programs
Practice: searching and sorting
Step 1 of 21 · Concept
Look at each one in turn
This lesson is practice: the classic searches and sorts, written by hand.
Linear search looks at each element in turn, until it finds the one it wants. It returns that index, or -1
when there is none. -1 can never be an index.
Step 2 of 21 · Quiz
What will it print?
indexOf(values, target) is a linear search. Type exactly what this prints.
int[] values = {7, 3, 9, 4, 9};
System.out.println(indexOf(values, 9));
System.out.println(indexOf(values, 5));
Step 3 of 21 · Demo
See it run
Run it and compare with your answer. return i leaves the method, and its loop, at the first match.
Step 4 of 21 · Concept
A sorted array halves the work
A linear search of a million elements may look at a million of them. When the array is sorted, there is a much faster way, binary search:
- Look at the middle element. If it is the target, you are done.
- If the target is bigger, it can only be in the right half. If smaller, in the left half.
- Repeat with that half.
Each look halves what is left: a million elements take at most 20 looks.
Step 5 of 21 · Trace
Watch binary search halve
low and high are the first and last place the target can still be. Press Next to follow a search for 23.
static int binarySearch(int[] a, int target) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
return mid;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}midis (0 + 9) / 2 = 4.a[4]is 16, less than 23, so line 9 is next.lowis now 5. The newmidis 7, and 56 is more than 23: line 11 is next.highis now 6.midis (5 + 6) / 2 = 5, anda[5]is 23: found.- The method returns 5 after three looks, and its frame is gone.
Step 6 of 21 · Quiz
Which way next?
A binary search for 23 looks at the middle, and finds 56. What changes?
static int binarySearch(int[] a, int target) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
return mid;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}Step 7 of 21 · Exercise
Your turn: binary search
Write binarySearch with a while (low <= high) loop, as in the trace.
Print each value it looks at, then a space, with System.out.print. Return the index of target, or -1. The
output must be exactly:
16 56 23 -> 5
16 5 2 -> 0
16 56 72 91 -> 9
16 5 8 -> -1
Each round starts with int mid = (low + high) / 2; and prints sorted[mid] + " ".
Then three cases: equal returns mid; smaller sets low = mid + 1; bigger sets high = mid - 1.
while (low <= high) {
int mid = (low + high) / 2;
System.out.print(sorted[mid] + " ");
if (sorted[mid] == target) {
return mid;
} else if (sorted[mid] < target) {
Step 8 of 21 · Trace
Swap two cells
To swap two cells you need a third box, tmp. Without it, a[0] = a[1] would lose the 5. Press Next.
int[] a = {5, 1};
int tmp = a[0];
a[0] = a[1];
a[1] = tmp;aholds a reference to the array{5, 1}on the heap. Line 2 is next.tmpis a new box inmain's frame. It holds a copy ofa[0]: 5.a[0]now holds 1. The 5 is safe intmp.a[1]gets the 5 fromtmp. The two cells are swapped.
Step 9 of 21 · Quiz
Without tmp
a is {5, 1}. Someone swaps without tmp:
a[0] = a[1];
a[1] = a[0];
What does a hold now?
Step 10 of 21 · Concept
Bubble sort
Bubble sort compares neighbours from left to right, and swaps two that are in the wrong order. One walk along the array is a pass.
After one pass, the biggest value has "bubbled" to the end. The next pass can stop one place earlier.
Step 11 of 21 · Quiz
After pass 2
After pass 1, the array is [1, 4, 2, 5, 8]. What is it after pass 2?
Step 12 of 21 · Demo
See bubble sort run
Run it. It prints the array after each pass. The method changes main's array itself (lesson 10), so it returns
nothing.
Step 13 of 21 · Concept
Selection sort
Selection sort fills the array from the front. For each place i, from the first:
- find the smallest value from
ito the end, - swap it into place
i.
After pass i, the first i + 1 places hold the smallest values, in order.
Step 14 of 21 · Exercise
Your turn: selection sort
Write selectionSort. For each i from 0 to a.length - 2:
- find the index of the smallest value from
ito the end, - swap that value with
a[i], - print the array.
The output must be exactly:
[10, 29, 14, 37, 13]
[10, 13, 14, 37, 29]
[10, 13, 14, 37, 29]
[10, 13, 14, 29, 37]
Two loops: the outer one for the place i, the inner one to look from i + 1 to the end.
Keep the index of the smallest so far in int min = i;. After the inner loop, swap a[i] and a[min] with tmp.
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
Step 15 of 21 · Concept
Real code calls the library
Both sorts compare every pair once: n × (n − 1) / 2 comparisons for n values. For 5 values that is 10. For a million, it is about 500 billion.
Java's library sorts a million values with about 20 million comparisons. Real code calls it:
| you write | it does |
|---|---|
Arrays.sort(a) | sorts an array |
Collections.sort(list) | sorts a list |
Arrays.binarySearch(a, x) | the index of x in a sorted array; negative if missing |
You wrote them by hand to see how they work. The same loops, comparisons and swaps solve many other problems.
Step 16 of 21 · Exercise
Your turn: count with a map
Write two methods:
count: how often each word occurs, in aHashMap, withgetOrDefault(lesson 13);mostCommon: the word with the biggest count.
main copies the counts into a TreeMap, which keeps its keys in alphabetical order. The output must be exactly:
{and=2, bird=1, cat=1, dog=1, the=3}
Most common: the
counts.getOrDefault(w, 0) is the count so far, or 0 for a new word. Put back that number plus 1.
For mostCommon, loop over counts.keySet() and keep the best word and its count so far.
for (String w : words) {
counts.put(w, counts.getOrDefault(w, 0) + 1);
}
Step 17 of 21 · Exercise
Your turn: reverse the words
Write reverseWords: the words of the sentence in the opposite order. Put one space between them, and none at the
end.
Cut the sentence with split(" ") (lesson 19). Then walk the array from its last index down to 0. The output must be
exactly:
browser the in runs Java
one
c b a
Start the result with the last word, words[words.length - 1]. Then add " " and each word before it.
Count down with for (int i = words.length - 2; i >= 0; i--). i-- takes 1 away from i, as i++ adds 1.
String result = words[words.length - 1];
for (int i = words.length - 2; i >= 0; i--) {
result += " " + words[i];
}
Step 18 of 21 · Exercise
Your turn: a palindrome check
A palindrome reads the same both ways, like level. Capitals count as small letters.
Write isPalindrome with two indices: i from the start, j from the end. Compare charAt(i) with charAt(j),
and move both towards the middle. The output must be exactly:
level: true
Racecar: true
java: false
abba: true
a: true
First make the word small letters with toLowerCase() (lesson 9), so R and r match.
Loop while (i < j). Two different characters mean return false. After the loop, return true.
int i = 0;
int j = w.length() - 1;
while (i < j) {
if (w.charAt(i) != w.charAt(j)) {
return false;
}
i++;
j--;
}
Step 19 of 21 · Check yourself
Check yourself: a small dictionary
Write sort by hand (either sort of this lesson) and find as a binary search, both on Strings.
Compare two texts with a.compareTo(b): it is negative when a comes first in the alphabet (lesson 17). The output
must be exactly:
[apple, banana, cherry, fig, kiwi, pear]
kiwi: 4
mango: -1
apple: 0
Start from your selection sort and your binary search. Each < or == between two texts becomes a compareTo.
Step 20 of 21 · Challenge · optional
Challenge: stop when it is sorted
Optional. It earns the lesson's third star.
This bubble sort makes four passes, but its last two change nothing. Make it stop after the first pass that swaps nothing, and return the number of passes. The output must be exactly:
[1, 4, 2, 5, 8]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8]
Passes: 3
Use a boolean swapped, a flag. Set it to false before a pass, and to true whenever the pass swaps.
Repeat the passes while (swapped) instead of with the outer for. Start with swapped = true, so the first pass runs.
Step 21 of 21 · Recap
Recap
- A linear search looks at each element in turn. It works on any array.
- A binary search halves a sorted array at each look, with
low,midandhigh. - A swap needs a third box:
tmpkeeps one value safe. - Bubble sort swaps neighbours; selection sort picks the smallest for each place.
- Real code calls
Arrays.sort,Collections.sortandArrays.binarySearch.
Next: lesson 21 puts the course together in one project of your own.
Review
4 questions from this lesson, in a new order each time. Answer from memory: 3 of 4 right on the first try passes. On a day after you finish the lesson, a pass earns 15 XP.
The review needs JavaScript.
public class Search {
static int indexOf(int[] values, int target) {
for (int i = 0; i < values.length; i++) {
if (values[i] == target) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] values = {7, 3, 9, 4, 9};
System.out.println(indexOf(values, 9));
System.out.println(indexOf(values, 5));
}
}
public class Binary {
static int binarySearch(int[] sorted, int target) {
int low = 0;
int high = sorted.length - 1;
return -1;
}
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
System.out.println("-> " + binarySearch(a, 23));
System.out.println("-> " + binarySearch(a, 2));
System.out.println("-> " + binarySearch(a, 91));
System.out.println("-> " + binarySearch(a, 7));
}
}
import java.util.Arrays;
public class Bubble {
static void bubbleSort(int[] a) {
for (int pass = 0; pass < a.length - 1; pass++) {
for (int i = 0; i < a.length - 1 - pass; i++) {
if (a[i] > a[i + 1]) {
int tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
}
}
System.out.println(Arrays.toString(a));
}
}
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 8};
bubbleSort(a);
}
}
import java.util.Arrays;
public class Selection {
static void selectionSort(int[] a) {
}
public static void main(String[] args) {
int[] a = {29, 10, 14, 37, 13};
selectionSort(a);
}
}
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class Count {
static Map<String, Integer> count(String[] words) {
Map<String, Integer> counts = new HashMap<>();
return counts;
}
static String mostCommon(Map<String, Integer> counts) {
return "";
}
public static void main(String[] args) {
String text = "the cat and the dog and the bird";
String[] words = text.split(" ");
Map<String, Integer> counts = count(words);
System.out.println(new TreeMap<>(counts));
String top = mostCommon(counts);
System.out.println("Most common: " + top);
}
}
public class Reverse {
static String reverseWords(String sentence) {
return sentence;
}
public static void main(String[] args) {
String[] tests = {
"Java runs in the browser", "one", "a b c"
};
for (String t : tests) {
System.out.println(reverseWords(t));
}
}
}
public class Palindrome {
static boolean isPalindrome(String word) {
return false;
}
public static void main(String[] args) {
String[] words = {
"level", "Racecar", "java", "abba", "a"
};
for (String w : words) {
System.out.println(w + ": " + isPalindrome(w));
}
}
}
import java.util.Arrays;
public class Dictionary {
// sorts the words alphabetically, by hand
static void sort(String[] words) {
}
// a binary search: word's index, or -1
static int find(String[] sorted, String word) {
return -1;
}
public static void main(String[] args) {
String[] words = {
"pear", "apple", "fig", "kiwi", "banana", "cherry"
};
sort(words);
System.out.println(Arrays.toString(words));
System.out.println("kiwi: " + find(words, "kiwi"));
System.out.println("mango: " + find(words, "mango"));
System.out.println("apple: " + find(words, "apple"));
}
}
import java.util.Arrays;
public class BubbleStop {
static int bubbleSort(int[] a) {
int passes = 0;
for (int pass = 0; pass < a.length - 1; pass++) {
for (int i = 0; i < a.length - 1 - pass; i++) {
if (a[i] > a[i + 1]) {
int tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
}
}
passes++;
System.out.println(Arrays.toString(a));
}
return passes;
}
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 8};
System.out.println("Passes: " + bubbleSort(a));
}
}