Quick Sort2 7. Array(배열) - Quick Sort(퀵 정렬) 1. Quick Sort란? - Quick Select와 마찬가지로 정렬이 되어있지 않은 배열을 대상으로 사용하는 알고리즘이다. - Quick Select와 동일하게 Partitioning을 이용하여 배열을 정렬한다. a) Quick Sort 정렬과정 b) Quick Sort의 시간복잡도 c) Quick Sort의 안정성(Stability) - Quick Sort는 불안정한(unstable) 정렬 알고리즘이다. 2. 코드구현 from typing import List import random def quick_sort(case:List[int], begin_idx:int, last_idx:int) -> List[int]: length = last_idx - begin_idx + 1 if length 2021. 9. 6. Advanced Algorithm - 퀵 정렬(Quick Sort) 1. Quick 정렬이란? - 정렬 알고리즘의 꽃! 파이썬과 만나면 아름다운 코드가 탄생한다. - 데이터에서 기준점(pivot)을 정하여 pivot보다 작다면 좌측(left)에, 크다면 우측(right)에 정렬한다. - 좌/우측으로 1차 정렬된 데이터에서 좌/우측 각각의 pivot을 다시 선정하고 정렬을 수행한다. - 이 과정을 재귀함수를 사용하여 반복한다. - 최종적으로 정렬된 데이터를 반환한다. 예시) Quick 정렬의 동작과정 index 0 1 2 3 4 5 data 55 13 45 88 76 59 이와 같은 데이터가 있을 경우, 1) 55를 pivot으로, 좌/우측으로 정렬 index 1 2 0 3 4 5 data 13 45 55 (pivot) 88 76 59 2) 좌/우측에서 각각 pivot을 .. 2020. 9. 15. 이전 1 다음
