Visual Basic
Web Scripting
Active Server Page


Home


Articles

Links
Books

Mailing List
Receive free code snippets and notices when this site is updated.

Email

Feedback

 

Sorting Algorithms in Java

Over the next few weeks I will present a number of sorting algorithms implemented in Java.  The first of these is the Selection Sort.

  Time Growth Rate
Best Case
Time Growth Rate
Average Case
Time Growth Rate
Worst Case
Selection Sort N2 N2  N2 

Selection Sort

The selection sort is not a particular fast algorithm because the time it takes to sort a list is the square of the number of items in the list.  If there is 5 items to be sorted 25 major operations will be required to sort the list.  If there is 6 items to be sorted it will take 36 operations to sort the list.

Unlike some other algorithms the number of operations it takes to sort a list is the same if the list is totally out of order or already sorted.  Because the selection sort is so simple it may still be a good choice if the list to sort is small.  Because a selection sort performs a relatively low number of data swaps it can be a good choice when swapping data takes a long time and data comparisons don't.


The selection sort works by moving though a list and finding the largest non-sorted item and then swapping it with the last non-sorted item in the list.  After every pass at least one more item will be in correct order at the end of the list.

The figure to the right illustrates this.  

The largest item found in each search is in green.  The item it is swapped with is in blue.  The items that have already been sorted are Bold.

25 9 13 47 12 | Find largest Item
25 9 13 12 47 | Swap with item at end of array
25 9 13 12 47 | Find second largest item
12 9 13 25 47 | Swap with second to last item in array
12 9 13 25 47 | Find third largest item. item is
| already in
| order so don't swap
12 9 13 25 47 | Find fourth largest item.
9 12 13 25 47 | Swap with item fourth
| from the end

 

Below is an implementation of the Selection Sort algorithm.  L specifies were in the array to start sorting and R specifies what element to stop sorting at.

Each time the outer loop executes one more item will be in it's correct position at the end of the array.  The code that swaps the items executes even if the items are already in order.  This is usually faster than checking to see if the swap should be made each time.

public static void selectionSort(double arrayToSort[], int L, int R)
{
	int max, j;
	double temp;

	for(int i=R; i > L; i--)
	{
		max = 0;
		/* Find largest non-sorted item in array */
		for (j=L+1; j<=i; j++)
			if (arrayToSort[max] < arrayToSort[j] )
				max = j;
		/* Swap largest non-sorted item with item at the end of the array */
		temp = arrayToSort[i];
		arrayToSort[i] = arrayToSort[max];
		arrayToSort[max] = temp;
	}
}

Next week I will present an implementation of a Bubble Sort.