Analysis of Algorithms : An Active Learning Approach

2.1 SEQUENTIAL SEARCH 43 2.1 Sequential Search In search algorithms, we are concerned with the process of looking through a list ...

44 SEARCHING AND SELECTION ALGORITHMS ■ 2.1.1 Worst-Case Analysis There are two worst cases for the sequential search algorithm. ...

2.1 SEQUENTIAL SEARCH 45 What about the third? What about the last or Nth location? If you looked at the algorithm carefully, ...

46 SEARCHING AND SELECTION ALGORITHMS 2.1.3 Sequential search can also be used for a sorted list. Write an algorithm called Sor ...

2.2 BINARY SEARCH 47 what is left of the list with each comparison. This results in the following algorithm:^2 BinarySearch( lis ...

48 SEARCHING AND SELECTION ALGORITHMS loop’s conditional will become false, and the loop will stop. Therefore, the loop does alw ...

2.2 BINARY SEARCH 49 Building a decision tree for the search process can also help with this analy- sis. The nodes of the decisi ...

50 SEARCHING AND SELECTION ALGORITHMS means that we can determine the total number of comparisons done for every possible case b ...

2.2 BINARY SEARCH 51 Now, let’s consider the second situation where we include the possibility that the target is not in the lis ...

52 SEARCHING AND SELECTION ALGORITHMS 2.2.3 Draw the decision tree for the binary search algorithm for a list of 12 ele- ments. ...

2.3 SELECTION 53 Write an algorithm to do a multiway search. For your answer, you can assume that each node has two arrays calle ...

54 SEARCHING AND SELECTION ALGORITHMS for j = 2 to N-(i-1) do if list[j] > largest then largest = list[j] largestLocation = j ...

2.4 PROGRAMMING EXERCISE 55 start the index of the first value to consider end the value of the last value to consider K the ele ...

56 SEARCHING AND SELECTION ALGORITHMS should be incremented just before the key comparison in your sequential search routine. Yo ...

Chapter 3 Sorting Algorithms PREREQUISITES Before beginning this chapter, you should be able to Read and create iterative and r ...

58 SORTING ALGORITHMS sort, bubble sort, shellsort, heapsort, merge sort, and quicksort using the lists [6, 2, 4, 7, 1, 3, 8, 5] ...

3.1 INSERTION SORT 59 ing these two. Quicksort is a recursive sort that picks a pivot element from the list and then subdivides ...

60 SORTING ALGORITHMS end while list[ location + 1 ] = newElement end for This algorithm copies the next value to be inserted in ...

3.1 INSERTION SORT 61 sorted part of the list does at most i comparisons. It should be obvious that we do at least one compariso ...

62 SORTING ALGORITHMS By two applications of Equation 1.11, we get Notice that by using Equations 1.9 and 1.10, we have By appli ...