クイックソートについて

[はじめ]

このような正解例があるのですが、
[[[　　正解例　　]]]
出力結果:
1行目：Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: before: 792 530 324 587 202 691 721 734 54 792
2行目：(0, 9) pivot: 0, center: 8
3行目： 54 530 324 587 202 691 721 734 792 792
4行目：(0, 7) pivot: 3, center: 4
5行目： 54 530 324 202 587 691 721 734 792 792
6行目：(0, 3) pivot: 3, center: 1
7行目： 54 530 324 202 587 691 721 734 792 792
8行目：(1, 3) pivot: 2, center: 2
9行目： 54 202 324 530 587 691 721 734 792 792
10行目：(2, 3) pivot: 3, center: 3
11行目： 54 202 324 530 587 691 721 734 792 792
12行目：(4, 7) pivot: 5, center: 5
13行目： 54 202 324 530 587 691 721 734 792 792
14行目：(5, 7) pivot: 6, center: 6
15行目： 54 202 324 530 587 691 721 734 792 792
16行目：(6, 7) pivot: 7, center: 7
17行目： 54 202 324 530 587 691 721 734 792 792
18行目：(8, 9) pivot: 9, center: 9
19行目： 54 202 324 530 587 691 721 734 792 792
20行目：after: 54 202 324 530 587 691 721 734 792 792

自分の出力結果は以下のようになり、18行目だけ違ってしまいます。

1行目：Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: before: 792 530 324 587 202 691 721 734 54 792
2行目：(0, 9) pivot: 0, center: 8
3行目： 54 530 324 587 202 691 721 734 792 792
4行目：(0, 7) pivot: 3, center: 4
5行目： 54 530 324 202 587 691 721 734 792 792
6行目：(0, 3) pivot: 3, center: 1
7行目： 54 530 324 202 587 691 721 734 792 792
8行目：(1, 3) pivot: 2, center: 2
9行目： 54 202 324 530 587 691 721 734 792 792
10行目：(2, 3) pivot: 3, center: 3
11行目： 54 202 324 530 587 691 721 734 792 792
12行目：(4, 7) pivot: 5, center: 5
13行目： 54 202 324 530 587 691 721 734 792 792
14行目：(5, 7) pivot: 6, center: 6
15行目： 54 202 324 530 587 691 721 734 792 792
16行目：(6, 7) pivot: 7, center: 7
17行目： 54 202 324 530 587 691 721 734 792 792
18行目：(8, 9) pivot: 8, center: 9
19行目： 54 202 324 530 587 691 721 734 792 792
20行目：after: 54 202 324 530 587 691 721 734 792 792

前に
10行目：(2, 3) pivot: 3, center: 3　が　　10行目：(2, 3) pivot: 2, center: 3
16行目：(6, 7) pivot: 7, center: 7　が　　16行目：(6, 7) pivot: 6, center: 7
18行目：(8, 9) pivot: 9, center: 9　が　　18行目：(8, 9) pivot: 8, center: 9

となっていたので、
else if(right - left <= 1)
return(right);
という条件を付けました。
すると10行目、16行目は改善されたのですが
18行目は、改善されません。
以下のプログラムなのですが、どこを修正していけばいいかわからず、困っています。
どなたか教えていただけないでしょうか？
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
void quick(int *, int, int);
#define N 10
int main(void){
int a[N] = {0};
int k = 0;
for (k = 0; k < N ; k++) {
printf("Input a number: ");
scanf("%d", &a[k]);
}
printf("before: ");
for (k = 0; k < N; k++) {
printf("%4d", a[k]);
}
printf("\n");
quick(a, 0, N - 1);

printf("after: ");
for (k = 0; k < N; k++) {
printf("%4d", a[k]);
}
printf("\n");
}
void check(int a[], int left, int right, int p, int center) {
int i = 0;
printf("(%d, %d) pivot: %d, center: %d\n", left, right, p, center);
for (i = 0; i < N; i++) {
printf("%4d", a);
}
printf("\n");
}
int pivot(int a[], int left, int right) {
//
int x = (left + right) / 2;
int a1 = a[left];
int a2 = a[x];
int a3 = a[right];
if((a1==a2) && (a2==a3))
return(left);
else if(right - left <= 1)
return(right);
else if(a1==a2)
return(left);
else if(a1==a3)
return(right);
else if(a2==a3)
return(x);
else if((a1<a2) && (a2<a3))
return(x);

else if((a1<a3) && (a3<a2))
return(right);

else if((a2<a1) && (a1<a3))
return(left);

else if((a2<a3) && (a3<a1))
return(right);


else if((a3<a1) && (a1<a2))
return(left);

else if((a3<a2) && (a2<a1))
return(x);
}
int swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
int partition(int a[], int left, int right, int p) {
//
int i,j;
i = left;
j = right;

while(1){

while(a < p){
i++;
}
if(i >= right)
break;
while(p <= a[j]){
j--;
if(j==left){
if(i==left){
i++;
}
break;
}
}
if(j <= left) {
break;
}
if(i>=j){
break;
}
swap(&a, &a[j]);
i = left;
j = right;
}
return(i);
}
void quick(int a[], int left, int right) {
int p = 0; // 軸
int center = 0; // 配列を分ける位置
//
p = pivot(a, left, right);
center = partition(a, left, right, a[p]);
if(right-left<=0)

return;
check(a, left, right, p, center);
quick(a, left, center - 1);
quick(a, center, right);
}
//

[softya（ソフト屋)]

codeタグを利用頂く様にお願いします。　http://dixq.net/board/board.html#k10
それと再現テストのために入力データも正確に記入して下さい。

[はじめ]

すいません。見落としてました。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
void quick(int *, int, int);
#define N 10
int main(void){
int a[N] = {0};
int k = 0;
for (k = 0; k < N ; k++) {
printf("Input a number: ");
scanf("%d", &a[k]);
}
printf("before: ");
for (k = 0; k < N; k++) {
printf("%4d", a[k]);
}
printf("\n");
quick(a, 0, N - 1);

printf("after: ");
for (k = 0; k < N; k++) {
printf("%4d", a[k]);
}
printf("\n");
}
void check(int a[], int left, int right, int p, int center) {
int i = 0;
printf("(%d, %d) pivot: %d, center: %d\n", left, right, p, center);
for (i = 0; i < N; i++) {
printf("%4d", a[i]);
}
printf("\n");
}
int pivot(int a[], int left, int right) {
// 
int x = (left + right) / 2;
int a1 = a[left];
int a2 = a[x];
int a3 = a[right];
if((a1==a2) && (a2==a3))
return(left);
else if(right - left <= 1)
return(right);
else if(a1==a2)
return(left);
else if(a1==a3)
return(right);
else if(a2==a3)
return(x);
else if((a1<a2) && (a2<a3))
return(x);

else if((a1<a3) && (a3<a2))
return(right);

else if((a2<a1) && (a1<a3))
return(left); 

else if((a2<a3) && (a3<a1))
return(right);


else if((a3<a1) && (a1<a2))
return(left);

else if((a3<a2) && (a2<a1))
return(x);
}
int swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
int partition(int a[], int left, int right, int p) {
// 
int i,j;
i = left;
j = right;

while(1){

while(a[i] < p){
i++;
}
if(i >= right)
break;
while(p <= a[j]){
j--;
if(j==left){
if(i==left){
i++;
}
break;
}
}
if(j <= left) { 
break;
} 
if(i>=j){
break;
}
swap(&a[i], &a[j]);
i = left;
j = right;
}
return(i);
}
void quick(int a[], int left, int right) {
int p = 0; // 軸
int center = 0; // 配列を分ける位置
// 
p = pivot(a, left, right);
center = partition(a, left, right, a[p]);
if(right-left<=0)

return;
check(a, left, right, p, center);
quick(a, left, center - 1);
quick(a, center, right);
}

[はじめ]

入力データです。
792
530
324
587
202
691
721
734
54
792

[box]

自分の出力結果は以下のようになり、18行目だけ違ってしまいます。

正解例と食い違っていること自体に、本当に問題があるのでしょうか。
別に違っていてもいいのではないでしょうか。

[はじめ]

大学の課題なのですが、採点が自動で、正解例に一致しないといけないとのことなので、これではダメなようです。

前述のとおり、
10行目：(2, 3) pivot: 3, center: 3　が　　10行目：(2, 3) pivot: 2, center: 3
16行目：(6, 7) pivot: 7, center: 7　が　　16行目：(6, 7) pivot: 6, center: 7
18行目：(8, 9) pivot: 9, center: 9　が　　18行目：(8, 9) pivot: 8, center: 9

となっていたところ
rightとleftの位置が隣り合っているという条件で
else if(right - left <= 1)
return(right);
こう場合分けたしたつもりなのですが、
なぜ10行目、16行目は改善され、
18行目は、改善されないままなのでしょうか？

[box]

そもそも、pivot()の実装って、今ほどややこしくしなくてもいいような気がします。
そこまでいろいろと判断しなくてはならないものなんでしょうか。

[のり]

ものすごーくみずらいプログラムです。
インデントをちゃんとしてから貼ってほしかった。

単純にpivot=(left + right )/2;
となってるので最後は(9+9)/2=8
なので最後にpivot=8,center=9となる。

というかleft=9となった時点で終わりでしょ？
それ以上続けるからこうなる。

後プログラムにはコメントを振ってほしい。
いちいち変数がどういう働きをしてるかを確かめるのに時間がかかる。

最後にどうでもいいことだが、int mainで始まっているので、
return で終わるべきではないでしょうか？
もう一個なんでpivotとcenterをわけてるのだろうか？
普通は一緒だと思うんだけどな。オーダーのこと考えているのかな？
このやり方だと必ずo(nlogn)になるのかな？

[のり]

言い忘れた。
入力、出力がきまってるのならなんでscanfでキーボード入力
しているのでしょうか？あらかじめ配列に格納してはだめなの
でしょうか？

[beatle]

最後にどうでもいいことだが、int mainで始まっているので、
return で終わるべきではないでしょうか？

C99しか読んでませんが，規格としてはreturnに出会わずにmainの最後の}まで到達した場合，0を返すそうです．