クイックソートについて

Question

クイックソートのアルゴリズムについて学んだので、実際にCでコーディングしてみたのですが、基準点を配列の0番目にするとうまくいくのに、真ん中(右端と左端の和/2)にすると並べ替えができません。
エラーは出ませんが、順番がおかしくなります。

#include<stdio.h>
#include<stdlib.h>
#define N 10
void qui_sort(int,int);
 
int d[N]={2,8,5,3,4,9,1,6,0,7};
int lp=0,rp=N-1,pivot;
int tmp,i;
 
int main(void){
      qui_sort(lp,rp);
      for(i=0;i<10;i++)
             printf("%d",d[i]);
      printf("\n\n");
      system("pause");
      return 0;
}
void qui_sort(int lp,int rp){
      int L,R,pivot;
      L=lp;
      R=rp;
      pivot=L;   //ここを(L+R)/2にするとおかしくなる
 
      while(L<R){
           while(d[L]<d[pivot])
                    L++;
           while(d[pivot]<d[R])
                    R--;
           if(L<R){
                    tmp=d[L];
                    d[L]=d[R];
                    d[R]=tmp;
           }
       }
       if(lp<pivot-1)
                 qui_sort(lp,pivot-1);
       if(pivot+1<rp)
                 qui_sort(pivot+1,rp);
}
 

それと、テキスト等にあるクイックソートではほとんどがポインタ渡しをしているのですが、その意味と利点についても教えていただきたいです。

Comments

[jimbe]

学ばれたアルゴリズムにはどのように書かれていましたか.

Answer 1

それと、テキスト等にあるクイックソートではほとんどがポインタ渡しをしているのですが、その意味と利点についても教えていただきたいです。

グローバル変数の d しかソートできないと、
2つ以上の配列をソートしたい場合困りますよ。

例えば、次の 2つの配列をソートしようとします。
int a[10] = { 2, 8, 5, 3, 4, 9, 1, 6, 0, 7 };
int b[5] = { 3, 1, 4, 2, 5 };

void quick_sort(int *d, int left, int right);だったら、
quick_sort(a, 0, 9); や quick_sort(b, 0, 4); と呼び出すだけで済みます。

Answer 2

クイックソートの解説は多数あると思いますので, 幾つか参照されては如何でしょう.
ご提示のコードでは, ピボットの扱い等が間違っている気が致しました.

#include<stdio.h>
#include<stdlib.h>

#define N 10
int d[N]={2,8,5,3,4,9,1,6,0,7};

void print(char* post) {
  for(int i=0;i<N;i++) printf("%d",d[i]);
  printf(post);
}
void swap(int i, int j) {
  int t=d[i]; d[i]=d[j]; d[j]=t;
}
void qui_sort(int lp,int rp){
  int l=lp;
  int r=rp;
  int pivot=d[(l+r)/2];
  printf("l=%d,r=%d,pivot=%d\n",l,r,pivot);
  print(" -> ");
  while(1){
    while(d[l]<pivot) l++;
    while(pivot<d[r]) r--;
    if(l>=r)break;
    swap(l++, r--);
  }
  print("\n");
  if(lp<l-1) qui_sort(lp,l-1);
  if(r+1<rp) qui_sort(r+1,rp);
}
int main(void){
  qui_sort(0,N-1);
  print("\n\n");
  //system("pause");
  return 0;
}

Answer 3

テキスト等にあるクイックソートではほとんどがポインタ渡しをしているのですが

ポインタ渡しじゃないと、呼び出し側の変数の内容を変更できないのでそうなってますね