Windows Systems Administrator Jupitermedia US-CT-Darien Post A Job | Post A Resume

WebWeekly: Sorting Arrays

---

* This WebWeekly presents a Quicksort algorithm you can use to quickly sort your arrays in ASP.

For the past six months or so, I've been reading and participating in a number of ASP ListServ groups. One question which arises often is how to sort an array efficiently. There are *many* sorting algorithms available, each having its own advantages and disadvantages.

The simplest sort, a bubble sort, is good for small arrays, especially ones that are nearly sorted already. However, as the set of data to be sorted starts to grow, a bubble sort becomes quite inefficient. The sort that is regarded as the best sort for large arrays that are NOT nearly sorted is Quicksort.

Quicksort uses a divide and conquer approach, dividing the total array in half, then recursively dividing each half info halves, and those halves into halves and so on and so on. Eventually, it just has two values, and can swap them if needed. While this is not exactly how a Quicksort works, it is a general description. What to remember is that a Quicksort uses a divide and conquer approach utilizing recursion. This leads to a big O of N log N.

I implemented this Quicksort algorithm using JavaScript. Since you can use JScript as a server-side language with ASP, its cut & paste time. You can also, as this code shows, use your Quicksort algorithm with client-side scripting as well. If you would like to see this algorithm coded in VBScript, let me know, and if there is enough interest, I will go ahead and provide a link to a VBScript implementation in the next WebWeekly.

An implementation of Quicksort in VBScript using one dimensional arrays can be at this URL. A VBScript implementation using two dimensional arrays can be found at this URL.

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

If you have any questions regarding how or why Quicksort works, and why it is efficient, simply email me (mitchell@4guysfromrolla.com) with your question(s). Also, if a discussion on other sorts (such as bubble sort, selection sort, heap sort) is called for, please simply ask.

Happy Programming!

Related Articles

Quicksort for One Dimensional Arrays: VBScript Implementation

Quicksort for Two Dimensional Arrays: VBScript Implementation

Quicksort for One Dimensional Arrays: JavaScript Implementation

---

Sign up for WebWeekly!
WebWeekly is a weekly email publication which covers various ASP, SQL, JavaScript, and VBScript topics. This publication is geared toward the Intermediate to Advanced ASP programmer. If you'd like to receive WebWeekly, simply drop off your email address!

(WebWeekly is 100% free; email addresses are kept in strict confidence.)

Windows Internet Technology | ASP.NET [1.x] [2.0] | ASPMessageboard.com | ASPFAQs.com | Advertise | Feedback | Author an Article