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.
Selection Sort Algorithm in Java
The selection sort algorithm is slightly better performing than bubble sort, and so we're going to explain how it works and implement it in Java.
On Wednesday, April 16th 2008 at 09:54 PM
By Louis Fernandez (View Profile)
(Rated 4.6 with 9 votes)
The selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N2) to O(N). Unfortunately, the number of comparisons remains O(N2). However, the selection sort can still offer a significant improvement for large records that must be physically moved around in memory, causing the swap time to be much more important than the comparison time. (Typically, this isn’t the case in Java, where references are moved around, not entire objects.)
Selection Sort on the Baseball Players
Let’s consider the baseball players again. In the selection sort, you can no longer compare only players standing next to each other. Thus, you’ll need to remember a certain player’s height; you can use a notebook to write it down. A magenta-colored towel will also come in handy.
A Brief Description
The next time you pass down the row of players, you start at position 1, and, finding the minimum, swap with position 1. This process continues until all the players are sorted.
A More Detailed Description
Swap this shortest player with the player on the left end of the line. You’ve now sorted one player. You’ve made N-1 comparisons, but only one swap.
On the next pass, you do exactly the same thing, except that you can completely ignore the player on the left because this player has already been sorted. Thus, the algorithm starts the second pass at position 1, instead of 0. With each succeeding pass, one more player is sorted and placed on the left, and one less player needs to be considered when finding the new minimum.
Java Code for Selection Sort
The listing for the selectSort.java program is similar to that for bubbleSort.java, except that the container class is called ArraySel instead of ArrayBub, and the bubbleSort() method has been replaced by selectSort(). Here’s how this method looks:
public void selectionSort()
The outer loop, with loop variable out, starts at the beginning of the array (index 0) and proceeds toward higher indices. The inner loop, with loop variable in, begins at out and likewise proceeds to the right.
At each new position of in, the elements a[in] and a[min] are compared. If a[in] is smaller, then min is given the value of in. At the end of the inner loop, min points to the minimum value, and the array elements pointed to by out and min are swapped.
The output from selectSort.java is identical to that from bubbleSort.java:
77 99 44 55 22 88 11 0 66 33
Efficiency of the Selection Sort
|Digg It! Del.icio.us Reddit StumbleIt Newsvine Furl BlinkList|
Rate this tutorial
Related Source Code
Java Job Search