우리가 알던 quick sort는 잘못되었다(?)

한 강의에서 퀵 정렬을 공부하던 중

while문 아래의 두 while문을 보면

5 4 3 2 1이나 1 2 3 4 5같이 pivot보다 나머지가 모두 우선순위가 pivot보다 낲거나 높으면 low 나 high가 끊임없이 증가 또는 감소하지 않을까 하는 의문이 들었습니다.

그래서

이렇게 printf를 코드 내에 추가하여 보니
5 4 3 2 1 을 정렬해보니

확실하다! 이건 잘못되었다!!

그런데

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

이거 위키백과에도 이렇게 적혀있었습니다... 헐...

영문판 너마저!

모 대학교 컴공 친구에게 물어보니 자료구조 강의자료에도 이렇게 되어있었다고...

여러모로 충격....

그럼 어떻게 해야하는가??

사실 정답은 모르겠고 저는 이렇게 해봤습니다 ㅋㅋ...

#include <stdio.h>

int array[1000];

void qsort(int left, int right)
{
	if (left >= right) return;
	int pivot = array[left];
	int low = left + 1; // low가 low인 이유 : 우선 순위가 낮기 때문, 다 오른편으로 던질 것들
	int high = right; // high가 high인 이유 : 우선 순위가 높기 때문, 다 왼편으로 던질 것들
	int temp;
	while (pivot >= array[low]&&low<=right) low++;
	while (pivot <= array[high]&&high>left) high--;
	if (low > right)// 5 4 3 2 1같이 우선순위가 모두 높은 경우, 4 3 2 1 5와 같이 바꿔주면 된다.
	{
		array[left] = array[right];
		array[right] = pivot;
		qsort(left, right - 1);
		return;
	}
	if (high <= left)// 1 2 3 4 5 같이 우선 순위가 모두 낲은 경우
	{
		qsort(left + 1, right);
		return;
	}
	while (low <= high)//안이 참인동안 동작, low > high인 순간 동작 중지
	{
		temp = array[low];
		array[low] = array[high];
		array[high] = temp;
		while (pivot >= array[low]) low++;//pivot의 우선순위가 낮은 동안 동작, 즉 멈췄을 때는 pivot보다 array[low]의 우선순위가 더 높을 때
		while (pivot <= array[high]) high--;	
	}
	array[left] = array[high];//위의 과정을 거친 후 나온 high는 low와 high가 교차한 후 최초의 high 즉, 우선순위가 피버보다 높은 성분 중 가장 오른쪽의 성분이다.
	array[high] = pivot;
	qsort(left, high - 1);
	qsort(high + 1, right);
	return;
}

int main()
{
	int i, N;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%d", &array[i]);
	}
	qsort(0, N - 1);
	for (i = 0; i < N; i++)
	{
		printf("%d\n", array[i]);
	}
	return 0;
}

이렇게 하고 친구(https://www.acmicpc.net/user/rkaxhdals)
한테 보여줬는데

친구가 위의 if문 검사를 하지 않게
이렇게 짜주었고 성능도 제가 짠 것과 기존 알려진 퀵정렬 코드에 비해 확실히 좋았습니다.

(제가 짠건 기존 퀵소트와 비슷)

void qsort(int left, int right)
{
   if (left >= right) return;
   int pivot = array[left];
   int low = left + 1;  // low가 low인 이유 : 우선 순위가 낮기 때문, 다 오른편으로 던질 것들
   int high = right;  // high가 high인 이유 : 우선 순위가 높기 때문, 다 왼편으로 던질 것들
   int temp;
   while (low <= high)//이러면 low<=high이면 바로 검사 종료!
   {
      if (pivot >= array[low]) low++;//array[low]의 우선순위가 높은동안 low움직이고 낮으면 여기 진입 X
      else if (pivot <= array[high]) high--;
      else {//low가 우선순위가 낮은 성분, high가 높은 성분을 가리킬 때 진입
         temp = array[low];
         array[low++] = array[high];
         array[high--] = temp;
      }
   }
   array[left] = array[high];
   array[high] = pivot;
   qsort(left, high - 1);
   qsort(high + 1, right);
}

저는 한번 옮길 때마다 while문에 들어가서 검사를 한번씩 더 하니 성능이 더 안 좋을 줄 알았는데

아마 재귀함수 밑바닥에서는 제가 if문을 두번 검사하는게 더 효율이 안 좋으니 그 때문이 아닐까 싶습니다.