퀵 정렬

가장 빠른 알고리즘 중 하나
찰스 앤터니 리처드 호어(C.A.R. Hoare)가 명명

각 그룹에 대해 피벗(pivot) 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마침

불안정 정렬에 속함

피벗(pivot) : 그룹을 나누는 기준을 말하며, 피벗은 마음대로 선택할 수 있고, 왼쪽 그룹과 오른쪽 그룹 어디에 들어가도 상관없음

분할 정복 알고리즘이므로 재귀 호출을 사용하여 구현

퀵 정렬 방법

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
   (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
4. 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
5. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
6. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
7. 리스트의 크기가 0이나 1이 될 때까지 반복한다.
   https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

배열을 조금씩 나누어 보다 작은 문제를 해결하는 과정을 반복하므로 O(n log n)

정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간 복잡도가 증가할 수 있음

qsort함수

qsort(배열, 요소개수, 요소크기, 비교함수)

• Int형, double형, 구조체 형 등의 모든 자료형의 배열에 적용할 수 있음
• 내부적으로 항상 퀵 정렬 알고리즘을 사용하지 않음(함수 이름일 뿐)
• 안정된 정렬은 아님

-오름차순

-내림차순