퀵정렬 ?
글쓴이: nayana / 작성시간: 금, 2004/05/07 - 9:39오전
#include <stdio.h>
#include <stdlib.h>
#define N 100
void quick_sort2( int a[], int n );
void init_stack( void );
int pop( void );
int push( int t );
int is_stack_empty( void );
int top;
int stack[N];
int main ( void )
{
int i, n, score[N];
;
printf("Number of data?\t");
scanf("%d", &n);
for ( i = 0; i < n; i++ )
{
printf("score[%d] = ", i );
scanf("%d", &score[i]);
}
quick_sort2( score, n );
for ( i = 0; i < n; i++ )
printf("(%d)\t %d\n", i + 1, score[i]);
return 0;
}
void init_stack( void )
{
top = -1;
}
int push( int t )
{
if ( top >= N - 1 )
{
printf("Stack overflow\n");
return -1;
}
stack[++top] = t;
return t;
}
int pop( void )
{
if ( top < 0 )
{
printf("Stack underflow\n");
return -1;
}
return stack[top--];
}
int is_stack_empty( void )
{
return ( top == -1 );
}
void quick_sort2( int a[], int n )
{ /*난수로 분할 값 지정*/
int v, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = n - 1;
push( r );
push( l );
while ( !is_stack_empty())
{
l = pop();
r = pop();
if ( r - l + 1 > 1 )/*종료조건*/
{
t = rand()%( r - l + 1 ) + 1; // 난수 발생
v = a[t]; /* v가 축값이 됨*/
a[t] = a[r];
a[r] = v;
i = l - 1;
j = r;
while ( 1 )/*분할*/
{
while ( a[++i] < v );
while ( a[--j] < v );
if ( i >= j ) break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
t = a[i];/*축값과 i 값을 교환*/
a[i] = a[r];
a[r] = t;
push( r );
push( i + 1 );
push( i - 1 );
push( l );
}
}
}
그냥 qsort함수를 써서 구현해도 되지만 제 나름대로 공부하고 있는 입장이어서
책을 보면서 공부하고 있습니다. 축값을 난수로 발생시켜서 처리해볼려고하는데. 잘안됩니다.t = rand()%( r - l + 1 ) + 1; 이부분이 잘못된거 같은데...
^^정렬이 잘안되네요?
Forums:


댓글 달기