퀵 소트 구현하기
퀵소트
- 1번째 버전.
- swap 함수는 아래 코드에서 생략함.
void quick_sort(int* v, int n)
{
if(n <=1) return;
int* pivot = v;
int* left = v + 1;
int* right = v + n - 1;
while(1)
{
if(left == right) break;
if(*left > *pivot)
{
while(*right > *pivot)
{
if(left < right) right--;
else break;
}
if(left == right) break;
swap(left, right);
left ++;
}
else
{
left++;
}
}
int* meet = left; // or right
// 만난 값이 피봇보다 크면 만난 값왼쪽에 피봇을 넣는다.
if(*meet > *pivot )
{
int k = meet - pivot - 1;
for(int i = 0; i < k; i++)
{
swap(pivot + i, pivot + i + 1);
}
pivot = meet - 1;
}
//만난 값이 피봇보다 작으면 만난 값 오른쪽에 피봇을 넣는다.
else
{
int k = meet - pivot;
for(int i = 0; i < k; i++)
{
swap(pivot + i, pivot + i + 1);
}
pivot = meet;
}
// v이상 pivot 미만
quick_sort(v, pivot - v);
// 피봇을 초과하고 끝을 포함하는 배열, v+ n - 1은 끝 주소값 , pivot은 피봇값, 초과 이하이므로 + 0
quick_sort(pivot + 1, v + n - 1 - (pivot));
}
- 첫 번째 리팩토링
- 마음에 썩 들진 않지만 while문을 하나만 사용했고, 조건문에는 하나의 조건문만 주어 작성해 가독성과 원치 않은 오류를 줄였다.
- n이 2가되는 순간에 left와 right가 예상치못하게 자동으로 같아져 헤맸다.
void quick_sort(int* v, int n)
{
print(v, n);
if(n <=1) return;
int* pivot = v;
int* left = v + 1; // left를 v로 잡을까 v + 1로 잡을까에 대해서 고민을 했다.
int* right = v + n - 1;
printf("pivot: %d left: %d right: %d\n", *pivot, *left, *right);
while(1) // 하나의 while문에 담으려고 고민했다.
{
printf("=============================================\n");
print_debug(v, n, left, right);
if(left == right) break; // n = 2일때는 이미 left == right이기 때문에 확인해준다.
if(*left < *pivot) // 조건문에는 하나의 조건만 담으려고 했다. 두개 이상의 조건이 나오면 어떤 조건에서 성립이 안되었는지 2번확인해야 하기 때문이다.
{
left ++;
if(left == right) break; // left를 변화시킬때마다 left == right를 확인해준다.
}
else
{
if(*right > *pivot)
{
right --;
if(left == right) break; // right를 변화시킬때마다 left == right를 확인해준다.
}
else
{
puts("swap");
swap(left, right);
print_debug(v, n, left, right);
}
}
}
printf("\n\n");
print(v, n);
int* meet = left; // or right
// 만난 값이 피봇보다 크면 만난 값왼쪽에 피봇을 넣는다.
if(*meet > *pivot )
{
int k = meet - pivot - 1;
printf("k = %d\n", k );
for(int i = 0; i < k; i++)
{
swap(pivot + i, pivot + i + 1);
}
pivot = meet - 1;
}
//만난 값이 피봇보다 작으면 만난 값 오른쪽에 피봇을 넣는다.
else
{
int k = meet - pivot;
for(int i = 0; i < k; i++)
{
swap(pivot + i, pivot + i + 1);
}
pivot = meet;
}
print(v, n);
// v이상 pivot 미만
quick_sort(v, pivot - v);
// 피봇을 초과하고 끝을 포함하는 배열, v+ n - 1은 끝 주소값 , pivot은 피봇값, 초과 이하이므로 + 0
quick_sort(pivot + 1, v + n - 1 - (pivot));
}
- 2번째 리팩토링
- 코드가 한페이지에 보일정도로 확실히 짧아지고 가독성이 생겼다.
- 연속되는 두 while문에서 조건문을 하나만 넣지 않고 두개를 넣어 작성했는데, 이어지는 while문에서도 같은 조건을 주었다. 그래서 원하는 일을 반복해서 하면서도 left != right라는 중요한 조건이 깨지지 않도록 했다. 마지막으로 left ==right일 경우를 잡아내는 코드를 작성해 break 시켰다.
- left == right를 비교하는 if문이 전보다 2개가 줄게 되면서 코드 완결성이 더 높아졌다고 생각한다.
- 또한 pivot의 위치를 정하는 코드에서도 swap을 무식하지만 간편하게 반복하는 것 대신 좀 더 고려해서 n = 2일 때도 적용할 수 있는 코드를 작성했는데 , 훨씬 더 나아졌다고 생각한다.
void quick_sort(int* v, int n)
{
if(n <=1) return;
int* pivot = v;
int* left = v + 1; // left를 v로 잡을까 v + 1로 잡을까에 대해서 고민을 했다.
int* right = v + n - 1;
while(1)
{
while(*left < *pivot && left < right)
{
left ++;
}
while(*right > *pivot && left < right)
{
right --;
}
if(left != right)
{
swap(left, right);
}
else if(left == right)
{
break;
}
}
int* meet = left; // left와 right가 만난 값
if(*meet > *pivot)
{
swap(pivot, meet - 1);
}
else
{
swap(pivot, meet);
}
// v이상 pivot 미만
quick_sort(v, pivot - v);
// 피봇을 초과하고 끝을 포함하는 배열, v+ n - 1은 끝 주소값 , pivot은 피봇값, 초과 이하이므로 + 0
quick_sort(pivot + 1, v + n - 1 - (pivot));
}
####퀵소트를 짤 때 어려웠던 점
- 어떤 조건에서 리턴을 넣어야 할지 몇 분간 고민했다. n이 2보다 작을 때인지 1이하일 때인지.
- while문 안에 while문을 넣어야할까봐 고민을 했다.
- while문의 조건에 두가지 조건을 넣으면 break가 걸렸을 때 어떤 조건을 만족 못해서 나온것인지 너무 햇갈렸다.
- pivot과 left나 right가 만날 때 어떻게 처리해야 할지 고민했다.
- 가장 어려웠던 문제는 left와 right를 전진시킬 때 각각 한번 씩 전진시켰다. 이때 운이 좋으면 left와 right가 만나고 끝이 나지만, 최악의 상황에는 left가 right보다 뒤에가는 상황이 발생했다.
- 한 번 움직일 때마다 left와 right가 만나는지 확인하는 코드가 있으면 더 간단하고 가독성도 높은 코드가 될 것같다.
- 특히 만났을 때 상황에 따라서 pivot값의 위치가 달라져야 하는 상황에서 고민을 많이했다.
- 오류가 발생했을 때 디버깅하는 시간이 최소 1/3은 차지했던 것 같다.
- 반복되는 작업이므로 계속 쓸 디버깅 툴을 기억하자ㅏ.
- 포인터 주소값의 차를 구했을 때 이 값이 정말 주소값 간의 거리인지, 자료형의 크기로 이미 나누어 놓은 값인지 알지 못해 헤메었다.
- 포인터의 자료형을 int*으로 정해야 할지 long*으로 정해야 할지 햇갈렸다.
잘한 점
- 반복되는 작업시간을 줄이기 위해서 간단한 디버깅 툴을 만들었다.
- left와 right에 | |를 씌워주고 각 출력시 일정한 띄어쓰기 간격을 적용해서 디버깅 효율이 높아졌다.
