Computer Science 15-110, Spring 2010
Class Notes:  Searching and Sorting

Searching and Sorting

1. Searching

1. Linear Search
```class MyCode {
public static int linearSearch(int[] a, int key) {
int n = a.length;
for (int i=0; i<n; i++)
if (a[i] == key)
return i;
return -1;
}

public static void main(String[] args) {
int[] a = { 2, 5, 4, 1, 3 };
System.out.println(linearSearch(a,4));
System.out.println(linearSearch(a,6));
}
}```
2. Binary Search

1. Binary Search Implementation
```class MyCode {
public static int binarySearch(int[] a, int key) {
int lo = 0;
int hi = a.length-1;
while (lo <= hi) {
int i = (lo + hi)/2;
if (a[i] < key)
lo = i + 1;
else if (a[i] > key)
hi = i - 1;
else
// found it!
return i;
}
return -1;
}

public static void main(String[] args) {
int[] a = { 2, 4, 6, 8, 10, 12 };
System.out.println(binarySearch(a,6));
System.out.println(binarySearch(a,7));
}
}```
2. Improper Use:  Binary Search in an Unsorted Array
```class MyCode {
public static int binarySearch(int[] a, int key) {
int lo = 0;
int hi = a.length-1;
while (lo <= hi) {
int i = (lo + hi)/2;
if (a[i] < key)
lo = i + 1;
else if (a[i] > key)
hi = i - 1;
else
// found it!
return i;
}
return -1;
}

public static void main(String[] args) {
int[] a = { 6, 2, 4, 8 };
System.out.println(binarySearch(a,6));  // surprised?
}
}```
3. Arrays.binarySearch
```import java.util.Arrays;
class MyCode {
public static void main(String[] args) {
int[] a = { 2, 4, 6, 8, 10, 12 };
System.out.println(Arrays.binarySearch(a,6));
System.out.println(Arrays.binarySearch(a,7)); // why not -1?
}
}```
3. Informal Time Comparisons
```import java.util.*;
class MyCode {

/////////////////////////////
// Timer Code
/////////////////////////////

private static long startTime, endTime;

public static void startTiming() {
startTime = System.currentTimeMillis();
}

public static void stopTiming() {
endTime = System.currentTimeMillis();
}

public static int elapsedTime() {
return (int)(endTime - startTime);
}

/////////////////////////////
// Timed Searches
/////////////////////////////

private static String[] searchTypes = { "Linear", "Binary", "Built-in Binary" };
private static int LINEAR = 0, BINARY = 1, BUILT_IN_BINARY = 2;

public static void timedSearch(int[] a, int searchType) {
System.out.println("Timing " + searchTypes[searchType] + " search:");
int n = a.length;
// search for each of the n elements in the array
startTiming();
for (int key=0; key<n; key++) {
if (searchType == LINEAR)
linearSearch(a, key);
else if (searchType == BINARY)
binarySearch(a, key);
else if (searchType == BUILT_IN_BINARY)
Arrays.binarySearch(a, key);
else
throw new RuntimeException("Unknown search type!: " + searchType);
}
stopTiming();
System.out.println("Elapsed time: " + elapsedTime() + " ms");
}

/////////////////////////////
// Linear and Binary Search
/////////////////////////////

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

public static int binarySearch(int[] a, int key) {
int lo = 0;
int hi = a.length-1;
while (lo <= hi) {
int i = (lo + hi)/2;
if (a[i] < key)
lo = i + 1;
else if (a[i] > key)
hi = i - 1;
else
// found it!
return i;
}
return -1;
}

/////////////////////////////
// Main
/////////////////////////////

public static void main(String[] args) {
// Get n from user
Scanner scanner = new Scanner(System.in);
System.out.print("Enter n (suggestion: 50 thousand): ");
int n = scanner.nextInt();

// Create sorted array of size n
int[] a = new int[n];
for (int i=0; i<n; i++) a[i] = i;

// Time searching all N elements
for (int searchType=0; searchType<searchTypes.length; searchType++)
timedSearch(a, searchType);
}
}```
2. Sorting

1. xSortLab
2. Bubble Sort

1. First Try
```import java.util.*;
class MyCode {
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void bubblesortFirstTry(int[] a) {
int n = a.length;
boolean unsorted = true;
while (unsorted) {
unsorted = false;
for (int i=1; i<n; i++)
if (a[i] < a[i-1]) {
swap(a, i, i-1);
unsorted = true;
}
}
}

public static void main(String[] args) {
int[] a = { 4, 2, 5, 1, 3 };
System.out.println(Arrays.toString(a));
bubblesortFirstTry(a);
System.out.println(Arrays.toString(a));
}
}```
2. Better Bubble Sort
```import java.util.*;
class MyCode {
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void bubblesort(int[] a) {
int n = a.length;
int pass = 0;
boolean unsorted = true;
while (unsorted) {
unsorted = false;
for (int i=1; i<n-pass; i++)
if (a[i] < a[i-1]) {
swap(a, i, i-1);
unsorted = true;
}
pass++;
}
}

public static void main(String[] args) {
int[] a = { 4, 2, 5, 1, 3 };
System.out.println(Arrays.toString(a));
bubblesort(a);
System.out.println(Arrays.toString(a));
}
}```
3. Selection Sort
```import java.util.*;
class MyCode {
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void selectionsort(int[] a) {
int n = a.length;
for (int i=0; i<n; i++) {
int indexOfSmallest = i;
for (int j=i+1; j<n; j++)
if (a[j] < a[indexOfSmallest])
indexOfSmallest = j;
swap(a, i, indexOfSmallest);
}
}

public static void main(String[] args) {
int[] a = { 4, 2, 5, 1, 3 };
System.out.println(Arrays.toString(a));
selectionsort(a);
System.out.println(Arrays.toString(a));
}
}```
4. Insertion Sort
```import java.util.*;
class MyCode {
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void insertionsort(int[] a) {
int n = a.length;
for (int i=0; i<n; i++)
for (int j=i; (j>0 && a[j] < a[j-1]); j--)
swap(a, j, j-1);
}

public static void main(String[] args) {
int[] a = { 4, 2, 5, 1, 3 };
System.out.println(Arrays.toString(a));
insertionsort(a);
System.out.println(Arrays.toString(a));
}
}```
5. Merge Sort (Iterative)
```import java.util.*;
class MyCode {
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void mergesort(int[] a) {
int[] aux = new int[a.length];
for (int blockSize=1; blockSize<a.length; blockSize*=2)
for (int start=0; start<a.length; start+=2*blockSize)
merge(a, aux, start, start+blockSize, start+2*blockSize);
}

private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
int n = a.length;
if (mid >= n) return;
if (hi > n) hi = n;
int i = lo, j = mid;
for (int k = lo; k < hi; k++) {
if      (i == mid)    { aux[k] = a[j]; j++; }
else if (j == hi)     { aux[k] = a[i]; i++; }
else if (a[j] < a[i]) { aux[k] = a[j]; j++; }
else                  { aux[k] = a[i]; i++; }
}
// copy back
for (int k = lo; k < hi; k++)
a[k] = aux[k];
}

public static void main(String[] args) {
int[] a = { 4, 2, 5, 1, 3 };
System.out.println(Arrays.toString(a));
mergesort(a);
System.out.println(Arrays.toString(a));
}
}```
6. Arrays.sort
```import java.util.*;
class MyCode {
public static void main(String[] args) {
int[] a = { 4, 2, 5, 1, 3 };
System.out.println(Arrays.toString(a));
Arrays.sort(a);
System.out.println(Arrays.toString(a));
}
}```
7. Informal Time Comparisons of Sorts
```import java.util.*;
class MyCode {

/////////////////////////////
// Timer Code
/////////////////////////////

private static long startTime, endTime;

public static void startTiming() {
startTime = System.currentTimeMillis();
}

public static void stopTiming() {
endTime = System.currentTimeMillis();
}

public static int elapsedTime() {
return (int)(endTime - startTime);
}

/////////////////////////////
// Timed Sorts
/////////////////////////////

private static String[] sortTypes = { "Bubble First Try", "Bubble","Selection",
"Insertion", "Merge", "Built-in" };
private static int BUBBLE_FIRST_TRY = 0, BUBBLE = 1, SELECTION = 2,
INSERTION = 3, MERGE = 4, BUILT_IN = 5;

public static int[] copyArray(int[] a) {
int n = a.length;
int[] copy = new int[n];
for (int i=0; i<n; i++)
copy[i] = a[i];
return copy;
}

public static void timedSort(int[] a, int sortType) {
System.out.print("Timing " + sortTypes[sortType] + " Sort:");
for (int i=sortTypes[sortType].length(); i<17; i++)
System.out.print(" ");
// copy the array (so we don't modify it)!
int[] copy = copyArray(a);

// sort copy of array
startTiming();
if (sortType == BUBBLE_FIRST_TRY)
bubblesortFirstTry(copy);
else if (sortType == BUBBLE)
bubblesort(copy);
else if (sortType == SELECTION)
selectionsort(copy);
else if (sortType == INSERTION)
insertionsort(copy);
else if (sortType == MERGE)
mergesort(copy);
else if (sortType == BUILT_IN)
Arrays.sort(copy);
else
throw new RuntimeException("Unknown sort type!: " + sortType);
stopTiming();

// Now confirm we actually sorted the array without
// modifying it!  To do this, we'll compare our results
// against a built-in sort of another copy of the array
int[] copy2 = copyArray(a);
Arrays.sort(copy2);
if (!Arrays.equals(copy, copy2))
System.out.println("Oh no:  Sort failed!!!!");

// And print our results...
System.out.println("Elapsed time: " + elapsedTime() + " ms");
}

/////////////////////////////
// Sort algorithms
/////////////////////////////

public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void bubblesortFirstTry(int[] a) {
int n = a.length;
boolean unsorted = true;
while (unsorted) {
unsorted = false;
for (int i=1; i<n; i++)
if (a[i] < a[i-1]) {
swap(a, i, i-1);
unsorted = true;
}
}
}

public static void bubblesort(int[] a) {
int n = a.length;
int pass = 0;
boolean unsorted = true;
while (unsorted) {
unsorted = false;
for (int i=1; i<n-pass; i++)
if (a[i] < a[i-1]) {
swap(a, i, i-1);
unsorted = true;
}
pass++;
}
}

public static void selectionsort(int[] a) {
int n = a.length;
for (int i=0; i<n; i++) {
int indexOfSmallest = i;
for (int j=i+1; j<n; j++) {
if (a[j] < a[indexOfSmallest])
indexOfSmallest = j;
}
swap(a, i, indexOfSmallest);
}
}

public static void insertionsort(int[] a) {
int n = a.length;
for (int i=0; i<n; i++)
for (int j=i; (j>0 && a[j] < a[j-1]); j--)
swap(a, j, j-1);
}

public static void mergesort(int[] a) {
int[] aux = new int[a.length];
for (int blockSize=1; blockSize<a.length; blockSize*=2)
for (int start=0; start<a.length; start+=2*blockSize)
merge(a, aux, start, start+blockSize, start+2*blockSize);
}

private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
int n = a.length;
if (mid >= n) return;
if (hi > n) hi = n;
int i = lo, j = mid;
for (int k = lo; k < hi; k++) {
if      (i == mid)    { aux[k] = a[j]; j++; }
else if (j == hi)     { aux[k] = a[i]; i++; }
else if (a[j] < a[i]) { aux[k] = a[j]; j++; }
else                  { aux[k] = a[i]; i++; }
}
// copy back
for (int k = lo; k < hi; k++)
a[k] = aux[k];
}

/////////////////////////////
// Main
/////////////////////////////

public static void main(String[] args) {
// Get n from user
Scanner scanner = new Scanner(System.in);
System.out.print("Enter n (suggestion: 20 thousand): ");
int n = scanner.nextInt();

// Create unsorted array of size n
Random random = new Random();
int[] a = new int[n];
for (int i=0; i<n; i++) a[i] = random.nextInt();

// Time sorting the array
for (int sortType=0; sortType<sortTypes.length; sortType++)
timedSort(a, sortType);
}
}```

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem