퀵 정렬

[알고리즘][파이썬/Python] 퀵 정렬 (Quick Sort)

정의 기준 값을 중심으로 작은 원소들은 왼쪽 부분집합으로, 큰 원소들은 오른쪽 부분집합으로 분할하여 정렬하는 방식의 정렬 알고리즘 * 퀵 정렬도 분할과 정복(divide and conquer) 기법을 이용하는 정렬 알고리즘이다. 하지만 병합 정렬과 차이가 있는데, 병합 정렬이 분할 후 정복하는 원리였다면, 퀵 정렬은 정복 후 분할하는 원리의 정렬 알고리즘이다. 우선 기준 값보다 작은 원소들을 왼쪽 부분집합으로, 기준 값보다 큰 원소들은 오른쪽 부분집합으로 구분하는 정복 절차를 밟고, 기준 값을 중심으로 2개의 부분 집합으로 분할한다. 동작 방식 0. 기준 값을 보통 피벗(pivot)이라고 부르며, 선택하는 기준은 다양하겠으나 일반적으로 가장 왼쪽 원소를 피벗으로 지정한다. 본 글에서도 가장 왼쪽 원소를 ..