xor xor - 1 year ago 78
Java Question

Quicksort Counter Example

Firstly (as the question title implies) I'm not looking for why the bellow partitioning method doesn't work, rather a modification to it so that it will work for the following input:

int[] a = {1,2,8,4,5,7};

Here's the
method along with some other stuff:

static int[] swap (int[] a,int i,int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
return a;

static int partition (int[] a,int l,int r){
int i = l;
int j = r;
int v = a[l];
while (true) {

while (a[i] < v) {
if (i == r) break;

while (a[j] > v) {
if (j == l) break;

if (i >= j) break;

a = swap(a,i,j);

a = swap(a, l, j);
return j;

void sort(int[] a,int l,int r){
int j = partition(a, l, r);
sort(a, l, j-1);
sort(a, j+1, r);

public static void main(String[] args) {

int[] a = {1,2,8,4,5,7};




The output is the index of the pivot returned from the
, as the index of the pivot, makes sense in terms of the definition, i.e.
everything left of the pivot is smaller and everything right of the pivot is larger
, but clearly runs into a problem in

sort(a, l, j-1);

where you have the right pointer being negative (
j-1 = 0-1 = -1
). My question again being is there a modification to the above method(s) that will maintain the definition (
everything left of the pivot is smaller and everything right of the pivot is larger
) and not run into the problem in

Answer Source

The missing part is the line

if ( l >= r ) return;

in the beginning of the sort method. This is actually the recursion stop step so it is necessary to have it anyway to prevent endless recursion. But besides that, it also solves your problem, because if you call sort(0,-1) then -1 is less than 0, so it prevents further processing of that index.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download