Question? Leave a message!




Sorting and Searching

Sorting and Searching
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Comment
4.2 Sorting and Searching Introduction to Programming in Java: An Interdisciplinary Approach · Robert Sedgewick and Kevin Wayne · Copyright © 2002–2010 · 6/26/10 8:09 AM Sequential Search Sequential search. Scan through array, looking for key.   Search hit: return array index.   Search miss: return -1. public static int search(String key, String a) int N = a.length; for (int i = 0; i a.length; i++) if (ai.compareTo(key) == 0) return i; return -1; 2 Search Client: Exception Filter Exception filter. Read a sorted list of strings from a whitelist file, then print out all strings from standard input not in the whitelist. public static void main(String args) In in = new In(args0); String s = in.readAll(); String words = s.split("\\s+"); while (StdIn.isEmpty()) String key = StdIn.readString(); if (search(key, words) == -1) StdOut.println(key); 3 Searching Challenge 1 Q. A credit card company needs to whitelist 10 million customer account numbers, processing 1,000 transactions per second. Using sequential search, what kind of computer is needed? A.  Toaster B.  Cellphone C.  Your laptop D.  Supercomputer E.  Google server farm 4 Binary Search 5 Twenty Questions Intuition. Find a hidden integer. 6 Binary Search Main idea.   Sort the array (stay tuned).   Play "20 questions" to determine index with a given key. Ex. Dictionary, phone book, book index, credit card numbers, … Binary search.   Examine the middle key.   If it matches, return its index.   Otherwise, search either the left or right half. 7 Binary Search: Java Implementation Invariant. Algorithm maintains alo ≤ key ≤ ahi-1. public static int search(String key, String a) return search(key, a, 0, a.length); public static int search(String key, String a, int lo, int hi) if (hi = lo) return -1; int mid = lo + (hi - lo) / 2; int cmp = amid.compareTo(key); if (cmp 0) return search(key, a, lo, mid); else if (cmp 0) return search(key, a, mid+1, hi); else return mid; Java library implementation: Arrays.binarySearch() 8 Binary Search: Mathematical Analysis Analysis. To binary search in an array of size N: do one compare, then binary search in an array of size N / 2. N → N / 2 → N / 4 → N / 8 → … → 1 Q. How many times can you divide a number by 2 until you reach 1? A. log N. 2 1  2 → 1 4 → 2 → 1 8 → 4 → 2 → 1 16 → 8 → 4 → 2 → 1 32 → 16 → 8 → 4 → 2 → 1 64 → 32 → 16 → 8 → 4 → 2 → 1 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1 9 Searching Challenge 2 Q. A credit card company needs to whitelist 10 million customer account numbers, processing 1,000 transactions per second. Using binary search, what kind of computer is needed? A.  Toaster B.  Cell phone C.  Your laptop D.  Supercomputer E.  Google server farm 10 Sorting Sorting Sorting problem. Rearrange N items in ascending order. Applications. Statistics, databases, data compression, bioinformatics, computer graphics, scientific computing, (too numerous to list), ... Hauser Hanley Hong Haskell Hsu Hauser Hayes Hayes Haskell Hong Hanley Hornet Hornet Hsu 12 Insertion Sort 13 Insertion Sort Insertion sort.   Brute-force sorting solution.   Move left-to-right through array.   Exchange next element with larger elements to its left, one-by-one. 14 Insertion Sort Insertion sort.   Brute-force sorting solution.   Move left-to-right through array.   Exchange next element with larger elements to its left, one-by-one. 15 Insertion Sort: Java Implementation public class Insertion public static void sort(String a) int N = a.length; for (int i = 1; i N; i++) for (int j = i; j 0; j) if (aj-1.compareTo(aj) 0) exch(a, j-1, j); else break; private static void exch(String a, int i, int j) String swap = ai; ai = aj; aj = swap; 16 Insertion Sort: Empirical Analysis Observation. Number of compares depends on input family. 2   Descending: N / 2. 2   Random: N / 4.   Ascending: N. 10000000 Descendng Random 100000 Ascending 1000 10 0.1 0.001 1000 10000 100000 1000000 Input Size 17 Comparsions (millions)Insertion Sort: Mathematical Analysis Worst case. descending   Iteration i requires i comparisons. 2   Total = (0 + 1 + 2 + ... + N-1) N / 2 compares. E F G H I J D C B A i Average case. random   Iteration i requires i / 2 comparisons on average. 2   Total = (0 + 1 + 2 + ... + N-1) / 2 N / 4 compares A C D F H J E B I G i 18 Sorting Challenge 1 Q. A credit card company sorts 10 million customer account numbers, for use with binary search. Using insertion sort, what kind of computer is needed? A.  Toaster B.  Cell phone C.  Your laptop D.  Supercomputer E.  Google server farm 19 Insertion Sort: Lesson Lesson. Supercomputer can't rescue a bad algorithm. Comparisons Computer Thousand Million Billion Per Second 7 laptop 10 instant 1 day 3 centuries 12 super 10 instant 1 second 2 weeks 20