これは宿題用です。最終的にはこのコードを MIPS アセンブリに変換する予定ですが、それは私にとって簡単な部分です。私はこのコードを何時間もデバッグしており、教授のオフィスアワーにも行っていますが、まだクイックソートアルゴリズムを機能させることができません. これは、問題領域がどこにあると私が考えるかについての私のコメントのいくつかと一緒にコードです:
// This struct is in my .h file
typedef struct {
// v0 points to the first element in the array equal to the pivot
int *v0;
// v1 points to the first element in the array greater than the pivot (one past the end of the pivot sub-array)
int *v1;
} PartRet;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
PartRet partition(int *lo, int *hi) {
// Will later be translating this to MIPS where 2 values can be returned. I am using a PartRet struct to simulate this.
PartRet retval;
// We must use the last item as the pivot
int pivot = *hi;
int *left = lo;
// Take the last value before the pivot
int *right = hi - 1;
while (left < right) {
while((left < hi) && (*left <= pivot)) {
++left;
}
while((right > lo) && (*right > pivot)) {
--right;
}
if (left < right) {
swap(left++, right--);
}
}
// Is this correct? left will always be >= right after the while loop
if (*hi < *left) {
swap(left, hi);
}
// MADE CHANGE HERE
int *v0 = hi;
int *v1;
// Starting at the left pointer, find the beginning of the sub-array where the elements are equal to the pivot
// MADE CHANGE HERE
while (v0 > lo && *(v0 - 1) >= pivot) {
--v0;
}
v1 = v0;
// Starting at the beginning of the sub-array where the elements are equal to the pivot, find the element after the end of this array.
while (v1 < hi && *v1 == pivot) {
++v1;
}
if (v1 <= v0) {
v1 = hi + 1;
}
// Simulating returning two values
retval.v0 = v0;
retval.v1 = v1;
return retval;
}
void quicksort(int *array, int length) {
if (length < 2) {
return;
}
PartRet part = partition(array, array + length - 1);
// I *think* this first call is correct, but I'm not sure.
int firstHalfLength = (int)(part.v0 - array);
quicksort(array, firstHalfLength);
int *onePastEnd = array + length;
int secondHalfLength = (int)(onePastEnd - part.v1);
// I have a feeling that this isn't correct
quicksort(part.v1, secondHalfLength);
}
オンラインのコードサンプルを使用してコードを書き直そうとしましたが、要件は lo および hi ポインターを使用することですが、これを使用しているコードサンプルは見つかりませんでした。コードをデバッグすると、特にピボットが配列内の最小の要素である場合に、一部の配列でのみコードが機能し、他の配列では機能しなくなります。