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
bet45/147
Sana17.06.2023
Hajmi1.48 Mb.
#1540634
1   ...   41   42   43   44   45   46   47   48   ...   147
Bog'liq
books-library.net-11301817Az7X6

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]



Download 1.48 Mb.

Do'stlaringiz bilan baham:
1   ...   41   42   43   44   45   46   47   48   ...   147




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling