Sorting Algorithm for Javascript 1

mooster2 · Jul 29, 2004

I have this following algorithm to alphabetically list the items inside a "Select" object. The select has 50 items. This algorithm takes like 5-10 second to complete on a 300 Mhz computer and around 2-3 seconds on a 900 Mhz computer. It's still a very inefficient code when taking into account that i'm only sorting 50 items alphabetically.

So, my question is, can you guys propose me a more efficient sorting algorithm than the one i'm using below?

(I believe i'm using bubblesort

) There's got to be an algorithm that will sort faster and waste less CPU.

Thanks in advance

Code:

function sortItems()
{
  document.status.info2.value = "Sorting... please wait.";
  document.status.inventory.selectedIndex = 0;
  var tempitem = "";
  for (var i = 49; i >= 0; i--) {

    for ( var j = 49; j >= i; j-- ) {
       if ( status.inventory.options[i].text > status.inventory.options[j].text && status.inventory.options[j].text != "" )
       {
		tempitem = status.inventory.options[i].text;
		status.inventory.options[i].text = status.inventory.options[j].text;
		status.inventory.options[j].text = tempitem;
       }
       if ( status.inventory.options[i].text == "" ) 
       {
		status.inventory.options[i].text = status.inventory.options[j].text;
		status.inventory.options[j].text = "";
       }
    }
  }

  document.status.info2.value = "Inventory sorted";
}

kaht · Jul 29, 2004

I googled for a quicksort algorithm and this is the first site I got:

http://www.4guysfromrolla.com/webtech/012799-1.shtml

Quicksort is generally one of the quicker sorting algorithms.

and here's the code:

Code:

<SCRIPT LANGUAGE="JavaScript">
	function Quicksort(vec, loBound, hiBound)
	/**************************************************************
		This function adapted from the algorithm given in:
			Data Abstractions & Structures Using C++, by
			Mark Headington and David Riley, pg. 586.

		Quicksort is the fastest array sorting routine for
		unordered arrays.  Its big O is n log n.
	 **************************************************************/
	{

		var pivot, loSwap, hiSwap, temp;

		// Two items to sort
		if (hiBound - loBound == 1)
		{
			if (vec[loBound] > vec[hiBound])
			{
				temp = vec[loBound];
				vec[loBound] = vec[hiBound];
				vec[hiBound] = temp;
			}
			return;
		}

		// Three or more items to sort
		pivot = vec[parseInt((loBound + hiBound) / 2)];
		vec[parseInt((loBound + hiBound) / 2)] = vec[loBound];
		vec[loBound] = pivot;
		loSwap = loBound + 1;
		hiSwap = hiBound;

		do {
			// Find the right loSwap
			while (loSwap <= hiSwap && vec[loSwap] <= pivot)
				loSwap++;

			// Find the right hiSwap
			while (vec[hiSwap] > pivot)
				hiSwap--;

			// Swap values if loSwap is less than hiSwap
			if (loSwap < hiSwap)
			{
				temp = vec[loSwap];
				vec[loSwap] = vec[hiSwap];
				vec[hiSwap] = temp;
			}
		} while (loSwap < hiSwap);

		vec[loBound] = vec[hiSwap];
		vec[hiSwap] = pivot;


		// Recursively call function...  the beauty of quicksort

		// 2 or more items in first section		
		if (loBound < hiSwap - 1)
			Quicksort(vec, loBound, hiSwap - 1);


		// 2 or more items in second section
		if (hiSwap + 1 < hiBound)
			Quicksort(vec, hiSwap + 1, hiBound);
	}


	function PrintArray(vec,lo,hi)
	/**************************************************************
		Simply print out an array from the lo bound to the
		hi bound.
	 **************************************************************/
	{
		var i;
		for (i = lo; i <= hi; i++)
			document.write(vec[i] + "<BR>");
	}


	// Create an array and stuff some values in it
	var x = new Array(10);
	x[0] = 10;
	x[1] = 1;
	x[2] = 3;
	x[3] = 8;
	x[4] = 2;
	x[5] = 11;
	x[6] = 4;
	x[7] = 22;
	x[8] = 12;
	x[9] = 6;

	document.write("Here is a jumbled array:<BR>");
	PrintArray(x,0,9);

	Quicksort(x,0,9);	// Sort the array using quicksort

	document.write("<BR>Now the array is sorted!<BR>");
	PrintArray(x,0,9);
</SCRIPT>

-kaht

jemminger · Jul 29, 2004

how about javascript's built-in array sort function?

Code:

<html>
  <head>
    <title>test</title>
    <script type="text/javascript">
      function dosort(o) {
        var opts = o.options;
        var ar = [];
        
        //  build a real array from options
        for (var x = 0; x < opts.length; x++) {
          ar.push([opts[x].text, opts[x]]);
        }
        //  sort them
        ar.sort();
        
        //  delete existing options
        o.options.length = 0;
        //  rebuild options
        for (var x = 0; x < ar.length; x++) {
          o.options[x] = ar[x][1];
        }
      }
    </script>
  </head>

  <body>
    <form>
      <select name="foo">
        <option value="5">adff</option>
        <option value="16">do</option>
        <option value="6">aeiou</option>
        <option value="8">bar</option>
        <option value="10">blah</option>
        <option value="12">cam</option>
        <option value="20">eat</option>
        <option value="13">car</option>
        <option value="15">dim</option>
        <option value="29">iou</option>
        <option value="23">foo</option>
        <option value="17">drive</option>
        <option value="18">e</option>
        <option value="19">ea</option>
        <option value="4">abcd</option>
        <option value="26">go</option>
        <option value="45">when</option>
        <option value="21">ei</option>
        <option value="9">bark</option>
        <option value="47">which</option>
        <option value="14">cat</option>
        <option value="2">aab</option>
        <option value="22">excel</option>
        <option value="52">yard</option>
        <option value="24">fool</option>
        <option value="3">aabc</option>
        <option value="25">froo</option>
        <option value="43">var</option>
        <option value="55">yum</option>
        <option value="50">word</option>
        <option value="1">a</option>
        <option value="33">sea</option>
        <option value="31">object</option>
        <option value="49">woo</option>
        <option value="27">if</option>
        <option value="11">boo</option>
        <option value="28">in</option>
        <option value="46">where</option>
        <option value="36">slick</option>
        <option value="30">not</option>
        <option value="32">ram</option>
        <option value="7">asdf</option>
        <option value="34">see</option>
        <option value="54">you</option>
        <option value="35">seem</option>
        <option value="40">this</option>
        <option value="37">steel</option>
        <option value="38">that</option>
        <option value="42">until</option>
        <option value="39">then</option>
        <option value="41">to</option>
        <option value="44">what</option>
        <option value="48">while</option>
        <option value="51">work</option>
        <option value="53">yet</option>
      </select>
      <input type="button" value="dosort()" onclick="dosort(this.form.foo)" />
      <input type="button" value="value" onclick="alert(this.form.foo[this.form.foo.selectedIndex].value);" />
    </form>
  </body>
</html>

=========================================================
-jeff

http://www.jeffemminger.com

try { succeed(); } catch(E) { tryAgain(); } finally { rtfm(); }

vladibo · Aug 24, 2005

Code:

	// arguments:
	// arr - array to sort
	// func - function to retrieve the order numeric value from the array element
	function LuTree_QuickSort(arr,func){
		var iLen = arr.length;
		if(iLen == 0) return arr;
		var iStartIndex = 0;		
		while((iStartIndex + 1) < iLen){
			var iPivot = func(arr[iStartIndex]);
			var isFound = false;
			for(var i=iStartIndex+1;i<iLen;i++){
				var num = func(arr[i])
			
				if(num < iPivot){
					var temp = arr[iStartIndex];
					arr[iStartIndex] = arr[i];
					arr[i] = temp;
					isFound = true;
					break;
				}
			}
			if(!isFound){
				iStartIndex += 1;
			}	
		}
		return arr;
	}

vladibo · Aug 24, 2005

Code:

    function QuickSort(arr,func){
        var iLen = arr.length;
        if(iLen == 0) return arr;
        var iStartIndex = 0;        
        while((iStartIndex + 1) < iLen){
            var iPivot = func(arr[iStartIndex]);
            var isFound = false;
            for(var i=iStartIndex+1;i<iLen;i++){
                var num = func(arr[i])
            
                if(num < iPivot){
                    var temp = arr[iStartIndex];
                    arr[iStartIndex] = arr[i];
                    arr[i] = temp;
                    isFound = true;
                    break;
                }
            }
            if(!isFound){
                iStartIndex += 1;
            }    
        }
        return arr;
    }


var arr = ["A","F","C","B","E","D"];

alert( QuickSort(arr,new Function("x","return x;")) );

trollacious · Aug 24, 2005

I agree with jemminger about using the built-in sort. Anything you write will be interpreted by the script engine, where the built-in function is machine language, and probably quite a bit faster because of that.

Lee

BillyRayPreachersSon · Aug 25, 2005

You can even pass your own functions into default sort method to determine how it sorts... so you don't have to put up with a single sort method.

Stick with it, unless you have some really strange requirements that simply cannot be met with the default method.

Dan

[tt]Dan's Page [blue]@[/blue] Code Couch

http://www.codecouch.com/dan/

[/tt]

Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Sorting Algorithm for Javascript 1

mooster2

Programmer

kaht

Programmer

jemminger

Programmer

vladibo

Programmer

vladibo

Programmer

trollacious

Programmer

BillyRayPreachersSon

Programmer

Similar threads

Part and Inventory Search

Sponsor