C言語 配列を使わないクイックソート¶
下の配列を用いたクイックソートを、 配列を使わずポインタを用いたクイックソートにしたいのだがまったくソートされない。 恐らくpivotやiptr,jptrなどポインタにしたとこが動きまくってると思うのだが、 いったいどうしたことか…。
/* Qソートを行う */
void qsort(int *left, int *right)
{
int i, j, pivot;
int *iptr, *jptr; /* i, jのポインタ */
iptr = left;
jptr = right;
pivot = *(right - (__w64 int)(right - left) / 2); //中央値の設定
while(1)
{
while (*iptr < pivot) /* pivot より大きい値が */
iptr++; /* 出るまで i を増加させる */
while (pivot < *jptr) /* pivot より小さい値が */
jptr--; /* 出るまで j を減少させる */
if (*iptr >= *jptr) /* i >= j なら */
break; /* 無限ループから抜ける */
swap(iptr, jptr); /* iとjを交換 */
iptr++; /* 次のデータ */
jptr--;
}
if (left < iptr - 1) /* 基準値の左に 2 以上要素があれば */
qsort(left, iptr - 1); /* 左の配列を Q ソートする */
if (jptr + 1 < right) /* 基準値の右に 2 以上要素があれば */
qsort(jptr + 1, right); /* 右の配列を Q ソートする */
}
/* 要素を交換する */
void swap(int *i, int *j)
{
int temp;
temp = *i;
*i = *j;
*j = temp;
}
void qsort(int x[], int left, int right)
{
int i, j;
int pivot;
i = left; /*
ソートする配列の一番小さい要素の添字 */
j = right; /*
ソートする配列の一番大きい要素の添字 */
pivot = x[(left + right) / 2]; /* 基準値を配列の中央付近にとる */
while(1)
{
while (x[i] < pivot) /* pivot より大きい値が */
i++; /* 出るまで i を増加させる */
while (pivot < x[j]) /* pivot より小さい値が */
j--; /* 出るまで j を減少させる */
if (i >= j) /* i >= j なら */
break; /* 無限ループから抜ける */
swap(x, i, j); /* x[i] と x[j]を交換 */
i++; /* 次のデータ */
j--;
}
if (left < i - 1) /* 基準値の左に 2 以上要素があれば */
qsort(x, left, i - 1); /* 左の配列を Q ソートする */
if (j + 1 < right) /* 基準値の右に 2 以上要素があれば */
qsort(x, j + 1, right); /* 右の配列を Q ソートする */
}
/* 配列の要素を交換する */
void swap(int x[], int i, int j)
{
int temp;
temp = x[i];
x[i] = x[j];
x[j] = temp;
}