Dan's coding practice area

<< Recent postings

Description: Code that sorts a list of floating point numbers using a selection sort.

A selection sort is probably one of the most intuitive & easy to understand sorting algorithms. The algorithm operates by iterating over a list and finding during the i-th iteration the smallest value in the list that has an index (think position in the list) greater than or equal to i. The value that is found is swapped with the value in the i-th position in the list. Accordingly, after the 1^st iteration, the smallest value in the list will be in the first position in the list. And, after the second, the second smallest value in list will be in the second position. This continues until the list is completely sorted.

During each iteration, the i-th smallest value is found by iterating over all of the currently unsorted values and finding the minimum value. As such, the algorithm effectively has both an inner and and outer loop. The outer loop is executed N times, where N is the number of items in the list. For each iteration of the outer loop, the inner loop executes N-i times. Thus, for a list of n items, the total number of iterations preformed by the algorithm will ben(n+1)/2, or rather of order n². This means that, in big-O notation, the algorithm has a time complexity of O(n²).

Languages: C, C++, Java, Perl, Python, Ruby, Octave(/Matlab like), Scheme, and Bourne shell.

Source files:
SelectionSort.c [raw code], SelectionSort.cc [raw code], SelectionSort.java [raw code], SelectionSort.pl [raw code], SelectionSort.py [raw code], SelectionSort.rb [raw code], SelectionSort.m [raw code], SelectionSort.scm [raw code], SelectionSort.sh [raw code],