資料結構›Ch7 搜尋與排序
第 45 題/共 76 題
◀ DS 45/76
45. Quicksort、Hoare Partition、C
#DS-07-045易QuicksortHoare PartitionC
題組題幹(本題:⑤,共 3 小題)點擊展開

The following code is a C implementation of a sorting algorithm:

void FSort(int* a, int left, int right)
{
    if (left < right) {
        static int c = 0;
        int i = left, j = right + 1;
        int d = a[left];
        do {
            do i++; while (a[i] < d);
            do j--; while (a[j] > d);
            if (i < j) {
                int z = a[i]; a[i] = a[j]; a[j] = z;
            }
        } while (i < j);
        int z = a[left]; a[left] = a[j]; a[j] = z;
        printf("c=%d\n", ++c);
        FSort(a, left, j - 1);
        FSort(a, j + 1, right);
    }
}

Assume that we want to use this function to sort a 10-element array m, given by

int m[] = { 3,5,9,8,2,0,4,1,6,7 };

For the above array m, assuming that the call above is correct, what is the largest value of c in the text output?

📄 交大113
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch7 搜尋與排序
本章題號 · 41–60 / 76