QuickSort не работает с более чем 2000 элементов. Зачем? - PullRequest
Новая
       26

QuickSort не работает с более чем 2000 элементов. Зачем?

0 голосов
/ 29 мая 2019

Если я хочу выполнить сортировку по следующему алгоритму быстрой сортировки, я получаю либо ошибку «RecursionError: максимальная глубина рекурсии превышена в сравнении», либо, если я устанавливаю предел рекурсии намного выше, Python перестает работать после сортировки через BubbleSort с (Process Закончено с кодом выхода -1073741571 (0xC00000FD)). У кого-нибудь есть идея, как я могу решить эту проблему

Установить предел рекурсии выше 

import time
import random
from sys import setrecursionlimit
#setrecursionlimit(1000000)

#------------------------------Sortieralgorithmen-----------------------------------------------
#-----------------------------------------------------------------------------------------------

def bubbleSort(array):

    length = len(array)

    for sorted in range(length):

        for j in range(0, length-sorted-1):
            if array[j] > array[j+1] :
                array[j], array[j+1] = array[j+1], array[j]



def help(array, low, high):
    pivot = array[low]
    fromhigh = high
    fromlow = low
    while True:
        while(array[fromhigh]>pivot):
            fromhigh = fromhigh-1
        while(array[fromlow]<pivot):
            fromlow = fromlow+1
        if(fromlow<fromhigh):
            array[fromlow], array[fromhigh] = array[fromhigh], array[fromlow]
        else:
            return fromhigh


def quickSort(array, low, high):
   if (low<high):
       pivot = help(array, low, high)
       quickSort(array, low, pivot)
       quickSort(array, pivot + 1, high)




#--------------------------------Zeitmessung-----------------------------------------------------
#------------------------------------------------------------------------------------------------

numb_elements = 6000

sortedarray = []
for i in range (0,numb_elements):
    sortedarray.append(i)

notsortedarray = random.sample(range(0,numb_elements),numb_elements)

copy1 = sortedarray.copy()
before = time.time()
bubbleSort(copy1)
after = time.time()
total = after-before
print("Bubblesort sortiertes Array:\t\t" + str(total))

copy2 = notsortedarray.copy()
before = time.time()
bubbleSort(copy2)
after = time.time()
total = after-before
print("Bubblesort nicht sortiertes Array:\t" + str(total))

copy3 = sortedarray.copy()
before = time.time()
quickSort(copy3, 0, len(copy3)-1)
after = time.time()
total = after-before
print("QuickSort sortiertes Array:\t\t\t" + str(total))

copy4 = notsortedarray.copy()
before = time.time()
quickSort(copy4, 0, len(copy4)-1)
after = time.time()
total = after-before
print("QuickSort nicht sortiertes Array:\t" + str(total)+"\t (Worst Case)")

1 Ответ

1 голос
/ 29 мая 2019

Небольшая начальная трассировка показывает проблему: 

indent = ""

def quickSort(array, low, high):
   global indent
   # print(indent, "quickSort ENTER", low, high)
   indent += "  "
   if (low<high):
       pivot = help(array, low, high)
       print(low, high, pivot)
       quickSort(array, low, pivot)
       quickSort(array, pivot + 1, high)

   indent = indent[2:]

Увидев проблему со стеком, я вставил оператор print, который включает в себя сводную точку.Вывод: 

0 5999 0
1 5999 1
2 5999 2
3 5999 3
4 5999 4
5 5999 5
6 5999 6
...
994 5999 994
995 5999 995
996 5999 996
Traceback (most recent call last):
  File "so.py", line 79, in <module>
    quickSort(copy3, 0, len(copy3)-1)
  File "so.py", line 46, in quickSort
    quickSort(array, pivot + 1, high)
  File "so.py", line 46, in quickSort
    quickSort(array, pivot + 1, high)
  File "so.py", line 46, in quickSort
    quickSort(array, pivot + 1, high)
  [Previous line repeated 994 more times]
  File "so.py", line 43, in quickSort
    pivot = help(array, low, high)
  File "so.py", line 28, in help
    while(array[fromhigh]>pivot):
RecursionError: maximum recursion depth exceeded in comparison

Ваша проблема в том, что ваша логика сводки всегда возвращает младший элемент, который изменяет ваш алгоритм на O (N ^ 2) , умираякогда N больше допустимой глубины стека.

Можете ли вы взять его оттуда?Смотрите этот прекрасный debug блог за помощью.
Даже банальный print даст вам много подсказок.

...