Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Page 1 of 2 12 LastLast
Results 1 to 15 of 19
  1. #1
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Exclamation Quick sort function not working...

    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...

    Code:
    	//----- 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:

    Code:
    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 [::
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."

  • #2
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ...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.

    Code:
    	//----- 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 [::
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."

  • #3
    Senior Coder
    Join Date
    Aug 2002
    Posts
    3,467
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.
    Code:
    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...
    My Site | fValidate | My Brainbench | MSDN | Gecko | xBrowser DOM | PHP | Ars | PVP
    “Minds are like parachutes. They don't work unless they are open”
    “Maturity is simply knowing when to not be immature”

  • #4
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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???

    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:

    Code:
    	//----- 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 [::
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."

  • #5
    Senior Coder
    Join Date
    Aug 2002
    Posts
    3,467
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...)
    Last edited by beetle; 11-20-2002 at 05:06 PM.
    My Site | fValidate | My Brainbench | MSDN | Gecko | xBrowser DOM | PHP | Ars | PVP
    “Minds are like parachutes. They don't work unless they are open”
    “Maturity is simply knowing when to not be immature”

  • #6
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ...in that case, should I be using ++i for the quicksort loop, instead of i++?

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

    ::] krycek [::
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."

  • #7
    Senior Coder
    Join Date
    Aug 2002
    Posts
    3,467
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Strange...just FYI, that i++/++i thing is common to ALL C-based scripting languages that I'm aware of (including C! wheehee!)
    My Site | fValidate | My Brainbench | MSDN | Gecko | xBrowser DOM | PHP | Ars | PVP
    “Minds are like parachutes. They don't work unless they are open”
    “Maturity is simply knowing when to not be immature”

  • #8
    Senior Coder
    Join Date
    Aug 2002
    Posts
    3,467
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...
    My Site | fValidate | My Brainbench | MSDN | Gecko | xBrowser DOM | PHP | Ars | PVP
    “Minds are like parachutes. They don't work unless they are open”
    “Maturity is simply knowing when to not be immature”

  • #9
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    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):

    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.

  • #10
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    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).

  • #11
    Senior Coder
    Join Date
    Aug 2002
    Posts
    3,467
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.
    My Site | fValidate | My Brainbench | MSDN | Gecko | xBrowser DOM | PHP | Ars | PVP
    “Minds are like parachutes. They don't work unless they are open”
    “Maturity is simply knowing when to not be immature”

  • #12
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    A webpage if you want to visibly see how bad bubble sort is compared to any other sorting algorithm
    (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/.../example1.html

  • #13
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    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.

  • #14
    Senior Coder
    Join Date
    Aug 2002
    Posts
    3,467
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks for that link jkd, I had seen it before but couldn't remember where....
    My Site | fValidate | My Brainbench | MSDN | Gecko | xBrowser DOM | PHP | Ars | PVP
    “Minds are like parachutes. They don't work unless they are open”
    “Maturity is simply knowing when to not be immature”

  • #15
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ...lol

    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 [::
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."


  •  
    Page 1 of 2 12 LastLast

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •