sort
-
[알고리즘] 퀵 정렬 (Quick Sort)Study/자료구조,알고리즘 2022. 11. 3. 12:35
01. 퀵 정렬의 개념 불안정 정렬이며, 다른 원소와의 비교를 통해 정렬하는 비교 정렬 분할 정복 알고리즘이다. 매우 빠른 속도를 보장 ( O(NlogN) ) 주로 순환 호출로 구현 02. 과정 설명 오름차순으로 정렬한다고 가정한다. 리스트 안에 있는 한 요소를 선택 (보통 맨 앞의 원소), 이를 Pivot이라고 한다. 피벗을 기준으로, 피벗보다 작은 요소들을 모드 왼쪽으로 옮기고 피벗보다 큰 요소를 오른쪽으로 옮긴다. 피벗을 제외한 왼쪽, 오른쪽 요소들을 각각 따로 정렬한다. 나눠진 부분들이 더 이상 분할이 불가능 할 떄까지 반복 03. 자세한 설명 배열에 [4, 6, 3, 2, 8, 7, 9, 1, 0, 5] 가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬한다. 초기 상태에서 pivot을 0번 ..