퀵 정렬

퀵 정렬이란 분할, 정복, 결합

순환 호출이 한번 진행될 때마다 최소한 하나의 피벗은 최종적으로 위치가 정해지므로 이 알고리즘은 반드시 끝난다는 것을 보장

1. 리스트 안에 있는 한 요소를 선택 이것을 피벗(pivot)이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소는 피벗의 왼쪽 큰 요소는 피벗의 오른쪽으로 옮김
3. 분활된 리스트에 다시 피벗을 정하고 피벗을 기준으로 분할이 불가능할 때까지 1, 2 번 반복

장점 : 속도가 빠르다.

단점 : 정렬된 리스트에 대해 퀵 정렬의 불균형 분할의 의해 오히려 시간이 더 많이 걸린다.

예제)

QuickSort 클래스와 Main 클래스를 나눠 출력하는 이유 : 퀵 정렬은 분할 정복 알고리즘을 사용하여 구현되기 때문에 코드 구조의 모듈화, 확장성과 재사용성, 사용자 편의성을 고려하기 때문이다.