정렬알고리즘_퀵정렬

퀵정렬

빠른속도와 간단 원리

연속적인 분할에 의해서 정렬한다.

축값을 중심으로 왼쪽은 이 축값보다 작은 값으로 오른쪽은 모두 이 축값보다 큰 값으로 배열시키는 것이다.

이 과정을 분할의 크기가 1이 될 때까지 반복하면 전체적으로는 정렬이 완료된다.

 

퀵 정렬의 전략

<퀵 정렬 알고리즘 (a, N)>

1.만약 n > 1이면

1.1 N의 크기의 a 배열을 분할하여 축값의 위치를 mid로 넘긴다.

1.2 퀵 정렬 알고리즘(a,mid)

1.3 퀵 정렬 알고리즘(a+mid+1,N-mid-1)

왼쪽구간 부터 우선적으로 분할을 하고, 그 다음에 오른쪽 부분에 대해서 분할을 시작한다.

쉘 정렬 처럼 멀리 떨어져 있는 요소끼리 교환을 하기 때문에 빨리 정렬된 상태로 변화된다.

 

난수나, 반쯤 정렬된 배열에 대해서는 빠른 속도를 보이지만 이미 정렬된 배열이나 역순 배열에 대해서는 성능이 매우 떨어진다.
(빠른 알고리즘이란 최대한 적은 비교와 교환이다. 퀵정렬은 피벗에 모두 순차적으로 비교하게 되므로)



 

퀵소트 비재귀 버전