Previous sort algorithm post
In this post, I will additionally study the sort algorithm that I studied last time.
Sorting algorithm
Merge Sort
Merge sort is an algorithm that divides the array into two groups, sorting them into two groups, and then merging them.
For example
An array called A is sorted 1, 2, 3, 5,
If an array called B is sorted 4, 6, 7, 8
This is how to sort these two sets by merging them.
First, let's understand how these two sets can be merged and sorted with an example.
[1, 2, 3, 5] # sorted array A
[4, 6, 7, 8] # sorted array B
[] # empty array C to concatenate two setsStep 1: [1, 2, 3, 5] ➜ [4, 6, 7, 8] Compare 1 and 4!
Since 1 < 4, we put 1 in C.
C:[1]Step 2: [1, 2, 3, 5] ➜ [4, 6, 7, 8] Compare 2 and 4!
Since 2 < 4, we put 2 in C.
C:[1, 2]Step 3: [1, 2, 3, 5] ➜ [4, 6, 7, 8] Compare 3 and 4!
Since 3 < 4, we put 3 in C.
C:[1, 2, 3]Step 4: [1, 2, 3, 5] ➜ [4, 6, 7, 8] Compare 5 and 4!
Since 5 > 4, we put 4 into C.
C:[1, 2, 3, 4]Step 5: [1, 2, 3, 5] ➜ [4, 6, 7, 8] Compare 5 and 6!
Since 5 < 6, we put 5 in C.
C:[1, 2, 3, 4, 5]
At this point, all elements of A are finished! Then, the element not included in B, What about [6, 7, 8]? Just add them to C one by one. C:[1, 2, 3, 4, 5, 6, 7, 8] Like this! Then I was able to sort by merging A and B.
Just apply the concept of divide and conquer.
Divide and conquer is a strategy in which a problem is broken into two smaller problems, each is solved, and then the results are pooled to solve the original problem.
For example, if you have an array [5, 4]
Think of this array as two smaller problems, each with an array of [5] and [4].
So what if you combine these two and sort them? This can end up being a whole sorted list.
Let's expand this concept a bit further.
Let's say you have an array [5, 3, 2, 1, 6, 8, 7, 4]. Splitting this array in half
[5, 3, 2, 1] becomes [6, 8, 7, 4]. If you split it in half
[5, 3][2, 1] [6, 8][7, 4] becomes. If you split it in half
[5][3] [2][1] [6][8] [7][4].
What would happen if we merged these arrays two by one?
Merging [5][3] into [3, 5][2] Merging [1] into [1, 2]
Merging [6][8] gives [6, 8]
Merging [7][4] gives [4, 7]
Then again!
Merging [3, 5] and [1, 2] gives [1, 2, 3, 5]
Merging [6, 8] and [4, 7] gives [4, 6, 7, 8]
Then again!
Merging [1, 2, 3, 5] and [4, 6, 7, 8] gives [1, 2, 3, 4, 5, 6, 7, 8] .
How is it? By breaking the problem down and solving the parts, the whole thing was solved!
This is called Divide and Conquer.
What code comes to mind when you repeat the same pattern like this?
The "recursive" code immediately comes to mind.
If you define a function in a self-contained form,
Let's say MergeSort(start point, end point).
then
MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))
can be said.
That is, in order to see it sorted from 0 to N,
It is the sum of those sorted from 0 to N/2 and those sorted from N/2 to N. is the concept.
As we saw earlier, combining [1, 2, 3, 5] and [4, 6, 7, 8] results in a sorted array!
Alright, now let's translate the above thoughts into code!
array = [5, 3, 2, 1, 6, 8, 7, 4]
def merge_sort(array):
if len(array) <= 1:
return array
mid = (0 + len(array)) // 2
left_array = merge_sort(array[:mid]) # left part sort
right_array = merge_sort(array[mid:]) # right part sort
merge(left_array, right_array) # add left and right array
def merge(array1, array2):
result = []
array1_index = 0
array2_index = 0
while array1_index < len(array1) and array2_index < len(array2):
if array1[array1_index] < array2[array2_index]:
result.append(array1[array1_index])
array1_index += 1
else:
result.append(array2[array2_index])
array2_index += 1
if array1_index == len(array1):
while array2_index < len(array2):
result.append(array2[array2_index])
array2_index += 1
if array2_index == len(array2):
while array1_index < len(array1):
result.append(array1[array1_index])
array1_index += 1
return result
print(merge_sort(array)) # [1, 2, 3, 4, 5, 6, 7, 8]
```python
array = [5, 3, 2, 1, 6, 8, 7, 4]
def merge_sort(array):
# 이 곳을 채워보세요!
return array
def merge(array1, array2):
result = []
array1_index = 0
array2_index = 0
while array1_index < len(array1) and array2_index < len(array2):
if array1[array1_index] < array2[array2_index]:
result.append(array1[array1_index])
array1_index += 1
else:
result.append(array2[array2_index])
array2_index += 1
if array1_index == len(array1):
while array2_index < len(array2):
result.append(array2[array2_index])
array2_index += 1
if array2_index == len(array2):
while array1_index < len(array1):
result.append(array1[array1_index])
array1_index += 1
return result
print(merge_sort(array)) # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!
print("Answer = [-7, -1, 5, 6, 9, 10, 11, 40] / result = ", merge_sort([-7, -1, 9, 40, 5, 6, 10, 11]))
print("Answer = [-1, 2, 3, 5, 10, 40, 78, 100] / result = ", merge_sort([-1, 2, 3, 5, 40, 10, 78, 100]))
print("Answer = [-1, -1, 0, 1, 6, 9, 10] / result = ", merge_sort([-1, -1, 0, 1, 6, 9, 10]))Reference
