Quick sort function not working...

[krycek]

OK, I have just finished coding my quick sort function... and it doesn't work :S I think it may be something to do with the fact that it recursively calls an inner function... but I dunno. I have tried doing it with the inner function outside, and I get the same result.

Could someone who has some knowledge of the quick sort algorithm please cast their eye over this? My bubble sort (easy) and radix sort (not so easy) work fine...


//----- Swap Array Items -----------------------------------------------------------------------------------------------
Array.prototype.swap = function(firstIndex, secondIndex) {
// Swaps items firstIndex and secondIndex of an array.
if (firstIndex < 0) firstIndex = this.length + firstIndex
if (secondIndex < 0) secondIndex = this.length + secondIndex
if (this[firstIndex] == this[secondIndex]) return
var tempIndex = this[firstIndex]
this[firstIndex] = this[secondIndex]
this[secondIndex] = tempIndex
}

//----- Compare Array Items --------------------------------------------------------------------------------------------
Array.prototype.compare = function(firstIndex, secondIndex) {
// Compares items firstIndex and secondIndex of an array.
if (firstIndex < 0) firstIndex = this.length + firstIndex
if (secondIndex < 0) secondIndex = this.length + secondIndex
return (this[firstIndex] > this[secondIndex])
}

//----- Quick Sort Array -----------------------------------------------------------------------------------------------
Array.prototype.qsort = function(order) {
var tempArray = this.copy()
doQSort(0, tempArray.length)

function doQSort(start, end) {
if (end - start > 1) {
var lastlow = start
for (var i = start + 1; i < end; i++) {
if (tempArray.compare(start, i)) {
tempArray.swap(i, lastlow++)
}
}
tempArray.swap(start, lastlow)
doQSort(start, lastlow)
doQSort(lastlow + 1, end)
}
}
return tempArray
}


Try doing the following:


var testArray = new Array(1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 5, 3, 1, 1, 3, 3, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1)
var output = ""
for (var c = 0; c < testArray.length; c++) {
output+= "" + testArray[c] + ", "
}
alert(output)
testArray = testArray.qsort()
var output = ""
for (var c = 0; c < testArray.length; c++) {
output+= "" + testArray[c] + ", "
}
alert(output)


See, the result I get is:

1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 5, 3, 3, 3, 3

...which is obviously not sorted properly, although it has changed.

Cheers everyone!

::] krycek [::

[krycek]

...since posting the above, I have written the fourth and final sorting algorithm that I am currently doing, the merge sort. It uses an inner function just like the quick sort... but it works fine.

That means that there is something wrong with my actual method on the quick sort... but I can't see where! Can anyone help...?

The code for the merge sort is here if anyone wants to play with it. I will be tidying it up a little but it works.


//----- Merge Sort Array -----------------------------------------------------------------------------------------------
Array.prototype.msort = function(order) {
var tempArray = this.copy()
doMSort(0, tempArray.length)

function doMSort(start, end) {
if (end - start > 1) { // Recursively merge sort
// Merge sort each half of tempArray
var mid = parseInt((start + end) / 2)
doMSort(start, mid)
doMSort(mid, end)

// Merge the two halves
var tempArray2 = new Array() // Temporary array
var j1 = start
var j2 = mid
for (var i = 0; i < end - start; i++) {
if (j1 >= mid) {
tempArray2[i] = tempArray[j2++]
} else if (j2 >= end) {
tempArray2[i] = tempArray[j1++]
} else if (tempArray[j1] <= tempArray[j2]) {
tempArray2[i] = tempArray[j1++]
} else {
tempArray2[i] = tempArray[j2++]
}
}
for (i = 0; i < end - start; i++) {
tempArray[i + start] = tempArray2[i]
}
}
}
return tempArray
}


::] krycek [::

[beetle]

Looks like it's time to release an array API there, krycek ;) I'll check my quick sort algo against yours in a bit. FYI, thanks for keening me on to the concept of inner functions....I got my user-defined bubblesort going without any globals. Here it is using a couple differen user-defined sorts.function Array.prototype.usort(sortHandler, i){
this.sort(eval(sortHandler));

function sortByIndex(a, b) {
if (a[i] == b[i]) return 0;
return (a[i] < b[i]) ? -1 : 1;
}

function sortByLastLetter(a,b) {
var aa = a[i]; var bb = b[i];
if (aa.substring(aa.length-1) == bb.substring(bb.length-1)) return 0;
return (aa.substring(aa.length-1) < bb.substring(bb.length-1)) ? -1 : 1;
}
}

function Array.prototype.dump() {
var a = "";
for (var i in this)
if (typeof this[i] != 'function') a+= i + " : " + this[i] + "\n";
alert(a);
}

var myData = [
['werg',4],
['gikl',8],
['jsry',1],
['rewt',1]
];

myData.dump();
myData.usort("sortByIndex",1);
myData.dump();
myData.usort("sortByIndex",0);
myData.dump();
myData.usort("sortByLastLetter",0);
myData.dump();Like I said, I'll be back in a bit after checking that quick sort...

[krycek]

beetle, these are for my API which is being publically released next week at www.soapi.com :)

I have fixed the qsort! One BIG problem with it: this line...

tempArray.swap(i, lastlow++)

should be...

tempArray.swap(i, ++lastlow)

...but WHY??? :confused:

I spent an hour debugging that routine, and this is what the official JavaScript reference has to say:


JavaScript has both binary and unary operators. A binary operator requires two operands, one before the operator and one after the operator:

operand1 operator operand2
For example, 3+4 or x*y.

A unary operator requires a single operand, either before or after the operator:

operator operand
or

operand operator
For example, x++ or ++x.

In addition, JavaScript has one ternary operator, the conditional operator. A ternary operator requires three operands.


Now, it says nothing about there being a difference in performance whether you put the ++ on one side or the other... I have always put it on the right, like this: i++ but the qsort only works with the ++ on the left.

I do not know why! Try it out by all means :)

...and thanks for the help, beetle, I am going to look at your code now. Oh and by the way, here's my bubble sort function:


//----- Bubble Sort Array ----------------------------------------------------------------------------------------------
Array.prototype.bsort = function(order) {
var tempArray = this.copy()
for (var i = tempArray.length - 1; i > 0; i--) {
for (var j = 0; j < i; j++) {
if (tempArray.compare(j, j + 1)) {
tempArray.swap(j, j + 1)
}
}
}
return tempArray
}


...just so you can compare it with mine :)

::] krycek [::

[beetle]

I know the difference....using the increment operator (++) or decrement for that matter (--) AFTER the variable increments it after it's used. Before the variable increments it before it's used. Example...

var i = 0;
alert(i++); // alerts 0!
alert(i); // alerts 1

var i = 0;
alert(++i); // alerts 1
alert(i); // alerts 1

Note: the existing sort() method for arrays IS a bubble sort (methinks).

var myArray = ['b','a','d,'c'];
myArray.sort();
// myArray == a,b,c,d

The sort() obviously takes 1 argument, which is a function-pointer to a user-defined sort (exactly the method I used in the code above...)

[krycek]

...in that case, should I be using ++i for the quicksort loop, instead of i++? :confused:

I thought it was something like what you said, but the very helpful js reference did not cover it! :rolleyes:

::] krycek [::

[beetle]

Strange...just FYI, that i++/++i thing is common to ALL C-based scripting languages that I'm aware of (including C! wheehee!) ;)

[beetle]

hehe, consider this for loop for populating an array with the numbers 1-10

var myArray = new Array();
for (var i=0; i<10; myArray[i++] = i) {}

That's it! ;)

P.S. Make sure to read my edited notes about sort above...

[jkd]

My question is why are you implementing high-performance sorting routines in a low-performance language such as Javascript?

Since you can't have references to simple data-types in JS, you are copying every element you swap into memory, which means this is going to eat memory for breakfast (for relatively large arrays).

Since this will use large amounts of memory for large arrays, you may only sort small arrays. However, for smaller arrays, sorts such as Insertion or Selection will work faster than Quicksort or Mergesort.

Looking at your quicksort function, it seems kinda funky. A basic quicksort looks like (in pseudo-code):


quicksort(start, finish) {
if (start < finish) {
p = partition(start, finish)
quicksort(start, p-1)
quicksort(p+1, finish)
}
}


It seems you are doing something else... (which may result in the same, but I didn't look over your code carefully enough). All partition() does is return the pivot point.

[jkd]

Oh, and to quote my APCS teacher about Bubble Sort:

"Why do they teach bubble sort? Not only is it an O(n^2) algorithm, but it is the worst one!"

There is really no use at all to use a basic bubble sort when you have insertion and selection sorts available. However, odd-even bubble sorts in combination with a quicksort can be a little bit faster (quicksort large arrays, then odd-even bubble-sort sections of arrays smaller than X, where X is some optimization point (I think between 5 and 10).

[beetle]

Originally posted by jkd
My question is why are you implementing high-performance sorting routines in a low-performance language such as Javascript?I've been wondering that all along. It's interesteing nonetheless to see their implementation, but since krycek joined the board a few weeks ago, I've never seen anyone attempt to use javascript for such 'application-like' procedures.

[jkd]

A webpage if you want to visibly see how bad bubble sort is compared to any other sorting algorithm :D
(or if you want to see how fast Quicksort is relative to other algorithms, but remember Quicksort can be O(n^2) on an already sorted list as opposed to the average O(n log n))

http://www-cse.ucsd.edu/users/ricko/Java.Sort/example1.html

[jkd]

Originally posted by beetle
I've been wondering that all along. It's interesteing nonetheless to see their implementation, but since krycek joined the board a few weeks ago, I've never seen anyone attempt to use javascript for such 'application-like' procedures.

In my APCS class we've been doing all of this with C++. Javascript simply isn't capable of doing anything extremely fast. And when you *do* need some abstract data type implemented in a lower level language, you always have the objects found in Java via LiveConnect (at least in NS), such as BigDecimal for example.

[beetle]

Thanks for that link jkd, I had seen it before but couldn't remember where....

[krycek]

...lol :D

Quite a lot of discussion going on here :)

I dug up one of my old C++ references, and sure enough, ++i vs i++ is documented... they must have forgot to put it in the JS reference. I don't think I have ever had to use it the other way round before.

As for my sorts, yes in most cases bubble sort is the worst, but not in all. There are situations where an optimsed bubble sort can be quicker, such as when the array is already very nearly sorted. e.g. if you have an array with 500 items, and add 5, bubble sort would re-sort the array quicker than a quick sort.

It is precisely because of this that I am including a bubble sort in my array API, and also quick sort, merge sort, and radix sort (all done). I am going to do a couple more, probably insertion sort.

btw, jkd, in your pseudo-code example, you forgot to swap. Your code would essentially do nothing ;)

There may be a more efficient way of implementing quick sort in the function I did, however it is very basically a conversion of the pseudo-code into real code.

Now, as to the other reason why... because of my current work on compression algorithms, I am trying to optimise the two processor and memory heavy things: the search, and the sort. My current algorithm is an extension of the pre-defined token indexed encoding algorithm I posted a couple of days ago. This function creates an optimised token set, except it is currently unoptimised an hence processing time increases exponentially for each extra byte.

What I am doing is optimising the routine by using a combination of modified sorts, and a modified search function. The result, if my pseudo-code and calculations are correct, is a compression function that works in linear time and space and still acheives the same level of compression as I am currently getting. I cannot report an accurate level of compression yet because I have had to throttle back during testing, just to make it run in under 5 mins (processing a 160Kb string). However, when the multi-pass optimised code is done, it should turn out a string which is < 40% of the original, for strings of 10Kb and above.

Lastly, I have done all this sort of stuff in better languages (such as C, and VB) however remember I am currently making a JS API, and it needs to be as complete as possible, and also seeing as part of my technique for creating a proper application model in a browser involves a custom data object, built-in encryption and compression, and never having to reload the main page, I am forced to code these things in JS :)

So... there you go... your questions answered, your curiosity satisfied :)

oh, and thanks for the help, too :)

::] krycek [::

[krycek]

...oh and also, for the compression stuff, the compression of big stuff will be done server-side, in PHP, and any data sent from the browser will most likely be quite small.

::] krycek [::

[krycek]

hmmm, that page you linked to was very good, jkd... do you know where I can get the source for those algorithms from?

Oh and the reason they teach bubble sort, despite it being the worst in *most* cases, is that it is such a fundamentally important sorting algorithm.

::] krycek [::

[jkd]

Meh, my quicksort example was from the implementation I did in class, where I did the swapping inside partition():

int partitionQuick(apvector<int> & arr, int low, int high) {
if (high - low <= 10) {
// QuickSort is slower on smaller lists then Insertion Sort,
// so let's use Insertion Sort!
insertionSort(arr, low, high);
return -1;
}
else {
int first = arr[low];
while (low < high) {
while (arr[high] > first) high--;
while (arr[low] < first) low++;
if (low < high)
swap(arr[low], arr[high]);
}
return high;
}
}

void quickSort(apvector<int> & arr, int a, int b) {
if (a < b) {
int pivot = partitionQuick(arr, a, b);
if (pivot > -1) {
quickSort(arr, a, pivot - 1);
quickSort(arr, pivot + 1, b);
}
}
}

:D

As for Bubble Sort being a fundamental sorting technique, try telling that to my teacher. Bubble sort is only fast on already sorted lists, which kind of defeats the purpose of sorting it. Insertion or selection are always better O(n^2) techniques. However, you can make several improvements on bubble sort so that it doesn't suck entirely, such as the common odd-even variety.

[krycek]

...I'm sure you know what I mean :)

bubble sort is very important to learn, even if it is never useful.

I want to include it in my API just to make sure it is complete, you see ;)

also, I often use bubble sort when developing, so that I can step through things more easily and keep an eye on what is happening, which is not always as easy as when using another sorting technique. Then, when the rest of the code is correct, I replace the bubble sort with another sort, optimised for the type of data. :)

Thanks for the code, by the way :)

::] krycek [::