Python의 QuickSort - 입력 크기가 더 커지면 프로그램이 멈 춥니 다.

Question

작은 테스트 케이스 (N = 20)에 대해 올바른 논리 출력을 확인했기 때문에 혼란스러워졌습니다. 나는 N = 10,000의 숫자를 시도하고 프로그램이 멈 춥니 다. 이유를 이해하지 못합니다 ... 가능한 한 간단하게 알고리즘을 구현했습니다.

또한 N = 10k 목록에서 sorted(data)을 호출하면 거의 즉시 작동하는 것으로 보입니다. 그래서 나는 알고리즘이 어딘가에 갇혀 있다고 확신합니다. 그래서 나는 꽤 왜 이런 일이 수에로 잃었어요

def QuickSort(array): 
    qsort(array, 0, len(array)) 


def qsort(arr, left, right): 
    if ((right - left) < 2): 
     return 

    pivotIndex = choosePivot0(arr, left, right) 

    newPivotIndex = partition(arr, pivotIndex, left, right) 

    qsort(arr, 0, newPivotIndex) 
    qsort(arr, newPivotIndex + 1, right) 

def partition(arr, pivotIndex, left, right): 
    swap(arr, pivotIndex, left) 
    pivot = arr[left] 
    i = left + 1 
    for j in range(left+1, right): 
     if (arr[j] < pivot): 
      swap(arr, i, j) 
      i = i + 1 

    swap(arr, left, i-1) #put pivot back where it belongs 
    #cobj.count = cobj.count + (right - left - 1) #add m-1 the #of comparisons 
    return (i-1) #give back where the pivot resides 



def swap(array, i, j): 
    temp = array[i] 
    array[i] = array[j] 
    array[j] = temp 

def choosePivot0(array, left, right): 
    return randint(left, right-1) #random 

: 여기

는 코드입니다. 어떤 도움을 주셔서 감사합니다.

Answer 1

는 다음 줄에 오타가있는 것 같습니다.

qsort(arr, left, newPivotIndex) 

그렇지 않으면이 기능은 일부 입력 데이터 세트에서만 작동합니다. 이것이 알고리즘이 멈추는 이유입니다.

Answer 2

참고 : 알고리즘을 검사하지 않아서 문제가있을 수 있습니다./파이썬은 어떤 이유로 든 마음에 들지 않을 수 있지만 : 빠른 정렬은 N^2에서 N log (N) , 입력 데이터에 따라 N^2만큼 나쁠 수도 있습니다. N = 20에 비해 N = 10,000 인 최적의 데이터를 사용하면 40,000/26 = 1538 배 느려질 수 있습니다. 아마도 그것은 단지 처리 중일 것입니다.

최악의 경우 데이터는 100,000,000/400 = 25,000 배 더 느립니다. 당신의 데이터는 무엇입니까?

Answer 3

파이썬은 심층 재귀 함수에서 종종 멈추는 경우가 있습니다. 현재 세션을 종료하는 경우 (IDLE에서 시도하는 경우), 출력을 전혀주지 않고 새로운 세션을 시작합니다. 이것을 시도하십시오 : import sys; sys.setrecursionlimit(2**30), 이것이 항상 도움이 될 수 있습니다.

qsort(arr, 0, newPivotIndex) 

내가 이렇게해야한다고 생각 :