Searching & SortingSearching with Linear SearchLinear SearchSortingInsertion SortSlide 6Slide 7Slide 8Pascal Code for Insertion SortSlide 10Slide 11Modification for Practical usageSlide 13Binary SearchSlide 15Binary Search ImplementationSlide 17J. Michael MooreSearching & SortingCSCE 110J. Michael MooreSearching with Linear SearchMany times, it is necessary to search an array to find a particular entry.To study the basics of this issue, we will look at an array of ________ integers (I.e. no __________) and search for a particular value called the ______. The answer is the ________ of the array element that holds the ______. If the ______ is not in the array, then this should be conveyed.J. Michael MooreLinear SearchA simple algorithm for linear (or sequential) search:Const MAX = 5;Type Number = Array[1..MAX] of integer;function linearSearch (A:Number, int key):integer;{returns the index to where the search value is found} begin var i:integer; linearSearch := -1; for i := 1 to MAX do if (A[i]=key) then linearSearch := i; end;_______________ running time is proportional to the __________________ in the array.O(n)If entries are ordered, faster algorithms are possible.J. Michael MooreSortingMany applications using arrays require that the data be sorted.A[1] < A[2] < ... < A[n-1]When the data is sorted, other operations can be done ______________ (e.g., searching).J. Michael MooreInsertion SortMany sorting algorithms have been devised. This is a simple one called insertion sort.•Think of the array as ___________ into the part that is __________ _________ and the part that is __________________.•Initially, only the _________________ of the array , A[1], is sorted. The rest, A[2..n], is not.J. Michael MooreInsertion Sort•Suppose we’ve sorted A[1..i-1]. Our task is to insert the ith entry, v, into its correct place among the already sorted entries.A[1]A[i-1]A[i]A[i+1] A[n]vsorted unsortedTo be ________ into __________ arrayJ. Michael MooreInsertion SortStart _____________ backwards from A[i-1] down to A[0]. ________ entries to the _________ until the proper place for v is _______, and _______ v.A[0]A[i-1]A[i]A[i+1] A[n]v>v<vv ______ here Must ________ this partunsortedJ. Michael MooreInsertion SortMore detail:•At each entry j in that range, ________ v to A[j].•If A[j]>v, then v goes _______________________ A[j]; keep shifting -- value in A[j] is moved to A[j+1].•If A[j]<v, then v goes just after A[j], so v is put in A[j+1].•If we _____________ the end of the array, then v is __________ than anything in the range, so v goes in A[0].A[0]A[i]A[i+1] A[n-1]v>v<vsortedunsortedJ. Michael MoorePascal Code for Insertion Sortprocedure insertionSort(var A:Number); var i,j:integer; var value:integer; begin for i := 2 to MAX do {start at second element in array} begin value := A[i]; { current value to insert } j := i - 1; { between A[i-1] and A[1] } while ((j >= 1) AND (A[j] > value)) do begin A[j+1] := A[j]; { shift to the right } j := j – 1 end; A[j+1] := value {Place value} end end;J. Michael MooreInsertion SortThe __________ running time for insertion sort is proportional to the ___________ of the _______________________ to be sorted O(___)A visualization: http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertionen.htmhttp://web.engr.oregonstate.edu/~minoura/cs162/javaProgs/sort/InsertSort.htmlNote: The array used by these sites is indexed from 0 to n-1, where the array used in these slides is indexed from 1 to n.J. Michael Mooreprocedure insertionSort(var A:Number); var i,j:integer; var value:integer; begin for i := 2 to MAX do {start at second element in array} begin value := A[i]; { current value to insert } j := i - 1; { between A[i-1] and A[1] } while ((j >= 1) AND (A[j] > value)) do begin A[j+1] := A[j]; { shift to the right } j := j – 1 end; A[j+1] := value {Place value} end end;Pascal Code for Insertion SortJ. Michael MooreModification for Practical usageprocedure insert(value: integer; var A:Number; i: integer); var j: integer; begin j := i - 1; { between A[i-1] and A[1] } while ((j >= 1) AND (A[j] > value)) do begin A[j+1] := A[j]; { shift to the right } j := j – 1 end; A[j+1] := value {Place value} end;J. Michael MooreModification for Practical usageprocedure insertionSort(var A:Number); var i,j: integer; var value: integer; begin for i := 2 to MAX do {start at second element in array} begin value := A[i]; { current value to insert } insert(value, A, i); end end;J. Michael MooreBinary SearchRecall Linear Search… We started at one end and checked each valueWith ordered Data we can do ____________.We don’t have to look at _______ array element.sortedIs the _______ value _______ than what we are looking for?Not hereSomewhere in here!Let’s look in the ______: is it what we are looking for?YESNot hereSomewhere in here!NONOJ. Michael MooreBinary SearchRepeat the process until we find what we are looking for or failWe continue until we find what we are looking for, or run out of places to look thus failing to find a match.sortedIs the ______ value _______ than what we are looking for?YESNot hereNOLet’s look in the ______: is it what we are looking for?NONot here Here Not here Here J. Michael MooreBinary Search Implementationfunction binarySearch(A:Number; key:integer):integer; begin var low, high, mid: integer; var found:boolean; found := false; low = 1; high = MAX; while (low<=high) AND (NOT found) do begin mid = (low + high) div 2; if (A[mid] > key) then high = mid – 1 else if (A[mid] < key) then low = mid + 1 else found := true end; if found then binarySearch := mid else binarySearch := -1; end;J. Michael MooreBinary SearchRuns much _______ than linear search.The _______ running time for binary search is proportional to the ________ of the ________________ to be searched O(______)____ is defined as ______Linear search: O(______)Binary search:
View Full Document
Unlocking...