개발자의시작

Quick Sort(퀵 정렬) 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속합니다. 퀵 정렬은 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 보입니다. 분할 정복 알고리즘을 사용하는 병합 정렬(merge sort)와 다르게 퀵 정렬은 비균등하게 분할합니다. 아이디어 퀵 정렬은 위에서 언급한대로 분할 정복 알고리즘을 사용한다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한다음 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복은 일반적으로 재귀 호출을 사용하여 구현한다. 과정은 다음과 같다. 리스트에 있는 요소 하나를 선택한다. 이를 피벗(pivot)이라고 한다. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로..