Я создал алгоритм слияния - PullRequest
0 голосов
/ 14 апреля 2020

Я только что попытался создать алгоритм сортировки слиянием. Я сравнил его с тем, что нашел на 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))

1 Ответ

1 голос
/ 14 апреля 2020

Код, который вы написали, работает как сортировка слиянием. Тем не менее, он показывает некоторые отличия от веб-версии, которую вы разместили. Версия GeeksforGeeks работает рекурсивно, поэтому сначала вы отсортируете левую половину, а затем правую. В то время как ваш код работает снизу вверх, объединяя списки одинакового размера одновременно. Временная сложность двух одинакова, и основной принцип одинаков.

...