Searching and SortingCommon ProblemsSearchingSequential Search on an Unordered FileSequential Search on an Ordered FileSequential Search of Ordered vs. Unordered ListOrdered vs Unordered (cont.)Ordered vs. Unordered (cont.)Binary SearchHow a Binary Search WorksHow Fast is a Binary Search?How Fast is a Binary Search?What’s the Pattern?A Very Fast Algorithm!Lg n EfficiencySortingCommon Sort AlgorithmsBubble Sort - Let’s Do One!Bubble Sort CodeInsertion SortArranging Your HandSlide 22Slide 23Insertion Sort (cont.)Slide 25Slide 26Courses at UMBCSearching and SortingTopicsSequential Search on an Unordered FileSequential Search on an Ordered FileBinary SearchBubble SortInsertion SortReadingSections 6.6 - 6.8Common ProblemsThere are some very common problems that we use computers to solve: Searching through a lot of records for a specific record or set of recordsPlacing records in order, which we call sortingThere are numerous algorithms to perform searches and sorts. We will briefly explore a few common ones.SearchingA question you should always ask when selecting a search algorithm is “How fast does the search have to be?” The reason is that, in general, the faster the algorithm is, the more complex it is.Bottom line: you don’t always need to use or should use the fastest algorithm.Let’s explore the following search algorithms, keeping speed in mind.Sequential (linear) searchBinary searchSequential Search on an Unordered FileBasic algorithm:Get the search criterion (key)Get the first record from the fileWhile ( (record != key) and (still more records) )Get the next recordEnd_whileWhen do we know that there wasn’t a record in the file that matched the key?Sequential Search on an Ordered FileBasic algorithm:Get the search criterion (key)Get the first record from the fileWhile ( (record < key) and (still more records) )Get the next recordEnd_whileIf ( record = key )Then successElse there is no match in the fileEnd_elseWhen do we know that there wasn’t a record in the file that matched the key?Sequential Search of Ordered vs. Unordered ListLet’s do a comparison.If the order was ascending alphabetical on customer’s last names, how would the search for John Adams on the ordered list compare with the search on the unordered list?Unordered listif John Adams was in the list?if John Adams was not in the list?Ordered listif John Adams was in the list?if John Adams was not in the list?Ordered vs Unordered (cont.)How about George Washington?Unordered if George Washington was in the list? If George Washington was not in the list?Ordered if George Washington was in the list? If George Washington was not in the list?How about James Madison?Ordered vs. Unordered (cont.)Observation: the search is faster on an ordered list only when the item being searched for is not in the list.Also, keep in mind that the list has to first be placed in order for the ordered search.Conclusion: the efficiency of these algorithms is roughly the same.So, if we need a faster search, we need a completely different algorithm.How else could we search an ordered file?Binary SearchIf we have an ordered list and we know how many things are in the list (i.e., number of records in a file), we can use a different strategy.The binary search gets its name because the algorithm continually divides the list into two parts.How a Binary Search WorksAlways look at the center value. Each time you get to discard half of the remaining list. Is this fast ?How Fast is a Binary Search?Worst case: 11 items in the list took 4 triesHow about the worst case for a list with 32 items ?1st try - list has 16 items2nd try - list has 8 items3rd try - list has 4 items4th try - list has 2 items5th try - list has 1 itemHow Fast is a Binary Search? List has 250 items1st try - 125 items2nd try - 63 items3rd try - 32 items4th try - 16 items5th try - 8 items6th try - 4 items7th try - 2 items8th try - 1 itemList has 512 items1st try - 256 items2nd try - 128 items3rd try - 64 items4th try - 32 items5th try - 16 items6th try - 8 items7th try - 4 items8th try - 2 items9th try - 1 itemWhat’s the Pattern? List of 11 took 4 triesList of 32 took 5 triesList of 250 took 8 triesList of 512 took 9 tries32 = 25 and 512 = 298 < 11 < 16 23 < 11 < 24128 < 250 < 256 27 < 250 < 28A Very Fast Algorithm!How long (worst case) will it take to find an item in a list 30,000 items long? 210 = 1024 213 = 8192 211 = 2048 214 = 16384 212 = 4096 215 = 32768So, it will take only 15 tries!Lg n EfficiencyWe say that the binary search algorithm runs in log2 n time. (Also written as lg n)Lg n means the log to the base 2 of some value of n.8 = 23 lg 8 = 3 16 = 24 lg 16 = 4There are no algorithms that run faster than lg n time.SortingSo, the binary search is a very fast search algorithm.But, the list has to be sorted before we can search it with binary search.To be really efficient, we also need a fast sort algorithm.Common Sort AlgorithmsBubble Sort Heap SortSelection Sort Merge SortInsertion Sort Quick SortThere are many known sorting algorithms. Bubble sort is the slowest, running in n2 time. Quick sort is the fastest, running in n lg n time.As with searching, the faster the sorting algorithm, the more complex it tends to be.We will examine two sorting algorithms:Bubble sortInsertion sortBubble Sort - Let’s Do One!CPGATOBBubble Sort Codevoid bubbleSort (int a[ ] , int size){ int i, j, temp; for ( i = 0; i < size; i++ ) /* controls passes through the list */ {for ( j = 0; j < size - 1; j++ ) /* performs adjacent comparisons */{if ( a[ j ] > a[ j+1 ] ) /* determines if a swap should occur */{temp = a[ j ]; /* swap is performed */a[ j ] = a[ j + 1 ];a[ j+1 ] = temp;}}}}Insertion SortInsertion sort is slower than quick sort, but not as slow as bubble sort, and it is easy to understand.Insertion sort works the same way as arranging your hand when playing cards.Out of the pile of unsorted cards that were dealt to you, you pick up a card and place it in your hand in the correct position relative to the cards you’re already holding.Arranging Your Hand75 7Arranging Your Hand 5 6 7575 6 7K5 6 7 8 KInsertion Sort Unsorted -
View Full Document