Lecture Data Structures: Lesson 45

Lecture Data Structures: Lesson 45 provide students with knowledge about divide and conquer; binary search; mergesort; splits the list in half; mergesorts the two halves; merging animation; mergesort the right half; merge sort and linked lists;...
Nội dung trích xuất từ tài liệu:
Lecture Data Structures: Lesson 45LectureNo.45DataStructuresDr.SohailAslamDivideandConquer Whatifwesplitthelistintotwoparts? 10 12 8 4 2 11 7 5DivideandConquer Sortthetwoparts: 10 4 12 8 10 8 12 4 2 11 5 7 11 5DivideandConquer Thenmergethetwopartstogether: 24 48 10 5 12 7 82 10 5 11 7 11 12Analysis  Tosortthehalves(n/2)2+(n/2)2  Tomergethetwohalvesn  So,forn=100,divideandconquertakes: =(100/2)2+(100/2)2+100 =2500+2500+100 =5100 (n2=10,000)DivideandConquer  Whynotdividethehalvesinhalf?  Thequartersinhalf?  Andsoon...  Whenshouldwestop? Atn=1DivideandConquer Recall: Binary Search Search Search SearchDivideandConquer Sort Sort Sort Sort Sort Sort SortDivideandConquer Combine Combine CombineMergesort  Mergesortisadivideandconqueralgorithm thatdoesexactlythat.  Itsplitsthelistinhalf  Mergesortsthetwohalves  Thenmergesthetwosortedhalvestogether  MergesortcanbeimplementedrecursivelyMergesort  Themergesortalgorithminvolvesthreesteps: • Ifthenumberofitemstosortis0or1,return • Recursivelysortthefirstandsecondhalves separately • Mergethetwosortedhalvesintoasorted groupMerging:animation 4 8 10 12 2 5 7 11 2Merging:animation 4 8 10 12 2 5 7 11 2 4Merging:animation 4 8 10 12 2 5 7 11 2 4 5Merging 4 8 10 12 2 5 7 11 2 4 5 7Mergesort Splitthelistinhalf. Mergesortthelefthalf. 10 4 8 12 11 2 7 5 Splitthelistinhalf. Mergesortthelefthalf. 10 4 8 12 Splitthelistinhalf. Mergesortthelefthalf. 10 4 Mergesorttheright. 10 4Mergesort 10 4 8 12 11 2 7 5 10 4 8 12Mergesorttherighthalf. Mergethetwohalves. 10 4 10 4 8 12 Mergethetwohalves. 8 12Mergesort 10 4 8 12 11 2 7 5 Mergethetwohalves. 10 4 84 10 8 12Mergesorttherighthalf. Mergethetwohalves. 10 4 10 4 8 12MergesortMergesorttherighthalf. 4 8 10 12 11 2 7 5 11 2 7 5 11 2 11 2MergesortMergesorttherighthalf. 4 8 10 12 11 2 7 5 11 2 11 2 7 5 11 2 11 2