[Algorithm] Quick Sort : 퀵 정렬, 퀵 소트 ( 코드 포함 )

퀵 정렬은 평균적으로 O(n logN) 시간이 소요되며 좋은 성능을 가진다.

 

맨 뒤의 원소를 기준으로 삼고 맨 뒤의 원소보다 작은 것은 기준 앞에, 큰 것은 기준 뒤에 놓는다.

기준의 양 옆을 재귀적으로 반복한다.

 

10 4 5 2 1 6 3 9 8 7 이 배열 안에 있으면 최초 7을 기준으로 좌우 정렬한다

따라서 4 5 2 1 6 3 7 10 9 8 이 되며 기준의 양 옆을 다시 재귀적으로 동작시키면

4 5 2 1 3 을 다시 재정렬하여 2 1 3 4 5 가 된다

이를 다시 기준의 양 옆을 재 정렬하면 1 2 3 4 5 가 된다.

 

quick sort 함수 본체. 자기 자신을 호출하는 부분이 재귀로 동작

 

기준을 설정하고 앞 뒤로 나누는 함수

 

실제 사용하여 정렬