Python에서 빠른 정렬 구현

Question

빠른 정렬을 구현하려고합니다. 단순 해 보이고 작은 요소와 큰 요소가 두 개의 개별 목록에 모아 지도록 피벗 기능을 구현합니다. 목록이 일정 시간 내에 정렬 될 수있을 때까지 반복적으로 수행하십시오.

Traceback (most recent call last): 
    File "11.py", line 79, in <module> 
    print(quicksort(a)) 
    File "11.py", line 73, in quicksort 
    return quicksort(l1) + quicksort(l2) 
    File "11.py", line 73, in quicksort 
    return quicksort(l1) + quicksort(l2) 
    File "11.py", line 73, in quicksort 
    return quicksort(l1) + quicksort(l2) 
    [Previous line repeated 993 more times] 

Traceback (most recent call last): 
    File "11.py", line 76, in <module> 
    print(quicksort(a)) 
    File "11.py", line 70, in quicksort 
    return quicksort(l1) + quicksort(l2) 
    File "11.py", line 70, in quicksort 
    return quicksort(l1) + quicksort(l2) 
    File "11.py", line 70, in quicksort 
    return quicksort(l1) + quicksort(l2) 
    [Previous line repeated 993 more times] 
    File "11.py", line 69, in quicksort 
    l1, l2 = pivot(a, p) 
    File "11.py", line 54, in pivot 
    while(i<j): 
RecursionError: maximum recursion depth exceeded in comparison 

아마 무슨 일이 일어나고 것은 기본 케이스 퀵에 호출되지 것입니다 :

def pivot(a, pivot_index): 
    # I guess you can keep two indexes one greater and one lesser and swap. 
    i, j = 0, len(a)-2 
    p = a[pivot_index] 
    a[pivot_index] = a[len(a)-1] 
    a[len(a)-1] = p 

    while(i<j): 
     if(a[i]<p): 
      i = i + 1 
     if(a[i]>p): 
      temp = a[i] 
      a[i] = a[j] 
      a[j] = temp 
      j = j - 1 
     #print(a) 
    return a[0:i], a[i:] 

def quicksort(a): 
    if len(a) <= 1: 
     return a 
    p = len(a)//2 
    l1, l2 = pivot(a, p) 
    return quicksort(l1) + quicksort(l2) 

if __name__ == "__main__": 
    a = [1,-9,288,91,3,4,58,67,8] 
    print(quicksort(a)) 

가 나는 오류가 발생합니다. 그러나 그것을 고치는 방법을 모릅니다.

Answer 1

The below functionality explains how exactly the quicksort has been implemented by sending the input data as an array to the quicksort function. Here we implemented quicksort using recursion as below:

1. First check whether the array contains more than 1 element or not. If there is less than or equal to one element in the array then return array.(if len(arr) <= 1 then return arr)
2. Now take a pivot element from the middle of the array(Retrieve element from half the size of array) and then calculate the pivot element in the first iteration (pivot = arr[len(arr)//2])

3. If elements in array are less than pivot element then create a left array using list comprehension in python(left = [x for x in arr if x < pivot])

4. If elements in the array is equal to pivot element then create a middle array (middle = [x for x in arr if x == pivot])

5. If elements in the array are more than pivot element then create a right array (right = [x for x in arr if x > pivot])

6. Send the left array, right array to the quicksort function and repeat them recursively until all the elements in the array are sorted.

def quicksort(arr): 
      if len(arr) <= 1: 
      return arr 
      pivot = arr[len(arr)//2] 
      left = [x for x in arr if x < pivot] 
      middle = [x for x in arr if x == pivot] 
      right = [x for x in arr if x > pivot] 
      return quicksort(left) + middle + quicksort(right)