ki hyun's 개발블로그

퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. - 위키백과 - 1. 퀵 정렬? 퀵 정렬은 n개의 원소를 가진 배열을 최악의 경우에 O(n²)시간에 정렬하는 알고리즘이다. 이렇게 최악의 경우로만 봤을땐 퀵 정렬은 느리지만 평균 수행시간이 O(n lg n)으로 굉장히 효율적이고 O(n lg n)에 숨겨진 상수 인자도 굉장히 작다. 퀵 정렬은 병합 정렬과 마찬가지로 분할정복에 기반을 두고 있다. 따라서 퀵 정렬의 동작은 다음과 같이 설명할 수 있다. 분할: 배열 A[p..r]을 두 개의 부분 ..