장소 (장소)의 성능 (파이썬)

Question

'장소'퀵소트 버전을 쓰도록 요청 받았습니다. 재귀 함수와 무작위 피벗을 선택하는 '적절한 정렬'두 가지 내부 함수를 작성하고 목록을 제자리에 정렬하고 정렬 후에 피벗 인덱스를 반환합니다. 매우 느리게 분류되어 100 개 요소 또는 이상을 포함

목록 -

 import random 

def quicksort(lst): 

    def innerfunc(lst, start=0, end=(len(lst) - 1)): 
     temporal_pivot = subfunc(lst, start, end) 

     if (end - start > 1): 
      if (temporal_pivot == start or temporal_pivot == start + 1): 
       innerfunc(lst, temporal_pivot + 1, end) 

      elif (temporal_pivot == end or temporal_pivot == end - 1): 
       innerfunc(lst, 0 , temporal_pivot - 1) 

      else: 
       innerfunc(lst, 0 , temporal_pivot - 1), innerfunc(lst, temporal_pivot + 1, end) 


    def subfunc(l, start, end): 
     i_random = random.randint(start, end) # chooses random index! 
     l[i_random], l[start] = l[start], l[i_random] 

     i_pivot = start 
     pivot = l[start] 

     i = end 
     while i > i_pivot: 
      if l[i] <= pivot: 
       l.insert(i_pivot, l[i]) 
       i_pivot += 1 
       l.pop(i + 1) 

      else: 
       i = i - 1 

     return i_pivot 


    return innerfunc(lst) 

문제

시간이 실행됩니다.

"subfunc"알고리즘과 Quicksort 성능을 향상시키는 방법이 있습니까?

감사합니다. 루프와 배열 부분에 삽입 -

오렌

Answer 1

그 subfunc이 효율적이지 않습니다 보인다. 파이썬 프로그래머가 아니지만 메모리 재 할당 및 비용 (O) 조작의 원인이 될 수 있습니다.

Answer 2

문제는 l.insert() 및 l.pop()에 대한 반복 호출입니다. 루프의 각 반복을 O(1)으로하는 반면, 이들 각각에는 O(n) 복잡도가 있습니다.

반복적 인 삽입 및 제거를 수행하는 대신 요소를 바꿔서 작동하도록 함수를 다시 작성해야합니다.

Wikipedia에서 일부 가상 코드를 찾을 수 있습니다.