Merge Sort

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

MERGESORT : 

1 MERGESORT The elements are to be sorted in ascending order Procedure MERGESORT (low, high) // A (low : high) is a global array whose elements are to be sorted // integer low, high if low< high then mid?+(low + high)/2+ call MERGESORT (low,mid) call MERGESORT (mid+1, high) call MERGE (low, mid, high) endif end MERGESORT

MERGESORT (Contd..) : 

2 MERGESORT (Contd..) Procedure MERGE (low, mid, high) // The sorted arrays A (low : mid) and A (mid+1, high) are merged // // into a single array A (low : high) .An auriliary array B is used // integer h, i, j, k global A (low : high) ; local B(low : high) h?low ; i?low ; j?mid+1 // h is used for A (low : mid) and // // i is used for A (mid+1, high) // while h<=mid and j<=high do if A(h) <= A(j) then B(i)?A(h) ; h?h+1 else B(i)?A(j) ; j?j+1 Endif i?i+1 repeat

MERGESORT (Contd..) : 

3 MERGESORT (Contd..) if h>mid then for m?j to high do B(i) ? A(k); i? i+1 repeat // elements in second array are left // else for k?h to mid do B(i)?A(k) ; i?i+1 repeat // elements in 1st array are left // endif for k?low to high do A(k)?B(k) repeat end MERGE

MERGESORT EXAMPLE : 

4 MERGESORT EXAMPLE Example:Consider the array A = (310, 285,179, 652, 351, 423, 861, 254, 450,520) (310, 285, 179, 652, 351) (423, 861, 254, 450,520) (310, 285, 179) ( 652, 351) (423, 861, 254) (450, 520) (310,285) (179) (652,351) (450,520) (310)(285) (351, 652) (423, 861) (254) (285,310) (179) (423) (861) (254) 179 285 310 (423) (861) (254)

MERGESORT (Contd..) : 

5 MERGESORT (Contd..) A(1:5) is (179 285 310 351 652) (254 423 861) (450 520) (254 423 861) (450) (520) A(6:10) is (254 423 450 520 861) A(1:5) and A(6:10) are merged to get (179 254 285 310 351 423 450 520 652 861)

MERGESORT (Contd..) : 

6 MERGESORT (Contd..) The tree of recursive calls of merge sort for n=10 1,10 Tree of calls of Merge 1,5 6,10 1,1,2 6,6,7 1,3 4,5 6,8 9,10 1,2,3 4,4,5 6,7,8 9,9,10 1,2 3,3 4,4 5,5 1,3,5 6,8,10 6,7 8,8 9, 9 10,10 1,5,10 1,1 2,2 6,6 7,7

MERGESORT (Contd..) : 

7 MERGESORT (Contd..) Merge (6,6,7) merges A (6, 6), A (7, 7) Merge (1, 1, 2) merges A (1, 1), A (2, 2) Merge (1, 2, 3) merges A (1, 2), A(3, 3)

Computing time for mergesort : 

8 Computing time for mergesort T(n) = a n=1 ‘a’ is a constant = 2T(n/2)+cn n>1 ‘c’ is a constant Suppose n is a power of two n=2k T(n) = 2(2T(n/4)+cn/2)+cn = 4T(n/4)+2cn = 4[2T(n/8)+cn/4]+2cn = ……..=2kT(n/2k)+kcn = an+cn log2n (? n=2k ) If 2k < n ? 2k+1 Then T(n) ? T (2k+1) Therefore T (n) = 0 (n log2n)

MERGESORT (Contd..) : 

9 MERGESORT (Contd..) No sorting algorithm based on comparisons can have less than O (n log n) complexity But some inefficiencies in mergesort are to be removed. Merge sort uses 2n locations for n elements. Each call of merge copies B (low : high) back into A (low : high). An alternative to copying is to associate a link field with each key. Then merging proceeds by changing link values without moving the records.

MERGESORT (Contd..) : 

10 MERGESORT (Contd..) Along with array A, we require auxiliary array link (1 : n) containing integers 0 to n which are pointers to elements of A. Example: Suppose Q and R are two lists with Q = 2 and R = 5 are pointers to start of each list with the following set of values for Link. Link: (1) (2) (3) (4) (5) (6) (7) (8) 6 4 7 1 3 0 8 0 Then Q = (2, 4, 1, 6) and R = (5, 3, 7, 8) Then A (2) ? A (4) <= A (1) <= A (6) and A(5) <= A (3) <= A (7) <= A (8)

MERGESORT (Contd..) : 

11 MERGESORT (Contd..) Mergesort with inclusion of Insertion sort is as follows: Procedure MERGESORT (low, high, p) // Link (low : high) is used along // // with A (low : high) // // P is set to point to the beginning // // of the list // // global A (low : high), Link (low : high) if high – low + 1 < 16 then call Insertionsort (A, Link, low, high, p) else mid?+low+high+/2 call MERGESORT (low, mid, q) call MERGESORT (mid+1, high, r) call MERGE1 (q, r, p) endif end MERGESORT1

MERGESORT (Contd..) : 

12 MERGESORT (Contd..) Procedure MERGE1 (q, r, p) // q and r are pointers to lists // // contained in the global array Link (0 : n)// // p points to the final sorted list // // zero terminates a list // global n, A (1 : n), Link (0 : n) local i, j, k while i ? 0 do // while both // // lists are non empty //

MERGESORT (Contd..) : 

13 MERGESORT (Contd..) if A(i) <= A(j) then Link (k)?i ; k?i; i?Link (i) // shift to next // else Link (k)?j ; k?j ; j?Link (j) endif repeat if i = 0 then link (k)?j // The second list has still // // elements // else link (k)?i // first list // // has still elements // Link (2) ? 3 endif Link (3) ? 4 P ? Link (0) Link (4) ? 1 End MERGE1 Link (1) ? 0

MERGESORT (Contd..) : 

14 MERGESORT (Contd..) Example :( 10 25 30 50 ) ( 15 70 ) 2 5 Let the list be 50 10 25 30 15 70 35 55 1 2 3 4 5 6 7 8 q ? 2 r ? 5 i ? 2 j ? 5 k ? 0 A(2) < A(5) so Link (0) ? 2 ; k ? 2 i ? i+1 = 3 A(3) > A(5) so Link (2) ? 5, k ? 5 j ? 5+1 = 6 A(3) = 25 < A(6) = 70 Link (5) ? 3 k ? 3 ; i ? 4

MERGESORT (Contd..) : 

15 MERGESORT (Contd..) A(k) < A(6) so Link (3) ? 4 k ? 4 i ? Link (4) i.e. i ? 1 A(1) = 50 < A(j) = A(6) = 70 Link (k) ? 1 k ? 1 i ? Link (1) = 0 i = 0 so Link (1) ? 6 p ? Link (0) = 2

INSERTION SORT : 

16 INSERTION SORT The basic idea of Insertion Sort for the items A (1 : n) is as follows: A (1) is already sorted for j?2 to n do place A(j) in its correct position in the sorted set A(1 : j-1) repeat.

INSERTION SORT (Contd..) : 

17 INSERTION SORT (Contd..) Procedure Insertion sort (A, n) // Arrange in non decreasing order // A(0) ? -infinity // create a smallest // // value to exit while loop // for j?2 to n do // A(1 : j-1) is sorted // item?A(j) ; i?j-1 while item < A(i) do // 0<=i<j // A (i+1)?A(i) ; i?i-1 Repeat A (i+1)?item Repeat End Insertion sort

INSERTION SORT (Contd..) : 

18 INSERTION SORT (Contd..) Example: Sort A = ( 15, 10, 5, 6, 8 ) 1, 2, 3, 4, 5 n = 5 A(0) = - ? 15 is already sorted Now j?2 item?A(2) = 10 10 is to be inserted in (15) i?j-1 = 1 item = 10 < A(i) = 15 so A(i+1 = 2)?A(i) i?1-1=0 Now item>A(1) = - ? so while loop is exited and A(0+1)=A(1)?item

INSERTION SORT (Contd..) : 

19 INSERTION SORT (Contd..) So, the current sorted list is (10, 15) Now j?3 item?A(j) =5 5 is to be inserted in (10 15) i?2, item=5<A(1)=15 so A(i+1)=A(3)?A(i)=15, i?2-1=1 item=5<A(i)=10 so A(2)?10 i?0, item = 5 >A(0) = - ? so A(1)?5 Similarly 6 is inserted at 2nd place and 8 at 3rd place So, final sorted list is (5, 6, 8, 10, 15)

ANALYSIS OF INSERT : 

20 ANALYSIS OF INSERT The statement within while loop is executed zero upto maximum j times. The worst case time is bounded by ? j = (n(n+1))/2 -1 = 0(n2) 2?j?n The best case computing time is ? (n) (i.e. lower bound) when the date is already in sorted order. In this while loop is never entered.

QUICK SORT : 

21 QUICK SORT In Quick Sort, the division into sub lists is made such that the sorted sub lists do not need to be merged. This is accomplished by rearranging the elements in such a way that A(i) ? A(j) ? i between 1 and m and ? j between m+1 and n where 1 ? m ? n. The elements of A(1 : m) and A(m+1 : n) are independently sorted.

OUICK SORT (Contd..) : 

22 OUICK SORT (Contd..) Procedure partition (m, p) // this procedure partitions elements A(m)…A(p-1) // such that all the elements to the left of a partition element, called pivot are less than it and those on right are greater than it // // Initially the pivot is chosen as A(m) // // After partitioning if pivot is at q, A(q) is stored in A(p) so, the pivot position is fixed at p //

OUICK SORT (Contd..) : 

23 OUICK SORT (Contd..) integer m, p, i ; global A(m : p) v?A(m) ; i?m // Let A(m) be the pivot // loop loop i?i+1 until A(i) ? v repeat // finds element ? v, moving L to R // loop p?p-1 until A(p) ? v repeat

OUICK SORT (Contd..) : 

24 OUICK SORT (Contd..) // finds element? v, moving R to L if i< p then call Interchange (A(i), A(p)) else exit endif Repeat A(m)?A(p) ; A(p)?v // the correct position for pivot A(m) is found at p // // so pivot is shifted to A(p) // // whatever element was at position p i.e. A(p) has to be stored in ex-pivot’s position A(m) //

OUICK SORT (Contd..) : 

25 OUICK SORT (Contd..) Example : Consider 65 70 75 80 85 60 55 50 45 infinity (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i=2 p=9 v?65 After First iteration Interchanging A(2) & A(9) 65 45 75 80 85 60 55 50 70 ? After next iteration i?3 p?8 Interchanging A(3) & A(8) 65 45 50 80 85 60 55 75 70

OUICK SORT (Contd..) : 

26 OUICK SORT (Contd..) i?5 p?6 so 45 50 55 60 85 80 75 70 i?6 p?5 i ? p so while loop is exited and v = 65 is shifted to 5th position and A(5) is moved to First position. 60 45 50 55 65 85 80 75 70 ? ?

OUICK SORT (Contd..) : 

27 OUICK SORT (Contd..) Procedure QUICK SORT (p, q) // sorts the elements A(p)….A(q) which // reside in A(1 : n), A(n+1)? + infinity// integer p, q, ; global n, A(1 : n) if p<q then j?q+1 call partition (p, j) // j is the position // call quicksort (p, j-1) // of the partition // call quicksort (j+1, q) // element // endif end QUICK SORT

OUICK SORT (Contd..) : 

28 OUICK SORT (Contd..) 60 70 75 80 85 60 55 50 45 + ? p?1, q?9, j?9+1 =10 1<9, partition (1, 10) returns j?5 45 50 55 65 85 80 35 70 + ? quick sort (1, 4) and quick sort (6, 9) are called

OUICK SORT (Contd..) : 

29 OUICK SORT (Contd..) For quick sort (1, 4) p?1 q?4 p<q ? j?4+1 = 5 Partition (1, 5) returns j?4 55 45 50 60 65 quick sort (1,3) and quick sort (5,4) are called quick sort (5,4) returns array (A(5), A(4)) as it is (60, 65) ( A(4) and A(5) are in their positions in the final sorted array)

OUICK SORT (Contd..) : 

30 OUICK SORT (Contd..) quick sort (1,3) p?1, q?3, p<q j?4 partition (1, 4) returns j?3 45 55 60 so quicksort (1,2) and quicksort (3,3) returns A(3) in its current position quick sort (1,2) p?1, q?2 p<q so j?3 Partion (1,3) returns j ? 2 with the array 50 55 so quicksort (1,1) and quicksort (2,2) are called and return A(1), A(3), A(2) in their positions in final array.

WORST CASE ANALYSIS OF QUICK SORT : 

31 WORST CASE ANALYSIS OF QUICK SORT Let the worst case number of comparison be C?(n). Let r be the number of element comparisons in PARTITION. At first level of recursion, only one call to PARTITION (1, n+1) is made. So r = n At level two, at most two calls are made, and r = n-1 At each level of recursion, O(r) comparisons are made.

WORST CASE ANALYSIS OF QUICK SORT (Contd..) : 

32 WORST CASE ANALYSIS OF QUICK SORT (Contd..) At each level r is at least one less than the r at the previous level. Hence, C?(n) = ?r = 0(n2) 2?r?n