Computer Science 15-110, Spring 2010
Class Notes: Searching and Sorting
Searching and Sorting
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)); } }
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)); } }
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? } }
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?
}
}
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); } }
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)); } }
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)); } }
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)); } }
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)); } }
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)); } }
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)); } }
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