[알고리즘] 정렬(6) - 퀵 정렬(Quick Sort)
원리 1. 배열 리스트 중 하나를 선택한다. 이 원소를 피벗이라고 함. 2. 피벗을 기준으로 피벗 앞에는 피벗보다 작은 모든 원소들이 오고 피벗 뒤에는 피벗보다 큰 원소가 옴 3. 분할 : 리스틀 피벗을 기준으로 두 리스트로 나눈다. 4. 분할된 리스트들에서 1-3번 과정을 반복한다. 위와 같은 과정을 반복한다면 매번 분할시 피벗으로 한 원소의 위치를 정할 수 있으므로 모든 수를 정렬할 수 있는 것은 자명합니다. 앞서 포스팅한 병합정렬에서와 마찬가지로 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 분할 정복을 모른다면 공부하고 읽는 것을 권장드립니다. 하지만 포스트를 통해서 이해는 할 수 있습니다. [ 16, 11, 6, 19, 12, 2, 2, 10 ] pivot값은 맨앞의 값..
2020.04.10