배열이 올바르게 나오지 않습니다.

Question

배열의 첫 번째 절반에있는 각 요소가 배열의 두 번째 절반에있는 각 요소보다 작도록 배열을 분할하려고합니다. 이것은 빠른 정렬에서 사용되는 것과 동일한 파티션 알고리즘입니다. 어떤 이유로 배열 A = [2, 8, 7, 1, 3, 5, 6, 4]을 사용할 수 있지만 A = [7, 3, 6, 1, 9, 5, 4, 8]은 작동하지 않습니다.

def partition(A): 
    x = A[len(A)-1] 
    i = -1 
    for j in range (0, len(A)-2): 
     if A[j]<=x: 
     i = i + 1 
     # exchange A[j] and A[i] 
     jValue = A[j] 
     A[j] = A[i] 
     A[i] = jValue 
    # exchange A[len(A)-1] and A[i+1] 
    rValue = A[len(A)-1] 
    A[len(A)-1] = A[i+1] 
    A[i+1] = rValue 
    print(A) 

Answer 1

코드는 배열의 중앙값을 나타내는 피벗을 선택해야합니다. 이것은 빠른 선택이나 비슷한 것을 사용하여 수행 할 수 있습니다. 빠른 선택은 O (n^2)의 최악의 시간 복잡성을가집니다. 위키 문서 :

http://en.wikipedia.org/wiki/Quickselect