算法课件全121301ADA05蛮力法串匹配与冒泡排序.pptVIP

2007-2008-01《Design and Analysis of Algorithms》SCUEC Goals of This Lecture At the end of this lecture, you should Know what’s brute force approach and its advantages and disadvantages Master the basic idea of brute force string match algorithm and analyze its time complexity Master the bubble sort algorithm and its best-case, worst-case and average-case analysis What’s Brute Force Method Description: A straightforward approach, usually based directly on the problem’s statement and definitions of the concepts involved. Application to sorting problem Problem description: given a list of N orderable items (eg., numbers, character string), we want to rearrange them in nondecreasing order. Bubble sort Idea: Compare adjacent elements of the list and exchange them if they are out of order. By doing it repeatedly, we end up “bubbling up” the largest element to the last position on the list. The next pass bubbles up the second largest element, and so on. Until after n-1 passes, the list is sorted. Bubble sort Algorithm ALGORITHM BubbleSort(A[0…n-1]) //Input: An array A[0…n-1] of orderable of elements //Output: Array A[0…n-1] sorted in ascending order numberOfComparisons ← n-1 needSwap ← true While needSwap do needSwap ← False for i ← 0 to numberOfComparisons-1 do if A[i+1] A[i] then Swap(A[i], A[i+1]) needSwap ← true end if end for numberOfComparisons ← numberOfComparisons -1 end while Bubble Sort Example Bubble Sort Example Bubble Sort Example Bubble Sort Example Bubble Sort Example Bubble Sort Example Bubble Sort Example Bubble Sort Example Bubble Sort Example Time complexity analysis Input size Basic operation Is the input instance affect the time efficiency? Best-case Analysis The input instances in which elements are in order will lead to the best case. This means there are no swaps on the first pass. How many comparisons are done in this best case? only one pass: n-1 comparisons