퀵 정렬이 더 짧은 하위 시퀀스를 먼저 정렬하는 이유는 무엇입니까?

우리 모두 알고 있듯이 재귀는 성능에 일정한 영향을 미칩니다. QSort 함수에는 마지막에 두 가지 재귀 작업이 있습니다. 정렬할 시퀀스 분할이 극도로 불균형한 경우 균형이 잡혔을 때 재귀 깊이는 log2n 대신 n에 접근하게 됩니다. 이는 단지 속도의 문제가 아닙니다. 스택의 크기는 매우 제한되어 있습니다. 각 재귀 호출은 특정 양의 스택 공간을 사용합니다. 함수에 매개변수가 많을수록 각 재귀가 사용하는 공간도 늘어납니다. 따라서 재귀를 줄일 수 있다면 성능은 크게 향상될 것입니다.

그래서 우리는 QSort에 꼬리 재귀 최적화를 구현했습니다. 코드를 살펴보겠습니다.

/* 시퀀스 목록 L.r[low..high]의 하위 시퀀스 빠른 정렬 L*/

void QSort1 (SqList *L, int low, int high) < /p >

{ int 피벗;

if ((high-low)>MAX_LENGTH_INSERT_SORT)

{

while (low

{

ivot=Partition1 (L, low, high); /*L.r[low..high]는 2개로 나누어집니다.*/ /*피벗 값을 계산합니다.*/ QSort1(L ,low,pivot-1); /* 낮은 하위 테이블을 재귀적으로 정렬*/ low=pivot+1 /* 꼬리 재귀*/ }

}

else InsertSort (L) ;

}

if를 while으로 변경하면 첫 번째 재귀 이후 변수 low는 쓸모가 없으므로 피벗+1을 low에 할당할 수 있으므로 재순환 후 Partition을 수행합니다. (L, low, high) 한 번 효과는 "QSort (L, 피봇+1, high);"와 동일합니다. 결과는 동일하지만 재귀적 방법이 아닌 반복적 방법을 사용하면 힙 크기를 줄이고 물리적 스택 깊이를 늘려 전반적인 성능을 향상시킬 수 있습니다.