If the outermost while loop of our implementation of quickSortInPlace (line 9 of Code Fragment 12.6) were changed to use condition left < right, instead of condition left <= right, there would be a flaw. Explain the flaw and give a specific input sequence on which such an implementation fails.

Transcribed Image Text:

/** Sort the subarray S[a.b] inclusive. */ private static void quickSortInPlace(K[] S, Comparator comp, int a, int b) { 3 // subarray is trivially sorted if (a >= b) return; int left = a; 4 5 int right = b-1; K pivot = S[b]; K temp; while (left <= right) { // scan until reaching value equal or larger than pivot (or right marker) while (left <= right && comp.compare(S[left], pivot) < 0) left++; // scan until reaching value equal or smaller than pivot (or left marker) while (left <= right && comp.compare(S[right], pivot) > 0) right--; if (left <= right) { // so swap values and shrink range temp = S[left]; S[left] = S[right]; S[right] = temp; left++; right--; %3D // temp object used for swapping 10 11 12 13 // indices did not strictly cross 14 15 16 17 18 } // put pivot into its final place (currently marked by left index) temp = S[left]; S[left] = S[b]; S[b] = temp; // make recursive calls quickSortInPlace(S, comp, a, left – 1); quickSortInPlace(S, comp, left + 1, b); 19 20 21 22 23 24 25