Как реализовать быструю сортировку по python? - PullRequest
Новая
       15

Как реализовать быструю сортировку по python?

0 голосов
/ 13 апреля 2020

возможно я следующий человек, который спрашивает, как правильно выпустить быструю сортировку на python. Но для меня важно знать, правильно ли я написал этот алгоритм, читая псевдокод из учебника «Основные алгоритмы: практический подход к компьютерным алгоритмам».

Когда я запускаю код, я получаю это сообщение. RecursionError: максимальная глубина рекурсии превышена в сравнении 

import random

def quickSort(arr, start, end):
    if start >= end:  # if len(arr) < 2
        return arr
    else:
        divideIndex = partition(arr, start, end)
        quickSort(arr, start, divideIndex - 1)
        quickSort(arr, divideIndex, end)

def partition(arr, head, tail):
    left = head
    right = tail
    pivot = arr[(head + tail) // 2]  # mid

    while right >= left:
        # looking through the array from the left
        while arr[left] <= pivot:
            left = left + 1
        # looking through the array from the right
        while arr[right] > pivot:
            right = right - 1
        # found a couple of elements that can be exchanged.
        if left <= right:
            swap(arr[right], arr[left])
            # move the left and right wall
            left = left + 1
            right = right - 1
    # return one elements if not found a couple
    return left

def swap(arr1, arr2):
    temp = arr1
    arr1 = arr2
    arr2 = temp

# Generator random variables
deck = list(range(50))
random.shuffle(deck)


start = 0
end = len(deck) - 1
print(quickSort(deck, start, end))

1 Ответ

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

Попробуйте это: 

def partition(arr,low,high): 
    i = ( low-1 )        
    pivot = arr[high]    

    for j in range(low , high): 


        if   arr[j] <= pivot: 

            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 

    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 


def quickSort(arr,low,high): 
    if low < high: 

        pi = partition(arr,low,high) 

        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high)
...