Download Download Presentation Merge sort, Insertion sort

# Merge sort, Insertion sort

Download Presentation ## Merge sort, Insertion sort

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -
##### Presentation Transcript

1. Merge sort, Insertion sort

2. Sorting • Selection sort or bubble sort • Find the minimum value in the list • Swap it with the value in the first position • Repeat the steps above for remainder of the list (starting at the second position) • Insertion sort • Merge sort • Quicksort • Shellsort • Heapsort • Topological sort • …

3. Bubble sort and analysis • Worst-case analysis: N+N-1+ …+1= N(N+1)/2, so O(N^2) for (i=0; i<n-1; i++) { for (j=0; j<n-1-i; j++) { if (a[j+1] < a[j]) { // compare the two neighbors tmp = a[j]; // swap a[j] and a[j+1] a[j] = a[j+1]; a[j+1] = tmp; } } }

4. Insertion: • Incremental algorithm principle • Mergesort: • Divide and conquer principle

5. Insertion sort 1) Initially p = 1 2) Let the first p elements be sorted. 3) Insert the (p+1)th element properly in the list (go inversely from right to left) so that now p+1 elements are sorted. 4) increment p and go to step (3)

6. Insertion Sort

7. Insertion Sort see applet http://www.cis.upenn.edu/~matuszek/cse121-2003/Applets/Chap03/Insertion/InsertSort.html • Consists of N - 1 passes • For pass p = 1 through N - 1, ensures that the elements in positions 0 through p are in sorted order • elements in positions 0 through p - 1 are already sorted • move the element in position p left until its correct place is found among the first p + 1 elements

8. Extended Example To sort the following numbers in increasing order: 34 8 64 51 32 21 p = 1; tmp = 8; 34 > tmp, so second element a is set to 34: {8, 34}… We have reached the front of the list. Thus, 1st position a = tmp=8 After 1st pass: 8 34 64 51 32 21 (first 2 elements are sorted)

9. P = 2; tmp = 64; 34 < 64, so stop at 3rd position and set 3rd position = 64 After 2nd pass: 8 34 64 51 32 21 (first 3 elements are sorted) P = 3; tmp = 51; 51 < 64, so we have 8 34 64 64 32 21, 34 < 51, so stop at 2nd position, set 3rd position = tmp, After 3rd pass: 8 34 51 64 32 21 (first 4 elements are sorted) P = 4; tmp = 32, 32 < 64, so 8 34 51 64 64 21, 32 < 51, so 8 34 51 51 64 21, next 32 < 34, so 8 34 34, 51 64 21, next 32 > 8, so stop at 1st position and set 2nd position = 32, After 4th pass: 8 32 34 51 64 21 P = 5; tmp = 21, . . . After 5th pass: 8 21 32 34 51 64

10. Analysis: worst-case running time • Inner loop is executed p times, for each p=1..N  Overall: 1 + 2 + 3 + . . . + N = O(N2) • Space requirement is O(N)

11. The bound is tight • The bound is tight (N2) • That is, there exists some input which actually uses (N2) time • Consider input as a reversed sorted list • When a[p] is inserted into the sorted a[0..p-1], we need to compare a[p] with all elements in a[0..p-1] and move each element one position to the right (i) steps • the total number of steps is (1N-1i) = (N(N-1)/2) = (N2)

12. Analysis: best case • The input is already sorted in increasing order • When inserting A[p] into the sorted A[0..p-1], only need to compare A[p] with A[p-1] and there is no data movement • For each iteration of the outer for-loop, the inner for-loop terminates after checking the loop condition once => O(N) time • If input is nearly sorted, insertion sort runs fast

13. Summary on insertion sort • Simple to implement • Efficient on (quite) small data sets • Efficient on data sets which are already substantially sorted • More efficient in practice than most other simple O(n2) algorithms such as selection sort or bubble sort: it is linear in the best case • Stable (does not change the relative order of elements with equal keys) • In-place (only requires a constant amount O(1) of extra memory space) • It is an online algorithm, in that it can sort a list as it receives it.

14. An experiment • Code from textbook (using template) • Unix time utility

15. Mergesort Based on divide-and-conquer strategy • Divide the list into two smaller lists of about equal sizes • Sort each smaller list recursively • Merge the two sorted lists to get one sorted list

16. Mergesort • Divide-and-conquer strategy • recursively mergesort the first half and the second half • merge the two sorted halves together

17. see applet http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/MSort.html

18. How do we divide the list? How much time needed? How do we merge the two sorted lists? How much time needed?

19. How to divide? • If an array A[0..N-1]: dividing takes O(1) time • we can represent a sublist by two integers left and right: to divide A[left..Right], we compute center=(left+right)/2 and obtain A[left..Center] and A[center+1..Right]

20. How to merge? • Input: two sorted array A and B • Output: an output sorted array C • Three counters: Actr, Bctr, and Cctr • initially set to the beginning of their respective arrays (1)   The smaller of A[Actr] and B[Bctr] is copied to the next entry in C, and the appropriate counters are advanced (2)   When either input list is exhausted, the remainder of the other list is copied to C

21. Example: Merge

22. Example: Merge... • Running time analysis: • Clearly, merge takes O(m1 + m2) where m1 and m2 are the sizes of the two sublists. • Space requirement: • merging two sorted lists requires linear extra memory • additional work to copy to the temporary array and back

23. Analysis of mergesort Let T(N) denote the worst-case running time of mergesort to sort N numbers. Assume that N is a power of 2. • Divide step: O(1) time • Conquer step: 2 T(N/2) time • Combine step: O(N) time Recurrence equation: T(1) = 1 T(N) = 2T(N/2) + N

24. Analysis: solving recurrence Since N=2k, we have k=log2 n

25. Don’t forget: We need an additional array for ‘merge’! So it’s not ‘in-place’!
{"ft_lang_label":"__label__en","ft_lang_prob":0.80289704,"math_prob":0.9721362,"size":5418,"snap":"2023-14-2023-23","text_gpt3_token_len":1618,"char_repetition_ratio":0.12246029,"word_repetition_ratio":0.01848249,"special_character_ratio":0.3224437,"punctuation_ratio":0.11158799,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9965735,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,null,null,null,null,2,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-09T17:39:50Z\",\"WARC-Record-ID\":\"<urn:uuid:189f75cf-b176-431d-be75-cdc86bec0263>\",\"Content-Length\":\"96051\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:9a223be7-e92e-42f7-a049-ca3ae752b721>\",\"WARC-Concurrent-To\":\"<urn:uuid:83692257-a9f3-4446-bbaf-affa7aae779b>\",\"WARC-IP-Address\":\"52.34.250.221\",\"WARC-Target-URI\":\"https://www.slideserve.com/nfawcett/merge-sort-insertion-sort-powerpoint-ppt-presentation\",\"WARC-Payload-Digest\":\"sha1:P67GICNLZ5U2RBT5ZMLBWGG36RYFC443\",\"WARC-Block-Digest\":\"sha1:4RGLDLF543MFHIGHWXMZ4KRV6ZITNOQK\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224656788.77_warc_CC-MAIN-20230609164851-20230609194851-00310.warc.gz\"}"}