Young Coders: Week 4 Notes
Sorting and Searching
- Bubble Sort, Insertion Sort, Selection Sort
- Linear Search, Binary Search
How to swap two elements
We first looked at how to swap two elements. Let's say we have
int a = 2;
int b = 3;
and we want to switch their values, so that a = 3 and b = 2.
Remember, we can't just say:
a = b;
b = a;
As we saw on the whiteboard yesterday, this will make both a and b equal to 3, instead of switching their values:
One way to switch a and b's values is by using a "temp" variable:
int temp = a;
a = b;
b = temp;
And the corresponding diagram we drew:
a is now 3 and b is now 2 ... this works!
Sorting
We went over three algorithms for sorting a list of elements (in ascending order).Bubble Sort
Here is our method for bubble sort. We are comparing every pair of elements, and if the second one is smaller than the first one, we swap them. You can try simulating this by taking a few cards from a deck and sorting them.
public static int[] bubble(int[] array) {
int temp;
for(int i = 0; i < array.length; i++) {
for(int j = i+1; j < array.length; j++) {
if(array[i] > array[j]) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
return array;
}
That wasn't too efficient...can we do better?
Insertion Sort
This algorithm divides the array into parts: a sorted part and an unsorted part. Each time around, it takes the next element in the unsorted part and moves that element to its correct place in the sorted part.
public static int[] insertion(int[] array) {
int temp;
for(int i = 1; i < array.length; i++) {
int j = i;
while((j>0) && (array[j] < array[j-1])) {
temp = array[j];
array[j] = array[j-1];
array[j-1] =temp;
j--;
}
}
return array;
}
Selection Sort
Selection sort also divides the array into a sorted part and an unsorted part. Each time, it takes the smallest element in the unsorted part and moves it to the end of the sorted part.
public static int[] selection(int[] array) {
int min; //index of minimum
int temp;
for(int i = 0; i < array.length; i++) {
min = i;
for(int j = i+1; j < array.length; j++)
if(array[j] < array[min])
min = j;
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
return array;
}
Searching
Linear Search
Linear search is pretty straightforward. One way to search an array for an element is just going in order (proceeding linearly). Here is our code from yesterday. We tested our linear search method with the array {1,10,5,-4} and looked for 5 (our "key"). Our method returns the index of our key, 2. If our key had been 100, our method would have returned -1.
public class SearchingIsFun {
public static int linearSearch(int[] array, int key) {
for(int i = 0; i < array.length; i++)
if(array[i] == key)
return i;
return -1;
}
public static void main(String[] args) {
System.out.println(linearSearch(new int[] {1, 10, 5, -4}, 5));
}
}
Binary Search
Another searching algorithm is called a "binary search". Before talking about it, imagine a game of "Guess The Number"...
"I'm thinking of a number between 1 and 100."
"Is your number 50?"
"It is higher than 50."
"Is your number 75?"
"It is lower than 75."
"Is your number 62?"
"It is higher than 62."
"Is your number 68?"
"It is lower than 68."
"Is your number 65?"
"You got it! My number is 65!"
One strategy for "Guess the Number" is always guessing the middle number in the possible range. As a result, the possible range also halves each time. That's what the binary search algorithm does.
Let's go over binary search in an array of ints. Note: Make sure the array is already sorted before you perform a binary search!
In our example, we searched for 551, the "key". The arrows "low" and "high" keep track of the range in where our key could be. I took the images from the following website:
http://www.cdf.toronto.edu/~ajr/104/diary/06/binarysearchslides/
What if our key is not in the array? Suppose the key is 552:
import java.util.Arrays;
public class BinarySearch {
public static int binSearch(int[] a, int key) {
int lo = 0;
int hi = a.length-1;
while(lo <= hi) {
int mid = lo + (hi-lo)/2;
if(key < a[mid])
hi = mid-1;
else if(key > a[mid])
lo = mid+1;
else
return mid;
}
return -1;
}
public static void main(String[] args) {
int[] test = {30, 40, 2};
Arrays.sort(test);
System.out.println(binSearch(test, 40));
}
}
