본문 바로가기

C.E/File processing

C++ 퀵정렬 소스(quick sort)

/*
2014.05.20
http://breath91.tistory.com
by_jacob(apodis91@naver.com/apodis91@ks.ac.kr)
*/ 
#include 
#include 
#include 

#define Max_Size 200000           // 배열 사이즈 정의
#define Rand_Num() rand() % 2000000        // 난수발생 전처리
#define SWAP( x, y, t ) ((t) = (x), (x) = (y), (y) = (t)) // 숫자 교환 전처리


//시간함수관련
time_t t1, t2;


void Quick_sort( int*, int, int );       // 정렬 함수
int  Partition ( int*, int, int );       // 분할 함수

int main( )
 {
	 //시간함수관련
	 time(&t1);

  int quick[ Max_Size ] = { 0, };       // 정수형 배열 선언
 int i, j, size = sizeof( quick ) / 4;     // 배열 갯수 선언
  
  srand( ( int ) time ( NULL ) );       // 난수 발생
 
  for( i = 0; i < Max_Size; i++ )
   quick[ i ] = Rand_Num();       // 난수를 배열에 저장
 
  fputs( "▶ Before : ", stdout );
  for( i = 0; i < Max_Size; i++ )  printf(" %d ", quick[ i ] );// 정렬 전 출력
 printf("\n");
  
  Quick_sort( quick, 0, size - 1 );      // 정렬 함수 호출
 
  fputs( "▶ After  : ", stdout );
  for( i = 0; i < Max_Size; i++ )  printf(" %d ", quick[ i ] );// 정렬 후 출력
 printf("\n");

 //시간함수관련
   time(&t2);
   printf("총 %f초가 걸렸습니다.", difftime(t2,t1));

  return 0;            // 정상 종료


}

void Quick_sort( int* quick, int begin, int end )   // 정렬 함수
{
  int i = 0;

 if( begin < end )          // 배열의 크기만큼 함수 호출
 {
   i = Partition( quick, begin, end );     // L 값 i에 저장
  Quick_sort( quick, begin, i - 1 );     // L 값 재귀 호출
  Quick_sort( quick, i + 1, end );     // R 값 재귀 호출
  }
 }


int Partition( int* quick, int begin, int end )    // 분할 함수
{
  int i = 0, j = 0, pivot = 0, L = 0, R = 0, temp = 0; // 변수 선언

 pivot = ( begin + end ) / 2;       // 원소의 가운데 값을 pivot에 대입
 L = begin;            // L은 첫 인덱스
 R = end;            // R은 마지막 인덱스
 
  while( L < R )           // 배열의 갯수만큼 반복
 {
   while( quick[ L ] < quick[ pivot ] && ( L < R ) ) L++;// L이 pivot보다 작고 R보다 작을때까지 L 증가
  while( quick[ R ] >= quick[ pivot ] && ( L < R ) ) R--;// R이 pivot보다 크거나 같고 L보다 클때까지 R증가 
  if( L < R )  SWAP( quick[ L ], quick[ R ], temp );// R이 L보다 크면 원소 교환
 }
  SWAP( quick[ pivot ], quick[ R ], temp );    // 그렇지 않으면 R과 pivot 교환
 
  return L;            // L 반환
}

맨아래 </time.h></stdlib.h></stdio.h>는 지워주시고 사용하시면 됩니다. ps. 저거 왜 남는지 아시는분 없으신가요 ㅠㅠ