Может ли эта сортировка слиянием быть более эффективной? - PullRequest
Новая
       12

Может ли эта сортировка слиянием быть более эффективной?

0 голосов
/ 22 октября 2019

Я сделал сортировку слиянием в python, чтобы лучше понять, как она работает. Код работает нормально, но мне интересно, если кто-нибудь может критиковать то, что я написал. Может ли это быть более эффективным?
Я ожидаю, что в моей рекурсии есть место для улучшения - функция продолжает работать после вызова и запускается сама. Я предотвратил ненужное продолжение, просто возвращая его сразу после рекурсивного вызова, но я не уверен, что есть лучший метод.

Кроме того, я должен указать в выводе, что я хочуиндекс 0 возвращаемого значения, поскольку секция слияния функции генерирует многомерный массив. 

"""
2019-10-17

This project simply re-creates common sorting algorithms
for the purpose of becoming more intimately familiar with 
them.
"""

import random
import math

#Generate random array
array = [random.randint(0, 100) for i in range(random.randint(5, 100))]
print(array)

#Merge Sort
def merge(array, split = True):
    split_array = []
    #When the function is recursively called by the merging section, the split will be skipped
    continue_splitting = False
    if split == True:
        #Split the array in half
        for each in array:
            if len(each) > 1:
                split_array.append(each[:len(each)//2])
                split_array.append(each[len(each)//2:])
                continue_splitting = True
            else:
                split_array.append(each)
    if continue_splitting == True:
        sorted_array = merge(split_array)
        #A return is set here to prevent the recursion from proceeding once the array is properly sorted
        return sorted_array
    else:
        sorted_array = []
        if len(array) != 1:
            #Merge the array
            for i in range(0, len(array), 2):
                #Pointers are used to check each element of the two mergin arrays
                pointer_a = 0
                pointer_b = 0
                #The temp array is used to prevent the sorted array from being corrupted by the sorting loop
                temp = []
                if i < len(array) - 1:
                    #Loop to merge the array
                    while pointer_a < len(array[i]) or pointer_b < len(array[i+1]):
                        if pointer_a < len(array[i]) and pointer_b < len(array[i+1]):
                            if array[i][pointer_a] <= array[i + 1][pointer_b]:
                                temp.append(array[i][pointer_a])
                                pointer_a += 1
                            elif array[i + 1][pointer_b] < array[i][pointer_a]:
                                temp.append(array[i + 1][pointer_b])
                                pointer_b += 1
                        #If the pointer is equal to the length of the sub array, the other sub array will just be added fully
                        elif pointer_a < len(array[i]):
                            for x in range(pointer_a, len(array[i])):
                                temp.append(array[i][x])
                                pointer_a += 1
                        elif pointer_b < len(array[i + 1]):
                            for x in range(pointer_b, len(array[i + 1])):
                                temp.append(array[i + 1][x])
                                pointer_b += 1
                else:
                    for each in array[i]:
                        temp.append(each)
                sorted_array.append(temp)
            if len(sorted_array) != 1:
                #Recursively sort the sub arrays
                sorted_array = merge(sorted_array, False)
    return sorted_array


sorted_array = merge([array])[0]
print()
print(sorted_array)
...