[김태원 알고리즘] 퀵정렬 (전위순회)

사용 언어: Python3

문제

퀵정렬을 구현해보자!

풀이

def quickSort(lt, rt):
    if lt < rt:
        pos = lt # pos는 0이 아니라 lt
        pivot = arr[rt]
        for i in range(lt, rt): # rt전까지 돌기
            if arr[i] <= pivot:
                arr[i], arr[pos] = arr[pos], arr[i] # swap
                pos += 1 # swap하면 pos 1 증가
        arr[rt], arr[pos] = arr[pos], arr[rt] # 다 끝나고 pos와 rt swap
        # 퀵 정렬은 전위순회
        quickSort(lt, pos-1)
        quickSort(pos+1, rt)

arr = [23, 11, 45, 36, 15, 67, 33, 21]
print('Before sort : ', end=' ')
print(arr)

quickSort(0,7)
print()

print('After sort : ', end=' ')
print(arr)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기