STEP 2.2 クイックソート (quick sort)

問題 

#define N 10

int a[N]={42,33,78,19,46,63,25,11,54,17};

とする。

[実行例] 
BEFORE : 42 33 78 19 46 63 25 11 54 17

 AFTER : 11 17 19 25 33 42 46 54 63 78

コメント

  • 再帰的に捉えよう。言葉で表現しよう。
    • 停止条件　：要素が１つなら、それ自身がソート結果
    • 再帰条件　：そうでないなら、pivotに応じて、要素を前半と後半の2つに分割し(partition)、それぞれをクイックソートする。
  • 分割統治法 (devide-and-conquer)
    • 問題を小さな問題に、（お互いが影響しないように）分割する。
    • 部分問題の解を統合することで、元の問題の解を得る。
    • n個の要素からなるデータをクイックソートする　⇒　（うまくいけば）約 n/2個の要素からなるデータをクイックソートするという2つの問題に分割。統合部分はいらない。
マージソートとクイックソート
  • マージソート：　ほぼ半分に分割し、それぞれをマージソート、その結果をマージして統合
    • いつでもほぼ半分に分割。
    • （時間）計算量は、どんな入力でも、ほぼ一定
    • ただし、マージの際、データの配列とは別に、マージ作業用の配列が必要。クイックソートに比較して、（領域）計算量が大きい。
  • クイックソート：　pivotに対応して、前半部と後半部に分割。それぞれをクイックソートすれば全体がソートされる（統合部分はない）。
    • pivotによっては、前半部、後半部のサイズが偏る
    • 計算量の議論に注意　－　教科書を　(pp.62 - 64)
    • マージソートとは異なり、作業用の配列は必要ない。（統合部分がない）
提出プログラムについて
  • 教科書を使って解答してよい。自分なりのコメントをつけよう。
  • 有名な例題なのでコードは入手できる。見るなら、しっかり読んで書けるようにしよう（よいコードを見よう！）
  • 自分なりの解答を作ってよいが、教科書の疑似コードやプログラムも理解すること。
    • 教科書と異なるコードを提出する場合は、「コードだけ送られても、読めない（読んでいる時間がありません）」。変数の役割など、コメントをつけてくれると助かります。

解答例

[未完プログラム] 

partition関数は STEP.2.1を
/* swap関数は、分割コンパイルするバージョン */
/* gcc -c 0202.c 
   gcc -o 0202 0202.obj swap.obj */

#include "swap.h" 
#define N 10
/* 大域変数 */
int a[N]={42,33,78,19,46,63,25,11,54,17};

void print_array(int left, int right);
int partition(int left, int right); 
void quick_sort(int left, int right);

void print_array(int from, int to) { /* from番目から to番目までの要素をプリント */
   int i;

   for (i = from ; i <= to; i ++)
     printf("%3d ", a[i]);

   printf("\n\n");

}

int main(void){

   /* 配列a ソート前。表示 */
   printf ("BEFORE :");
   print_array(0, N-1);

   quick_sort(0, N-1); /* クイックソート! */

   /* 配列a ソート後。表示 */
   printf (" AFTER :");
   print_array(0, N-1);

   return(0);
}

void quick_sort(int left, int right) {
  
   /*　疑似コードを参考に自作しよう。コードは簡単。納得までねばろう */


}

/* 以下はSTEP2.1 この関数がクイックソートの根幹部です。 */
int partition(int left, int right){
   int i, j, pivot;

   pivot = a[left]; /* pivotは、最左 */
   i = left+1; /* 左から右へ動くポインター */
   j = right;  /* 右から左へ動くポインター */


   /* 疑似コードを参考に作成しなさい */

}