컴공생의 다이어리

퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 알고리즘이다. 합병 정렬(Merge Sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다. 하나의 리스트를 피벗(pivot)을 기준으로 피벗보다 작은 데이터와 큰 데이터를 두 개의 부분 리스트로 나눈 다음, 각 부분 리스트에 대해 다시 재귀적으로 수행하여 정렬하는 방법이다. 정렬 과정 배열 가운데서 하나의 원소를 선택(→ 이 원소가 피벗) 피벗을 기준으로 피벗보다 작은 원소들은 피벗 앞(왼쪽)으로 오고, 피벗보다 큰 원소들은 피벗 뒤(오른쪽)로 이동 피벗을 제외하고 나뉘게 된 두 배열은 앞 ..