# Help with algorithms

I was given this algorighm to write a code for a quick sort method:

To partition a[left…right] such that a[left…j–1] are all less than or

equal to a[j], and a[j+1…right] are all greater than or equal to a[j]:

1. Set pivot to a

To partition a[left…right] such that a[left…j–1] are all less than or

equal to a[j], and a[j+1…right] are all greater than or equal to a[j]:

1. Set pivot to a

.

2. Set i = left + 1 and j = right.

3. While i ≤ j, repeat:

3.1. While i ≤ j and a

2. Set i = left + 1 and j = right.

3. While i ≤ j, repeat:

3.1. While i ≤ j and a

*≤ pivot, increment i.*

3.2. While j ≥ i and a[j] ≥ pivot, decrement j.

3.3. If i < j, swap a3.2. While j ≥ i and a[j] ≥ pivot, decrement j.

3.3. If i < j, swap a

*and a[j].*

4. If j * left, set a4. If j * left, set a

to a[j], and a[j] to pivot.

5. Terminate with answer j.

And this is the code i came up with

public static int partition1(Comparable[] a, int left, int right) {

Comparable pivot = a

5. Terminate with answer j.

And this is the code i came up with

public static int partition1(Comparable[] a, int left, int right) {

Comparable pivot = a

;

int i = left + 1;

int j = right;

while (i <= j) {

while (i <= j) {

a

int i = left + 1;

int j = right;

while (i <= j) {

while (i <= j) {

a

*.compareTo(pivot);*

i++;

}

while (j >= i) {

ai++;

}

while (j >= i) {

a

*.compareTo(pivot);*

j--;

}

if (i < j) {

aj--;

}

if (i < j) {

a

*= a[j];*

a[j] = aa[j] = a

*;*

} else if (j != left) {

a} else if (j != left) {

a

= a[j];

a[j] = pivot;

}

}

return j;

}

The problem is that this code doesn't work. Could you help me understand what im doing wrong please!

a[j] = pivot;

}

}

return j;

}

The problem is that this code doesn't work. Could you help me understand what im doing wrong please!

## Comments

The best way to check how it is working is to step through it with a debugger and see if it is doing what you think it should.

public static int partition(Comparable[] a, int left, int right) {

Comparable pivot = a

int i = left + 1;

int j = right;

while (i <= j) {

while (i <= j && a

.compareTo(pivot) <= 0) {

i++;

}

while (j >= i && a[j].compareTo(pivot) >= 0) {

j--;

}

if (i < j) {

Comparable temp = a

;a

= a[j];a[j] = temp;

}

}

if (j != left) {

a

a[j] = pivot;

numCopies +=2;

}

return j;

}

Let p be the position in the array such that a[p] is the median

of a

between left and right).

ive got this so far

int m = (left+right)/2;

int p = 0;

I am not quite following, how can you find a median from a median, or a median from 1 number?