I need help with this. Java !! Sorting

Here are the basic algorithm for the quicksort, given in pseudo-code. This is not Java.

QuickSort

quickSort(array): quickSort(array, 0, array.length)

quickSort(array, lo, hi): if lo ? high: return pivot = partition(array, lo, hi) quickSort(array, lo, pivot-1) quickSort(array, pivot+1, hi)

Example:

Consider the following eight-element array of letters. This could be a subarray of a larger array, with the endpoints of the subarray indicated by the brackets.

[ L D G Q A R B X ]

For visual simplicity, the brackets delimiting the subarray won't be repeated.

The first value in the subarray is L. We can store that in a separate variable.

var = L

This essentially opens up an empty spot where the pivot value L was.

_ D G Q A R B X

The task is to process through the subarray. We need to keep track of the two ends of the subarray where work needs to occur.

_ D G Q A R B X > <

To start the partition process, we will fill in the blank spot. An obvious choice is to move the values like this, staring at the low end and update the "edge" indicator.

_ D G Q A R B X > <

D _ G Q A R B X > <

D G _ Q A R B X > <

We can't continue because the next value belongs on the other side. So, now what? We start at the other end, the high end, looking for values to move into the empty spot:

D G _ Q A R B X > <

And move it, and update the indicator.

D G B Q A R _ X > <

As it turns out, this is not the most efficient way to approach this.

Also the meaning of the two indicators isn't always precisely consistent.

We can address both of these issues by starting at the high end of the subarray. The edge indicators show places that are not yet processed.

_ D G Q A R B X > <

_ D G Q A R B X > <

When a value less than the pivot value is encountered, it is moved to the empty spot, at the low end.

B D G Q A R _ X > <

And the process continues from the low end:

B D G Q A R _ X > <

B D G Q A R _ X > <

B D G Q A R _ X > <

When a value larger than the pivot is encountered, it is moved to the high end edge:

B D G _ A R Q X > <

And we continue from the location just "filled":

B D G _ A R Q X > <

B D G _ A R Q X > <

When a smaller value is encountered, it is move to the low end indication, the empty spot:

B D G A _ R Q X > <

And we continue from the low end:

B D G A _ R Q X ^

Eventually, the two endpoints will meet somewhere in the subarray, and the pivot value is placed in that location.

B D G A L R Q X ^

That index value is returned by the partition function.

The next iteration would work on the two resulting subarrays indicated / created by the pivot.

[ B D G A ] L [ R Q X ] ^

Partition Algorithm

partition(array, lo, hi): pivot = array[lo] while lo < hi: while lo < hi and array[hi] ge; pivot: hi -- array[lo] = array[hi] while lo < hi and array[lo] le; pivot: lo ++ array[hi] = array[lo] array[lo] = pivot return lo

The answer in you txt file should be like this:

==========================================================

initial array: [ L D G Q A R B X ] pivot: L next iteration: [ B D G A ] L [ R Q X ] pivots: B R next iteration: [ A ] B [ G D ] L [ Q ] R [ X ] pivots: A G Q X next iteration: A B [ D ] G L Q R X pivot: D sorted array: A B D G L Q R X

=====================================================================

Instructions

Now consider this array instead: [ L D P G B M T X F W ] . Your answer format should look as shown in bold txt above.