퀵정렬 구현하는데 재귀 부분에서 돌아가질 않습니다.

Question

퀵 정렬을 구현하려고 하는데 다른거 잘 돌아가다가 마지막 재귀호출 부분이 작동을 안합니다. 지금 단계 피벗의 왼, 오른쪽 리스트에 똑같은 quick()을 하려는데 안돌아가네요. 이 부분을 코드에 넣든 안넣든 똑같이 리스트를 한번만 퀵소트 방식으로 정렬한 결과가 나옵니다. 어디가 잘못된 걸까요? li = [9,8,1,5,3,7,4,10,6,2] def quick(arr): pivot_idx = 0#defining pointers - s is for finding what's not smaller than pivot, # and e is the contrast. pivot = arr[pivot_idx] s = 0 e = len(arr) - 1 while s <= e:#from here, s and e is moving to find value that doesn't fit while s <= e: if arr[s] <= pivot:#s increases if arr[s] is same or smaller than pivot. And when it s += 1#meets value bigger than pivot, break the loop and code moves onto e. else: break while s <= e: if arr[e] >= pivot: e -= 1 else: break if s <= e: arr[s], arr[e] = arr[e], arr[s] #swapping s and e s += 1 e -= 1 if pivot_idx >= s:#changing index of pivot pivot_idx, arr[0], arr[s-1] = s-1, arr[s-1], pivot if pivot_idx <= e: pivot_idx, arr[0], arr[e] = e, arr[e], pivot if len(arr[0:pivot_idx]) > 1:#recursively call quick() function.- sorting list before pivot quick(arr[0:pivot_idx]) if len(arr[pivot_idx+1:]) > 1:#sorting list after pivot quick(arr[pivot_idx+1:]) quick(li) print(li)

mirheeoj · Answer

계산한 결과값이 li에 반영이 안됩니다. 아래 코드와 비교해보세요. def quick(arr): if len(arr) <= 1: return arr pivot_idx = 0 pivot = arr[pivot_idx] s = 0 e = len(arr) - 1 while s <= e: while s <= e and arr[s] <= pivot: s += 1 while s <= e and arr[e] >= pivot: e -= 1 if s <= e: arr[s], arr[e] = arr[e], arr[s] s += 1 e -= 1 if pivot_idx >= s: pivot_idx, arr[0], arr[s-1] = s-1, arr[s-1], pivot if pivot_idx <= e: pivot_idx, arr[0], arr[e] = e, arr[e], pivot if pivot_idx > 0: print(arr) #print("recursive quick1") arr[0:pivot_idx] = quick(arr[0:pivot_idx]) if pivot_idx < len(arr) - 1: print(arr) #print("recursive quick2") arr[pivot_idx+1:] = quick(arr[pivot_idx+1:]) return arr li = [9, 8, 1, 5, 3, 7, 4, 10, 6, 2] li = quick(li) print(li)

퀵정렬 구현하는데 재귀 부분에서 돌아가질 않습니다.

1개의 답변

기술 목록