퀵 정렬 (1) 썸네일형 리스트형 [알고리즘] 퀵 정렬 퀵 정렬이란 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나 이고, 평균적인 상황에서 최고의 성능을 낸다. 퀵 정렬의 특징 분할 정복 알고리즘이다. 최악 시간복잡도 O(n²), 평균 시간복잡도 O(n log n) 퀵정렬은 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다. 퀵 정렬 알고리즘 리스트에서 적절한 피벗(원소) 하나를 고르고, 피벗 앞에는 피벗보다 작은 값들이 오게 하고, 피벗 뒤에는 피벗보다 큰 값들이 오게 한다. 작업이 완료되면 피벗을 기준으로 두 개의 리스트가 생기는데, 각각 리스트에도 이전에 했던 과정을 재귀적으로 반복해준다. 리스트가 더 이상 나누어지지 않는다면, 재귀반환하면서 여러 개의 정렬된 리스트를 .. 이전 1 다음