|
You just finished the swap on the
previous page, and you can now proceed to the
last section of code from the quickSort function - the two
conditional statements:
The first if statement asks if the left variable is less
than the value of j. That is false, for left is 1 and
j is 1
also, so nothing happens.
The second if statement asks if the value stored by the
right variable is greater than i, and that too is not true
because the right value is 3, and the value of i is 3 also.
So we don't get caught by either of the if statements. There
is now nowhere to go, so the function exits.
And now, your array is sorted. Let's now look at how the
ActionScript I presented on the first page helps you to
implement Quicksort.
For the most part, quicksort is one of those algorithms that
is fairly straightforward to implement. There are no tricky
syntax or weird coding hacks that you need to use to create
a working Quicksort.
Let's start:
- function quickSort(arrayInput:Array, left:Number,
right:Number) {
The quickSort function takes in three arguments - an array,
and two numbers representing the left and right boundaries.
The array will contain a series of numbers that you wish to
sort, and left and right will refer to the index positions
of the array to set as the boundaries.
- var i:Number = left;
- var j:Number = right;
- var pivotPoint:Number =
arrayInput[Math.round((left+right)*.5)];
In the above three lines I declare and initialize the i, j,
and pivotPoint variables. Notice that i and j will be
storing the values from the left and right values, and as
you read earlier, this copy is done to ensure that left and
right values remain unmodified so that it becomes possible
to make comparisons with the modified i and j values as our
function loops.
The pivotPoint variables stores the pivot number in our
array. I choose to use a center value for the pivotPoint, so
I determine the center position by averaging the values of
the left and right boundaries. I use Math.round() to ensure
that averaging the left and right values returns an integer
value.
Onwards to the next page!
|
Fast Sorting with Quicksort
