Я только что попытался создать алгоритм сортировки слиянием. Я сравнил его с тем, что нашел на Geeks для Geeks, и они не очень похожи. Интересно, правильно ли я сделал алгоритм сортировки слиянием или я создал другой алгоритм? Оба алгоритма одинаково эффективны, поэтому я думаю, что какая-то часть алгоритма верна?
import random
import copy
import time
data_size = 10000
unsorted_array = random.sample(range(0, data_size), data_size)
# My version
def mergeSort(arr):
split = []
# Takes two and two elements from the array
# It then puts the smallest item first in the new
# Returns an array consisting of smaller subarrays with two items each
for i in range(len(arr) // 2):
if arr[2*i] > arr[2*i+1]:
arr[2*i], arr[2*i+1] = arr[2*i+1], arr[2*i]
split.append([arr[2*i], arr[2*i+1]])
# If the number of items are odd
if len(split) != len(arr) / 2:
split.append([arr[-1]])
result = divide(split)
print(result)
def divide(arr):
i = 0
new_arr = []
# Merges two and two parts of the array
while i < len(arr) // 2:
new_arr.append(merge(arr[2*i], arr[2*i+1]))
i += 1
# The original array had an odd
# number of element
if len(new_arr) != len(arr) / 2:
new_arr.append(arr[-1])
# The array is not fully merged
# The process must be repetead
if len(new_arr) != 1:
new_arr = divide(new_arr)
#Return the final array
return new_arr
def merge(left, right):
merged = []
total_len = len(left) + len(right)
left_i = 0
right_i = 0
while len(merged) != total_len: # Repeat until all elements of org. is merged
if left_i < len(left): # Check if all elements of left array has been added
if right_i < len(right): # Check if all elements of right array has been added
# Add the smallest element to the merged list
if right[right_i] > left[left_i]:
merged.append(left[left_i])
left_i += 1
else:
merged.append(right[right_i])
right_i += 1
else: # Add left element, all right elements have been added
merged.append(left[left_i])
left_i += 1
else: # Add right array element, all left elements have been added
merged.append(right[right_i])
right_i += 1
return merged
# From GeeksForGeeks
def mergeSort_web(arr):
if len(arr) > 1:
mid = len(arr) // 2 #Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves
mergeSort_web(L) # Sorting the first half
mergeSort_web(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
start_time = time.time()
#mergeSort(unsorted_array)
mergeSort_web(unsorted_array)
# print(unsorted_array) # Only enable for the web version
print("--- %s seconds ---" % (time.time() - start_time))