한 강의에서 퀵 정렬을 공부하던 중
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문을 두번 검사하는게 더 효율이 안 좋으니 그 때문이 아닐까 싶습니다.