[PYTHON] Understand the process of merge sort. Finely disassemble following the flow.
What is merge sort?
A type of sort. Stable sort. It uses the divide-and-conquer method.
--Divide the array to be sorted into two ――Repeat the division into two until there is one element (divide) --Compare each leading element and merge with the smaller number forward (solve, merge) --Compare the first numbers of the sorted elements and merge them side by side (conquer, merge)
Reference: Kagoshima University HP
## Merge sort code
python
#Merge into the smallest unit after disassembling. Repeat this process
def merge_sort(arr):
#If the element is 1 or 0, the array is returned as it is. (Because there is no comparison target and there is no need for sorting)
if len(arr) <= 1:
return arr
#Divide into two. Extract only the integer part to separate by slicing
mid = len(arr)//2
#Divide the original array into two
arr1 = arr[:mid]
arr2 = arr[mid:]
#Continue splitting into two until the minimum unit
#Recursion ends when it becomes return
arr1 = merge_sort(arr1)
arr2 = merge_sort(arr2)
return merge1(arr1, arr2)
#Compare the two elements and put the smaller one first
def merge1(arr1,arr2):
#Array to put the merge result
merged = []
l_i, r_i =0,0
while l_i < len(arr1) and r_i < len(arr2):
if arr1[l_i] <= arr2[r_i]:
merged.append(arr1[l_i])
l_i += 1
else:
merged.append(arr2[r_i])
r_i += 1
if l_i < len(arr1):
merged.extend(arr1[l_i:])
if r_i < len(arr2):
merged.extend(arr2[r_i:])
return merged
Verification
list=[7,4,3,5,6,1,2]
merge_sort(list)
#[1, 2, 3, 4, 5, 6, 7]
## Merge sort details Since two functions are running, it is difficult to understand, so let's decompose it.
- Function to make the smallest unit (div_arr)
- A function (merge) that adds the smaller one to the array.
Function to make the smallest unit
First, consider a function that divides each element.
python
def div_arr(arr):
#If the element is 1 or 0, the array is returned as it is. (Because there is no comparison target and there is no need for sorting)
if len(arr) <= 1:
return print(arr)
#Divide into two. Extract only the integer part to separate by slicing
mid = len(arr)//2
#Divide the original array into two
arr1 = arr[:mid]
arr2 = arr[mid:]
#Continue splitting into two until the minimum unit
#Recursion ends when it becomes return
arr1 = div_arr(arr1)
arr2 = div_arr(arr2)
Verification
list=[7,4,3,5,6,1,2]
div_arr(list)
[7]
[4]
[3]
[5]
[6]
[1]
[2]
The point is to prepare two points, arr1 and arr2. The value input to the function is divided into two, and the processing is always stocked at the back (arr2).
Therefore, even after arr1 ends with return, it continues to be processed as much as arr2 is stocked.
I expected the array to be output with return arr, but since nothing is displayed, I set it toreturn print (arr). (I don't know why it doesn't appear ...)
### (Reference) When recursive processing is performed only in the front row
python
def div_arr(arr):
if len(arr) <= 1:
return print(arr)
mid = len(arr)//2
arr1 = arr[:mid]
arr1 = div_arr(arr1)
python
list=[7,4,3,5,6,1,2]
div_arr(list)
[7]
Since only arr1 is processed, only [7] is output.
- It does not become [7], [4], [3]. Because [4] and [3] are allocated to arr2 while repeating the recursive process.
## A function that adds the smaller one to the array
python
#Compare the two elements and put the smaller one first
def merge1(arr1,arr2):
#Array to put the merge result
#The initial value is 0, but the contents increase every time merge is repeated.
merged = []
#Initial value of array number of the element to be compared
l_i, r_i =0,0
#Loop end condition. Finish when comparing all of either array
while l_i < len(arr1) and r_i < len(arr2):
#If the front element is smaller
#If they are the same, give priority to the other party
if arr1[l_i] <= arr2[r_i]:
merged.append(arr1[l_i])
#Add 1 to the sequence number so that the same element is not verified again.
l_i += 1
else:
merged.append(arr2[r_i])
r_i += 1
#When the while statement is finished, add the whole unadded one to the answer.
#Since each array has already been sorted in ascending order, it is added as it is.
if l_i < len(arr1):
merged.extend(arr1[l_i:])
if r_i < len(arr2):
merged.extend(arr2[r_i:])
return merged
Verification
a=[2,3]
b=[1,8,9]
merge1(a,b)
#[1, 2, 3, 8, 9]
## Visualize the overall processing flow Let's take a look at the merge_sort process based on the above two processes.
python
#Array to sort
arr=[7,4,3,5,6]
#First process
arr1=[7,4]
arr2=[3,5,6]
#Recursive arr1
arr1`=[7]
arr2`=[4]
##Solution of arr1##
merge`=[4,7]
#Recursive arr2
arr1``=[3]
arr2``=[5,6]
#arr2``Recursive
arr1```=[5]
arr2```=[6]
##arr2``Solution of##
merge``=[5,6]
##Solution of arr2##
merge```=[3,5,6]
## Finally arr's solution ##
merge=[3,4,5,6,7]
## The solution of arr is a merge of arr1 and arr2
# arr1 solution merge` = [4,7]
#arr2 solution merge```=[3,5,6]
It's complicated. ** The last 3 lines are important **
python
arr1 = merge_sort(arr1)
arr2 = merge_sort(arr2)
return merge1(arr1, arr2)
Each time merge_sort, the merged value (result of merge1) goes into arr1 and arr2.
It will be merged further.
With this, the elements decomposed to the minimum unit are reassembled.
The person who thought this is amazing, and the person who understands this is amazing
Recommended Posts