수다닷컴

질문 제목 : quick sort
퀵소트 비재귀질문 내용 :
#include windows.h
#include stdio.h
#include stdlib.h
#include time.h
#include malloc.h
#define ary_size 20
#define init_stack (top = -1)
#define is_stack_empty (top 0)
#define pop (stack[top--])
#define peek (stack[top])
#define push(data) (stack[++top] = (data))void quick(int *ary, int size);int top;
int stack[ary_size];
int main(int argc, char **argv)
{
int start = gettickcount();
int a[ary_size],i;
srand((unsigned int)time(null));
for(i = 0; i sizeof(a)/sizeof(a[0]); i++) a[i] = rand()%30;
printf(before : );
for(i = 0; i sizeof(a)/sizeof(a[0]); i++) printf(%d ,a[i]);
quick(a,sizeof(a)/sizeof(a[0]));
printf(\n\nafter : );
for(i = 0; i sizeof(a)/sizeof(a[0]); i++) printf(%d ,a[i]);
printf(\n\nstart-time : %.3lf\n,start/1000.0);
printf(end-time : %.3lf\n,gettickcount()/1000.0);
printf(run-time : %.3lf\n,(gettickcount() - start)/1000.0);
}void quick(int *ary, int size)
{
int pivot,buf;
int i,j;
int l,r; //스택에 저장할 구간의 정보
init_stack;
l = 0; //배열의처음
r = size - 1; //배열의마지막
push(r);
//printf(\n1번째 푸시값 : %d\n,: %d\n,peek);
push(l);
//printf(2번째 푸시값 : %d\n,peek); while(!is_stack_empty)
{
l = pop; //배열의맨앞
//setconsoletextattribute( getstdhandle( std_output_handle ),14);
//printf(1번째 팝값 : %d\n,l);
r = pop; //배열의맨뒤
//setconsoletextattribute( getstdhandle( std_output_handle ),10);
//printf(2번째 팝값 : %d\n,r);
//setconsoletextattribute( getstdhandle( std_output_handle ),7);
if(r-l+1 1) //r-1+1 == 배열(구간)의 사이즈
{
pivot = ary[r]; //pivot은 배열의맨뒤값
i = l - 1; //i = -1 - 맨앞부터 탐색
j = r; //배열의 맨뒤부터 탐색

while(1) //분할
{
while(ary[++i] pivot);
while(ary[--j] pivot);
if(i = j) break; //i와j가 같거나 교차함

//--swap--피봇값을 중심으로 큰값과 작은값을 교환
buf = ary[i];
ary[i] = ary[j];
ary[j] = buf;
//--swap--
}
//--swap-- 맨뒤의 피봇과 피봇이들어가야할자리의값을 교환
buf = ary[i];
ary[i] = ary[r];
ary[r] = buf;
//--swap--
push(r);
//printf(3번째 푸시값 : %d\n,peek);
push(i+1);
//printf(4번째 푸시값 : %d\n,peek);
push(i-1);
//printf(5번째 푸시값 : %d\n,peek);
push(l);
//printf(6번째 푸시값 : %d\n,peek);
}
}

}퀵소트를 재귀함수사용하지않고 하는방법입니다...
여기서 사용되는 푸시와 팝.. 이걸왜 사용하고 어떤용도로 어떤의미로 사용되는지 전혀감이안오네요..알려주셨으면합니다.

신청하기