퀵 정렬(Quick Sort)

주어진 파일을 특정한 키값보다 작은 값을 갖는 레코드들과 큰 값을 갖는 레코드들로 분리하여, 1개의 파일을 논리적으로 2개의 부 파일로 재배열하고 각각의 부 파일에 대해서 순환적으로 같은 퀵 정렬을 적용해 파일을 정렬하는 방법.

 

C. A. Hore가 고안한 정렬로 첫 번째 데이터를 중간 값으로 설정하고 그 중간 값을 대상으로 왼쪽은 작은 값들을 오른쪽은 큰 값들을 배치하여 대상 자료를 부분적으로 나누어 가면서 되부름 방식으로 반복 분류시켜 정렬하는 방식. 순환프로그램을 수행하기 위해서 보조기억공간으로 스택을 이용한다.

 

이 정렬 방식은 이미 정렬되어 있는 자료를 정렬할 때는 최악의 경우가 발생한다.

 

C언어]

//정수형에 대한 오름차순 퀵정렬을 함수화하면 아래와 같다.

void QuickSort(int s, int e, int R[])

{

   //int s : 정렬될 값들이 들어 있는 시작 방 번호 변수

   //int e : 정렬될 값들이 들어 있는 끝 방 번호 변수

   //int R[] : 정렬될 값들이 있는 배열 변수

   int a; //a는 시작 방(왼쪽 방)을 대신하는 변수로 선언

   int b; //b는 끝 방(오른쪽 방)을 대신하는 변수로 선언

   int imsi;//임의의 값을 잠시 저장할 변수

   int key;//비교할 값을 키 값으로 할 변수

 

   if(e>s) { //끝 방 번호가 시작 방 번호 보다 크다면

      key=R[e];//끝 방 번호가 갖고 있는 값을 key에 저장.

      a=s-1; //시작 방 번호에 1을 뺀 수를 a 변수에 저장.

      b=e; //끝 방 번호를 b 변수에 저장.

      while(1)

      {

         //시작 방을 1씩 증가시키면서 key값보다 큰 값이 나오면 반복문을 벗어난다.

         while(R[++a] < key);

         //끝 방을 1씩 감소시키면서 key값보다 작은 값이 나오면 반복문을 벗어난다.

         while(R[--b] > key);

         if(a>=b) break; //시작 방 번호가 끝 방 번호 보다 크면 반복문을 벗어나게 한다.

         imsi=R[a]; //시작 방 값이 끝 방 값 보다 크기 때문에

         R[a]=R[b]; //시작 방이 갖고 있는 값과 끝 방이 갖고 있는 값을 교환한다.

         R[b]=imsi;

      }

      imsi=R[a]; //왼쪽 방이 갖고 있는 값을 key 값으로 한 끝 방의 값과 교환한다.

      R[a]=R[e];

      R[e]=imsi;

      QuickSort(s,a-1,R); //재귀호출하여 끝 방을 1씩 감소하면서 QuickSort를 진행한다.

      QuickSort(a+1,e,R); //재귀호출하여 시작 방을 1씩 증가하면서 QuickSort를 진행한다.

   }

}

 

 

출처]

한국통신기술협회 : 퀵 정렬(Quick Sort)

실전! 초보가 최고가 되는 C :  퀵 정렬(Quick Sort, p213)

 

 

참고 문제]

 

 

 

※ 10월 25일은 독도의 날입니다.

대한민국의 아름다운 영토, 독도의 여름