A step by step tutorial teaching you how to create your own chat client and chat server easily in C#, for local networks or the Internet.
A C# tutorial showing you how to make use of WMI to extract information on disk drives, such as model, capacity, sectors and serial number.
This tutorial will teach you how to calculate the shipping cost based on the weight, height, length and depth of the box, the distance and the UPS service type.
Quicksort in Java
A quick intro to the Quicksort algorithm in Java, showing an efficient (if not optimal) way to sort.
On Monday, July 7th 2008 at 07:28 PM
By Jesse Bonzo (View Profile)
(Rated 4.3 with 18 votes)
In my opinion, Quicksort is the best algorithm for sorting, when it is implemented correctly. It is the default sorting algorithm in Java itself. Of course, writing it in Java is probably not the best, but it is important to know how it works in case you need to write some variation of it for some other purpose.
This code is a little tricky to understand at first, but go through it slowly. First, we swap the pivot with the last element in the segment of the array being partitioned. Second, we set the marker index to be the front of the segment. Then the array is scanned, checking each element to see if it is less than or equal to the pivot item. If it is, the it is swapped to the front, which is where index points to and index is incremented. At the end of all that, index points to where the pivot should be replaced. If no elements were found to be less than the pivot, then the pivot should be the first element, and like wise, if all the elements were found to be less than the pivot, the pivot should be the last element. The pivot's index is returned so that it can be used in the recursive sort step. Also, the pivot is now in it's final place and does not need to be moved anymore.
This is the actual sorting function that is called recursively. See that since the newPivotIndex points to where the pivot was, and it needs to stay there, the function is only called on the segments from lo to newPivotIndex-1 and newPivotIndex+1 to hi.
It's selection sort! That's no good, we want to beat the O(n^2) time complexity of selection sort. Granted, this problem only occurs if the array is sorted or close to sorted, but that can happen pretty often. There are some complicated way of picking a better pivot, but I'll just use a random number to prevent the lowest number from being picked every time.
With a random number, there is no guarantee that it still won't "go quadratic", but the chances are greatly reduced since the expected value of the random number is the average of hi and lo, and the expected value of the number at that index in an already (or close to) sorted array is the average of that array. If the average value of the array is picked as the pivot, then about half of the array is passed into each recursive call. If half of the array is passed into each call then the time complexity of the algorithm becomes O(nlogn) since the partition portion takes O(n) time and half of the array is recursed on with O(logn) time, which is much better for large values of n. So putting it all together...
|Digg It! Del.icio.us Reddit StumbleIt Newsvine Furl BlinkList|
Rate this tutorial
Related Source Code
There is no related source code.
Java Job Search