The Self-Taught Computer Scientist
Figure 4.1: The first part of a merge sort Introduction to Algorithms
Download 1.48 Mb. Pdf ko'rish
|
books-library.net-11301817Az7X6
- Bu sahifa navigatsiya:
- Chapter 4
Figure 4.1: The first part of a merge sort
Introduction to Algorithms 46 Lists containing one item are sorted by definition. Once you have sorted lists containing one item each, you merge your sublists two at a time by comparing the first item in each list. Merging your lists means combining them in sorted order. First, you merge [6] and [3], then you merge [9] and [2]. In this case, each list contains only one number, so you compare the two numbers and put the smallest number at the beginning of your new, merged list and the larger number at the end. Now, you have two sorted lists: [3, 6], [2, 9] Then, you merge these two lists: # unmerged [3, 6], [2, 9] #merged [] First, you compare 3 and 2. Since 2 is smaller, it goes into your merged list: # unmerged [3, 6], [9] #merged [2] Now you compare 3 and 9. Since 3 is smaller, it goes into your merged list: # unmerged [6], [9] #merged [2, 3] Finally, you compare 6 and 9. Since 6 is smaller, it goes into your merged list. Then, you put the 9 into the merged list: # unmerged [], [] #merged [2, 3, 6, 9] Now that you’ve finished all your merges, you have a single, sorted list. Here is how to implement a merge sort in Python: def merge_sort(a_list): if len(a_list) > 1: Chapter 4 Sorting Algorithms 47 mid = len(a_list) // 2 left_half = a_list[:mid] right_half = a_list[mid:] merge_sort(left_half) merge_sort(right_half) left_ind = 0 right_ind = 0 alist_ind = 0 while left_ind < len(left_half) and right_ind < len(right_half): if left_half[left_ind] <= right_half[right_ind]: a_list[alist_ind] = left_half[left_ind] left_ind += 1 else: a_list[alist_ind] = right_half[right_ind] right_ind += 1 alist_ind += 1 while left_ind < len(left_half): a_list[alist_ind]=left_half[left_ind] left_ind += 1 alist_ind += 1 while right_ind < len(right_half): a_list[alist_ind]= right_half[right_ind] right_ind += 1 alist_ind += 1 This part of your algorithm is responsible for breaking your lists into sublists: if len(a_list) > 1: mid = len(a_list) // 2 left_half = a_list[:mid] right_half = a_list[mid:] merge_sort(left_half) merge_sort(right_half) left_ind = 0 right_ind = 0 alist_ind = 0 This part is responsible for merging two lists: left_ind = 0 right_ind = 0 alist_ind = 0 while left_ind < len(left_half) and right_ind < len(right_half): if left_half[left_ind] <= right_half[right_ind]: a_list[alist_ind] = left_half[left_ind] |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling