[c언어]pivot

도서 : 한빛미디어 c,c++로 배우는 자료구조론

p145에 나온 pivot 을 구현해봄

========================================================================

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void chg_in_arr(int arr[], int i1, int i2) {

int temp;

temp = arr[i1];

arr[i1] = arr[i2];

arr[i2] = temp;

}

void search_up(int arr[], int * p_up, int * p_down, int* p_pvt)

{

if ((*p_up) == (*p_down) + 1)

return;

else if(arr[*p_up] >= arr[*p_pvt])

{

return;

}

else

{

(*p_up)++;

search_up(arr, p_up, p_down, p_pvt);

}

}

void search_down(int arr[], int * p_up, int * p_down, int* p_pvt)

{

if ((*p_up) == (*p_down) + 1)

return;

else if (arr[*p_down] <= arr[*p_pvt])

{

return;

}

else

{

(*p_down)--;

search_down(arr, p_up, p_down, p_pvt);

}

}

void pivot(int arr[], int size)

{

int p_up = 0, p_down = size - 1;

int p_pvt;

int flagL = 0, flagR = 0;

p_pvt = (int)(size / 2);

chg_in_arr(arr, p_pvt, p_down);

p_pvt = p_down;

p_down--;

while (p_up != p_down + 1)

{

search_up(arr, &p_up, &p_down, &p_pvt);

search_down(arr, &p_up, &p_down, &p_pvt);

if (p_up == p_down + 1)

break;

else

chg_in_arr(arr, p_up, p_down);

}

chg_in_arr(arr, p_up, p_pvt);

printf("\n%d", arr[p_up]);

}

int main()

{

int size = 14;

int arr[14];

srand(time(NULL));

for (int i = 0; i < size; i++)

{

arr[i] = rand() % 50;

printf("%d ", arr[i]);

}

pivot(arr, size);

printf("\n");

for (int i = 0; i < size; i++)

{

printf("%d ", arr[i]);

}

return 0;

}

==========================================================================================

때때로 정상적으로 실행되지 않는다. 무한루프에 걸린것같은데, 무엇이 문제인지?

=========================================================================================

p_up 과 p_down의 조건을 P_up == p_down + 1 에서 

p_up >= p_down 으로 변경하니 오류가 생기지 않았다.

즉 같음에서 교차로 변경.