Topic 11 Sti dS hiSorting and Searching"There's nothing in your head theThere s nothing in your head the sorting hat can't see. So try me on and I will tell you where youon and I will tell you where you ought to be." The Sorting HatHarry Potter-The Sorting Hat, Harry Potter and the Sorcerer's StoneCS 307 Fundamentals of Computer Science Sorting and Searching1Sorting and Searching88Fundamental problems in computer science and programming8Sorting done to make searching easier8Multiple different algorithms to solve the utped ee tago t stoso et esame problem–Howdoweknowwhichalgorithmis"better"?How do we know which algorithm is better ?8Look at searching first8E amples ill se arra s of ints to ill strate8Examples will use arrays of ints to illustrate algorithms CS 307 Fundamentals of Computer Science Sorting and Searching2SearchingCS 307 Fundamentals of Computer Science Sorting and Searching3Searching8Gi li t f d t fi d th l ti f8Given a list of data find the location of a particular value or report that value is not presentpresent8linear searchint iti e approach–intuitive approach– start at first itemis it the one I am looking for?–is it the one I am looking for?– if not go to next itemrepeat until found or all items checked–repeat until found or all items checked8If items not sorted or unsortable this approach is necessaryCS 307 Fundamentals of Computer Science Sorting and Searching4approach is necessaryLinear Search/* pre: list != nullppost: return the index of the first occurrenceof target in list or -1 if target not present in list*/*/public int linearSearch(int[] list, int target) {for(int i = 0; i < list.length; i++)if( list[i]==target )if( list[i] target )return i;return -1;}CS 307 Fundamentals of Computer Science Sorting and Searching5Linear Search, Generic//* pre: list != null, target != nullpost: return the index of the first occurrenceof target in list or -1 if target not present in listlist*/public int linearSearch(Object[] list, Object target) {for(int i = 0; i < list.length; i++)iii iiif( list[i] != null && list[i].equals(target) )return i;return -1;}}T(N)? Big O? Best case, worst case, average case?CS 307 Fundamentals of Computer Science Sorting and Searching6Attendance Question 188What is the average case Big O of linear search in an array with N items, if an item is present?A. O(N)B. O(N2) CO(1)C.O(1)D. O(logN)EO(Nl N)E.O(NlogN)CS 307 Fundamentals of Computer Science Sorting and Searching7Searching in a Sorted List8If it t d thdi id d8If items are sorted then we can divide and conquer8di idi k i h lf ith h t8dividing your work in half with each step – generally a good thing8Th Bi S h Li t i A di d8The Binary Search on List in Ascending order– Start at middle of listi th t th it ?–is that the item?– If not is it less than or greater than the item?lth t dhlfflit–less than, move to second half of list– greater than, move to first half of listrepeat until found or sub list size = 0CS 307 Fundamentals of Computer Science Sorting and Searching8–repeat until found or sub list size = 0Binary Searchlistlow item middle item high itemIs middle item what we are looking for? If not is itIs middle item what we are looking for? If not is itmore or less than the target item? (Assume lower)listlow middle high item item itemCS 307 Fundamentals of Computer Science Sorting and Searching9and so forth…Binary Search in Action0 1 2 3 4 5 6 7 8 9 1011121314152 3 5 7 11 13 17 19 23 29 31 37 41 4743 530 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15public static int bsearch(int[] list, int target)public static int bsearch(int[] list, int target){ int result = -1;int low = 0;int high = list.length - 1;int mid;while( result == -1 && low <= high ){ mid = low + ((high - low) / 2);if( list[mid] == target )result = mid;else if( list[mid] < target)low = mid + 1;elsehigh = mid - 1;}}return result;}// mid = ( low + high ) / 2; // may overflow!!!// id (l hi h) 1 i bi iCS 307 Fundamentals of Computer Science Sorting and Searching10// or mid = (low + high) >>> 1; using bitwise opTrace When Key == 3Trace When Key == 30Variables of Interest?CS 307 Fundamentals of Computer Science Sorting and Searching11Attendance Question 2What is the worst case Big O of binary search in an array with N items, if an item is present?A. O(N)B. O(N2) C. O(1)D. O(logN)E. O(NlogN)CS 307 Fundamentals of Computer Science Sorting and Searching12Generic Binary Searchpublic static int bsearch(Comparable[] list, Comparable target){ int result = -1;int low = 0;int high = list.length - 1;ggint mid;while( result == -1 && low <= high ){ mid = low + ((high - low) / 2);if( target equals(list[mid]) )if( target.equals(list[mid]) )result = mid;else if(target.compareTo(list[mid]) > 0)low = mid + 1;lelsehigh = mid - 1;}return result;}CS 307 Fundamentals of Computer Science Sorting and Searching13Recursive Binary Searchpublic static int bsearch(int[] list int target){public static int bsearch(int[] list, int target){return bsearch(list, target, 0, list.length – 1);}bli i i b h(i [] li ipublic static int bsearch(int[] list, int target,int first, int last){if( first <= last ){int mid = low + ((high - low) / 2);if( list[mid] == target )return mid;else if( list[mid] > target )return bsearch(list, target, first, mid–1);return bsearch(list, target, first, mid 1);elsereturn bsearch(list, target, mid + 1, last);}return-1;return 1;}CS 307 Fundamentals of Computer Science Sorting and Searching14Other Searching Algorithms88Interpolation Search– more like what people really do8Indexed Searching8Binary Search TreesBinary Search Trees8Hash Table Searching8G'Alith(Witif8Grover's Algorithm (Waiting for quantum computers to be built)88best-first8A*CS 307 Fundamentals of Computer Science Sorting and Searching15SortingSortingCS 307 Fundamentals of Computer Science Sorting and Searching16Sorting FunSorting FunWhy Not Bubble Sort?yCS 307 Fundamentals of Computer Science Sorting and Searching17Sorting8A fundamental application for computers8A fundamental application for computers8Done to make finding data (searching) faster8M diff t l ith f ti8Many different algorithms for sorting8One of the difficulties with sorting is working ith fi d i t t i ( )with a fixed size storage container (array)– if resize, that is expensive (slow)88The "simple" sorts run in quadratic time O(N2)b bbl t–bubble sort– selection sortiti tCS 307 Fundamentals of Computer Science Sorting and Searching18–insertion sortStable Sorting8Atft8A property of sorts8If a
View Full Document
Unlocking...