पायथन में क्विकसार्ट - कार्यक्रम बड़े इनपुट आकार के लिए लटकता है?

Question

इस बारे में बहुत उलझन में है क्योंकि मैंने छोटे पर्याप्त टेस्टकेस (एन = 20) के लिए सही लॉजिकल आउटपुट सत्यापित किया है। मैं एन = 10,000 नंबर करने की कोशिश करता हूं और प्रोग्राम बस लटकता है और मुझे समझ में नहीं आता क्यों ... मैंने एल्गोरिदम को जितना संभव हो उतना लागू किया है।

इसके अलावा, मेरी एन = 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

नोट: मैं अपने एल्गोरिथ्म जाँच नहीं की है तो वहाँ शायद यह कोई समस्या हो/अजगर यह किसी कारण के लिए पसंद नहीं है लेकिन: त्वरित तरह लगभग एन^2-समय छँटाई एन लॉग में सुधार होगा (एन) , लेकिन इनपुट डेटा के आधार पर शायद एन^2 के रूप में खराब हो सकता है। इष्टतम डेटा के साथ, एन = 20 की तुलना में एन = 10,000, 40,000/26 = 1538 गुना धीमा होगा। शायद यह सिर्फ प्रसंस्करण कर रहा है?

सबसे खराब केस डेटा के साथ यह 100,000,000/400 = 25,000 गुना धीमा होगा। आपका डेटा क्या है?

Answer 3

पायथन अक्सर गहरे रिकर्सिव फ़ंक्शंस के लिए लटकता है, कभी-कभी यह केवल वर्तमान सत्र को समाप्त करता है (यदि आप इसे आईडीएलई में आज़मा रहे हैं), और कोई भी आउटपुट दिए बिना एक नया सत्र शुरू करता है। इसे आज़माएं: import sys; sys.setrecursionlimit(2**30), यह मदद नहीं कर सकता है, हालांकि हमेशा नहीं।

qsort(arr, 0, newPivotIndex) 

मुझे लगता है कि इस तरह से किया जाना चाहिए: