퀵정렬
-
[알고리즘] Quick sort개발/C·C++ 2021. 8. 3. 16:17
종류 분할-정복 알고리즘입니다. 분할-정복 알고리즘은 재귀적으로 자신을 호출하면서 연산 단위를 조금씩 줄여나가는 방법입니다. 재귀 호출이 한 번 진행될 때마다 최소 하나의 원소는 위치가 정해지기 때문에 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다. 장점 재귀호출의 과정에서 임시 메모리를 쓰는 것은 성능 저하를 가져오기 때문에(리턴값을 사용하지 않음) 배열 내부에서 분할 작업을 구현하는 편이 좋습니다. 퀵 정렬은 메모리 참조가 지역화되어 있기 때문에(캐시의 공간 지역성) 캐시 히트률이 높습니다. 이런 이유로 일반적인 경우 퀵 정렬은 다른 O(nlogn) 알고리즘보다 빠르게 작동합니다. 기본 흐름 피벗을 기준으로 왼쪽에는 피벗보다 작은 원소를, 오른쪽에는 피벗보다 큰 원소들을 위치합니다. 개념적으..
-
[간단 정리] 퀵 정렬컴퓨터 과학/자료구조와 알고리즘 2019. 11. 27. 01:16
*오름차순 기준입니다 정렬 알고리즘 중에 퀵 정렬이 가장 성능이 좋다. 다른 원소와 비교하여 정렬을 수행하는 비교 정렬에 속한다. 최악의 시간 복잡도는 O(N^2)이지만 최선과 평균이 O(NlogN)이다. 원소들 중에 같은 값이 있으면 순서가 달라질 수 있기 때문에 불안정 정렬이다. 기본적인 동작 1. 배열 중에 하나의 원소를 골라 피벗(기준)을 정한다. 2. 피벗을 기준으로 앞에는 피벗보다 작은 값, 뒤에는 큰 값이 오도록 나눈다. 이를 분할이라고 한다. 3. 분할된 배열에 대해 위 과정을 재귀적으로 반복한다. 최악의 경우는 피봇으로 가장 작은 수가 선택되거나 큰 수가 선택될 때인데, 이는 중위값을 선정해 해결할 수 있다. 0번째, 가운데, 마지막 요소 중에서 중간 값을 피벗으로 정하면 된다. 퀵 정렬..