코딩테스트/기본 알고리즘
2022. 1. 10.
정렬 코드2(퀵 정렬, 병합 정렬)
퀵 정렬 (quick sort) 퀵정렬은 삽입정렬과 다르게 '이미 데이터가 거의 정렬된 경우' 시간복잡도가 거의 O(n^2)으로 매우 느리게 동작한다. 하지만 데이터가 무작위로 입력되는 경우 O(nlogn)의 속도로 매우 빠르게 동작한다. 그러므로 데이터의 상태를 보고 삽입정렬과 잘 선택하여 사용해야한다. def quick_sort(array, start, end): if start >= end: # 아래 재귀함수에서 모든 정렬이 끝나고 원소가 1개인 경우 종료 return pivot = start left = start + 1 right = end while left right: # left와 right가 교차할때 작은값(right(엇갈렸으므로))과 pivot 교체 array[right], array[..