[자료구조] by C언어 -#08 [Quick sort]

ㅡㅡㅡㅡㅡ

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(a, b) { int c = a; a = b; b = c; } // "교환"
#define MAX 10

void quick_sort(int* arr, int start, int end) { // arr=숫자열 / start: 0부터. / end: MAX-1 = 9부터.//
   int pivot = arr[(end + start) / 2];  // (0+9)/2 => 4. pivot에 4 저장.
   int i = start;  // i에 0저장.
   int j = end;    // j에 9저장.
   while (i <= j) {  // j가 i 보다 크거나 같은가? 
      while (arr[i] < pivot) {  // i번째 인덱스의 값이 pivot보다 큰 동안 ++i;
         ++i;  // 계속 더하다가 arr[i]가 pivot보다 더 크거나, arr[i]와  pivot값이 같아지는 경우 while문 탈출.  
      }
      while (arr[j] > pivot) {  // j번째 인덱스의 값이 pivot보다 큰 동안 --j;
         --j;  // 계속 빼다가 arr[j]가 더 작거나, arr[j]와 pivot값이 같아지는 경우 while문 탈출.
      }
      if (i <= j) { // j가 i 이상인가? 
         SWAP(arr[i], arr[j]);  // 서로 값 바꾸기.
         ++i; 
         --j;
      }
   }

   if (start < j) {
      quick_sort(arr, start, j);
   }
   if (i < end) {
      quick_sort(arr, i, end);
   }

}

void print_array(int* data) { // 숫자열 출력함수. 
   for (int i = 0; i < MAX; ++i) {
      printf("%d\t", data[i]); //  \t : 탭 
   }
   printf("\n");
}

void set_data(int* data) {
   srand(time(0));
   for (int i = 0; i < MAX; ++i) {
      data[i] = rand() % 1000; // 0~999중 한 수를 랜덤으로 출력.
   }
}

void main() {
   int a[MAX] = { 0, };           // MAX=10 //10개의 정수를 저장가능한 숫자열 생성. 
   set_data(a);                        // 테스트용 난수 생성 //인덱스에 0~999중 무작위로 숫자하나 생성. 
   print_array(a);                      // 정렬 전의 숫자열 출력.
   quick_sort(a, 0, MAX - 1);          // 퀵소트 호출. 
   print_array(a);                            // 정렬 후의 숫자열 출력.
}

ㅡㅡㅡㅡㅡ