Sorting Algorithms Heaps and MergesSorting AlgorithmSlide 3Heap SortSlide 5Slide 6Slide 7Slide 8Merge SortSlide 10Slide 11Slide 12Slide 13Slide 14HomeworkWork SitedSorting Sorting AlgorithmsAlgorithmsHeaps and MergesHeaps and MergesCOT 4810COT 4810Topics in Computer ScienceTopics in Computer ScienceAlbert ParkAlbert ParkFebruaryFebruary 55, 2008, 2008Sorting AlgorithmSorting AlgorithmList and elements(or records)List and elements(or records)Algorithm that puts elements of a list in a Algorithm that puts elements of a list in a specific orderspecific orderIncreasing or decreasingIncreasing or decreasingNumerical orderNumerical orderEfficient and optimizeEfficient and optimizeSorting AlgorithmSorting AlgorithmThe fastestThe fastestHeap and Merge sortHeap and Merge sortTime complexityTime complexityO(n log n)O(n log n)Stable (Heap) vs. Unstable (Merge)Stable (Heap) vs. Unstable (Merge)Heap SortHeap SortDef: A sort algorithm that builds a heap, Def: A sort algorithm that builds a heap, then repeatedly extracts the maximum then repeatedly extracts the maximum item. item. Complete tree Complete tree Proposed by J.W.J. Williams in 1964.Proposed by J.W.J. Williams in 1964.Implementation by Robert W. Floyd in Implementation by Robert W. Floyd in 1964.1964.Heap SortHeap SortPseudocodePseudocodeStart at the beginning root nodeStart at the beginning root nodeSet Set nn = length of the list = length of the listwhile while nn > 0 { > 0 {swap (list[0], list[swap (list[0], list[n-n-1])1])while start > while start > n {n { for node list[start] // usually start is the root nodefor node list[start] // usually start is the root node mm = min(ChildA, ChildB) // find the minimum = min(ChildA, ChildB) // find the minimum value of its value of its childchild if list[start] > if list[start] > mm then swap(list[start], list[ then swap(list[start], list[mm]) ]) and start = and start = mm otherwise break out of while loop otherwise break out of while loop }}nn = = nn-1 }-1 }Heap SortHeap SortExampleExampleFirst construct a First construct a heap.heap.Then sort the heap Then sort the heap tree.tree.101022449911Heap SortHeap SortExample cont.Example cont.102914Heap SortHeap SortExample cont.Example cont.149102Merge SortMerge SortDef: A sort algorithm that splits the Def: A sort algorithm that splits the items to be sorted into two groups, items to be sorted into two groups, recursively sorts each group, and recursively sorts each group, and merges them into a final, sorted merges them into a final, sorted sequence.sequence.Divide and ConquerDivide and ConquerMemoryMemoryMerge SortMerge SortPseudocodePseudocodesort(sort(ii, , jj): if ): if ii = = jj then return then returnelseelsekk = ( = (ii++jj)/2)/2sort(sort(ii, , kk)) sort(sort(kk+1, +1, jj))merge A(merge A(ii, , kk) and A() and A(kk+1, +1, jj))sort(1, sort(1, nn))Merge SortMerge SortPseudocodePseudocodemerge: merge: jj= = kk = 1 = 1for for ii = 1 to = 1 to nn if B( if B(jj) > C() > C(kk) then A() then A(ii) = B() = B(jj) ) and and jj = = jj+1+1 else A( else A(ii) = C() = C(kk) and ) and kk = = kk+1+1Merge SortMerge SortExampleExampleDivideDivideConquerConquer101022449911Merge SortMerge SortExample cont.Example cont.10102244991110102244991110102244111010991199224422101044Merge SortMerge SortExample cont.Example cont.224410101199112244991010HomeworkHomeworkList 1 [3, 6, 4, 1, 5, 9, 2, 8]List 1 [3, 6, 4, 1, 5, 9, 2, 8]1. Sort the list above by using heapsort.1. Sort the list above by using heapsort.2. Sort the list above by using 2. Sort the list above by using mergesort.mergesort.3. What is the time complexity for both 3. What is the time complexity for both heap and merge sorts?heap and merge sorts?Work SitedWork SitedDewdney, A.K. Dewdney, A.K. The New Turing Omnibus.The New Turing Omnibus. New York: Computer Science Press, 1989.New York: Computer Science Press, 1989.Belzer, Jack Belzer, Jack Encyclopedia of Computer Encyclopedia of Computer Science and Technology.Science and Technology. New York: New York: Marcel Dekker, INC., 1994.Marcel Dekker, INC., 1994.Black, Black, Paul E. "heapsort", in Paul E. "heapsort", in Dictionary of Algorithms and Data StructuDictionary of Algorithms and Data Structuresres [online], Paul E. Black, ed., [online], Paul E. Black, ed., U.S. National Institute of Standards and U.S. National Institute of Standards and TechnologyTechnology. 14 May 2007. . 14 May
View Full Document
Unlocking...