공부하는 블로그

퀵 정렬(Quick Sort) ? 퀵 정렬은 분할 정복 알고리즘의 하나로 피벗(pivot)을 정한 뒤 피벗의 위치를 확정해가며 정렬한다. 피벗을 선정하는 기준은 가장 왼쪽, 가장 오른쪽, 가운데, 랜덤 등 다양하며 어떤 피벗이 좋은 피벗인지는 확답할 수 없다. 분할 정복은 대개 재귀호출을 이용하여 구현한다. * 분할 정복 알고리즘 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략 퀵 정렬은 O(nlog2n)의 시간복잡도를 가지는 매우 효과적인 정렬 알고리즘으로, 자바 스크립트의 배열 객체의 내장 함수인 sort의 내부 구조도 퀵 정렬을 따른다. 퀵 정렬의 과정은 다음과 같다. 각 반복 과정에서는 재귀호출이 사용된다. 1. 배열의 안에 있는 요소 하나를 ..