4.14-4.15 Searching and sortingLinear search, selection sort and insertion sort

Linear search
Linear search checks the elements one at a time, in order, until it finds the target or runs out. It returns the index where it found the target, or -1 if the target isn't there. It works on any data, sorted or not, and the same idea works on arrays, ArrayLists and 2D arrays (search each row in turn).
1public static int indexOf(int[] a, int target)2{3 for (int i = 0; i < a.length; i++)4 {5 if (a[i] == target)6 {7 return i;18 }9 }10 return -1;211}1213public static int find(ArrayList<String> list, String name)14{15 for (int i = 0; i < list.size(); i++)16 {17 if (list.get(i).equals(name))318 {19 return i;20 }21 }22 return -1;23}2425public static boolean contains(int[][] g, int target)26{427 for (int[] row : g)28 {429 for (int v : row)30 {31 if (v == target)32 {33 return true;34 }35 }36 }37 return false;38}
- line 7 Found: stop and report where
- line 10 Not found, only after checking every element
- line 17 Objects: equals. "bea" does not match "Bea"
- line 26-28 A 2D search is a 1D search on every row
?Wait, why equals for the Strings but == for the ints?
I thought about it. Show me
Selection sort
Selection sort builds the sorted part from the front. On each pass it scans the unsorted part for the smallest value, then swaps it into the first unsorted spot. After pass i, positions 0 through i hold their final values. An array of n elements needs n - 1 passes.
1public static void selectionSort(int[] a)2{3 for (int i = 0; i < a.length - 1; i++)4 {5 int min = i;16 for (int j = i + 1; j < a.length; j++)17 {18 if (a[j] < a[min])19 {110 min = j;111 }112 }113 int temp = a[i];214 a[i] = a[min];215 a[min] = temp;216 }17}
- line 5-12 Find the index of the smallest value in the unsorted part
- line 13-15 One swap moves it to its final spot
| pass | smallest found | array after the swap |
|---|---|---|
| start | {9, 4, 7, 1, 6} | |
| i = 0 | 1 | {1, 4, 7, 9, 6} |
| i = 1 | 4 (already there) | {1, 4, 7, 9, 6} |
| i = 2 | 6 | {1, 4, 6, 9, 7} |
| i = 3 | 7 | {1, 4, 6, 7, 9} |
Insertion sort
Insertion sort also grows a sorted part at the front, but differently. It picks up the next element, the key, and slides every bigger value in the sorted part one spot to the right until it finds where the key belongs, then drops the key into the gap. The front stays sorted, but its values can still move on later passes.
1public static void insertionSort(int[] a)2{3 for (int i = 1; i < a.length; i++)4 {5 int key = a[i];16 int j = i - 1;7 while (j >= 0 && a[j] > key)28 {29 a[j + 1] = a[j];210 j--;211 }212 a[j + 1] = key;313 }14}
- line 5 Pick up the next value
- line 7-11 Slide each bigger sorted value one step right
- line 12 Drop the key into the gap
| pass | key | values shifted | array after |
|---|---|---|---|
| start | {9, 4, 7, 1, 6} | ||
| i = 1 | 4 | 1 | {4, 9, 7, 1, 6} |
| i = 2 | 7 | 1 | {4, 7, 9, 1, 6} |
| i = 3 | 1 | 3 | {1, 4, 7, 9, 6} |
| i = 4 | 6 | 2 | {1, 4, 6, 7, 9} |
?Wait, why is j >= 0 written first in the while condition?
How do the two compare? One informal way to measure an algorithm is to count how many times a key statement runs. Selection sort always makes the same number of comparisons: 4 + 3 + 2 + 1 = 10 for five elements, no matter the order. Insertion sort depends on the data. It's fastest when the array is already nearly sorted and slowest when it's backward.
| starting array | selection: a[j] < a[min] checks | insertion: a[j] > key checks |
|---|---|---|
| {1, 2, 3, 4, 5} (sorted) | 10 | 4 |
| {9, 4, 7, 1, 6} | 10 | 9 |
| {5, 4, 3, 2, 1} (reversed) | 10 | 10 |
- i = 1, key 5: 8 > 5, so 8 shifts right. j reaches -1 and 5 drops into index 0: {5, 8, 6, 2}.
- i = 2, key 6: 8 > 6 shifts, then 5 > 6 is false, so 6 drops in at index 1: {5, 6, 8, 2}.
Why?
The loop stops at the first value that is not bigger than the key. - i = 3, key 2: 8, 6 and 5 all shift right, and 2 drops in at index 0: {2, 5, 6, 8}.
Answer: {5, 8, 6, 2}, then {5, 6, 8, 2}, then {2, 5, 6, 8}.
Stuck? Get a hint
- Each pass picks up the element at index i.
- Shift every bigger value in the sorted part one spot right.
- Stop at the first value that is not bigger, and drop the key just after it.
- A{2, 3, 8, 6, 5}
- B{3, 6, 8, 2, 5}
- C{2, 3, 5, 6, 8}
- D{2, 3, 6, 8, 5}
Show the answer
A. Pass 1 swaps the smallest value, 2, into index 0: {2, 3, 8, 6, 5}. Pass 2 finds 3, already at index 1, so nothing moves. The second choice is the trap: that's insertion sort after two passes.
- Linear search: check each element in order; return the index, or -1 after the loop. Works on unsorted data.
- Selection sort: each pass swaps the smallest remaining value into place. The front is final after each pass.
- Insertion sort: each pass slides the next value left into the sorted part. The front is sorted but can still change.
- Selection sort makes the same number of comparisons on any data; insertion sort does fewer on nearly sorted data.