Softpanorama (slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-)

Selection Sort

Selection sort is probably the simplest sorting algorithm to implement so it can be blazingly fast on short arrays. The idea is to find minimum of the array and swap it with the first element of the array. Then repeat the process with the rest of array, shrinking the unsorted part of array by one with each selection.

For student it is important to understand the flowchart and C-implementation. After that you can "objectify", javafy" or "Cpp-fy" or distort in other inventive ways the basic algorithm at your own pleasure ;-) The key ideas are simpler to understand in flowcharts and C or assembler.

Implementation consists of two loops:

• External loop index determines the boundary of the sorted area
• The inner loop is the classic algorithms of finding a minimum of the array.

The running time is dominated by the comparisons, as moves are performed only for elements for which we calculated the final placement.

This sorting algorithms is unable to make an advantage of the pre-existing sorting or sorted areas.  That means that the running time is almost independent of the initial ordering of elements and depends on the number of elements to sort. The fact that already sorted array will be sorted in the same time as any other diminish its usefulness for applications where we know definitely that input data came largely presorted with few permutations.

Here is the skeleton implementation in C. For notes on coding style see Sorting Algoritms Coding Style. Note that the outer loop iterates only to (n-1) while the inner loop (finding minimum) iterates till the end of array (n).

// a is an array of size n
for (i = 0; i < (n - 1); i++) {
    imin = i;
    amin=a[imin];
    for (j = (i + 1); j < n; j++) {
        if (a[j] < amin]) {
           imin = j; // new index of minimum
           amin=a[imin]; // new value of minimum
        } // if
    } // for j
   // swap operation: optimized as minimum is stored in variable amin
   if (imin==i) { continue; } // element is already in place
   a[imin]=a[i]; // overwrite sell with minimum, with the value of boundary cell
   a[i]=amin; // replace boundary cell with newly found minimum
} // for i

You can cut the number of passes in selection sort in half, if algorithm is modified to find both max and min on the same pass. This way you can grow the sorted area from both ends. This gives us a 50% improvement in speed, but somewhat complicates logic:

biinsertsort(int a[], int n) {
int lb = 0;
int ub = n-1;
int j, imin, imax, amin, amax, aub;

    while ( lb < ub ) {
        imin = lb; amin = a[imin];
        imax = ub; amax = a[imax];
        for (j = lb; j <= ub; j++) {
            if ( a[j] < amin ) { imin = j; amin = a[imin]; }
            else if ( a[j] > amax ) { imax = j; amax = a[imax]; }
        } // for j
// swap operations for minimum and maximum respectively
        aub=a[ub]; // can be damaged by minimum swap
        if ( imin != lb ) { a[imin] = a[lb]; a[lb] = amin; }
        if ( imax != ub ) { a[imax] = aub; a[ub] = amax; }
        lb++; ub--;
     } // while
} // biinsertsort

The other way to speed the sort is to use stack for all min values found during each pass and insert them one by one after the pass.  But in worst case (reversal sorted array) that will require an additional storage equal to the array to be sorted. You can limit the size of this stack, though.  For example to two elements or some other power of two, for example 16 (circular array implementation of stack should be used in the latter case to avoid overflow).

Recommended Links

Animator for selection sort Provided by - Peter Brummund through the Hope College Summer Research Program. Algorithms covered:

• Bubble Sort  -- incorrect implmentation
• Insertion Sort
• Merge Sort
• Quick Sort
• Selection Sort
• Shell Sort

Java Sorting Animation Page - Selection Sort Contains very nice anumation, that permits inputing your own data.

The selection sort algorithm is in many ways similar to the Simple Sort and Bubble Sort algorithms. Rather than swapping neighbors continously as the algorithm traverses the (sub)array to be sorted, as done in the Bubble Sort case, this algorithm finds the MINIMUM element of the (sub)array and swaps it with the pivot (or "anchor") element. The code for the algorithm is as follows:

	// List is an array of size == n
	for (i = 0; i < (n - 1); i++) {
	  imin = i;
	  for (j = (i + 1); j < n; j++) {
	      if (a[j] <= a[imin]) {
		imin = j;
                      } // if
                  } // for j
	  swap(a[i], a[imin]);
	} // for i 

Selection Sort

void selectionSort(int numbers[], int array_size)
{
  int i, j;
  int min, temp;

  for (i = 0; i < array_size-1; i++)
  {
    min = i;
    for (j = i+1; j < array_size; j++)
    {
      if (numbers[j] < numbers[min])
        min = j;
    }
    temp = numbers[i];
    numbers[i] = numbers[min];
    numbers[min] = temp;
  }
}

NIST Selection sort

Definition: A sort algorithm that repeatedly looks through remaining items to find the least one and moves it to its final location. The run time is Θ(n²), where n is the number of comparisons. The number of swaps is O(n).

Generalization (I am a kind of ...)
in-place sort.

Specialization (... is a kind of me.)
bingo sort.

See also strand sort, heapsort, Fisher-Yates shuffle.

Selection Sort

The idea of selection sort is rather simple: we repeatedly find the next largest (or smallest) element in the array and move it to its final position in the sorted array. Assume that we wish to sort the array in increasing order, i.e. the smallest element at the beginning of the array and the largest element at the end. We begin by selecting the largest element and moving it to the highest index position. We can do this by swapping the element at the highest index and the largest element. We then reduce the effective size of the array by one element and repeat the process on the smaller (sub)array. The process stops when the effective size of the array becomes 1 (an array of 1 element is already sorted).

For example, consider the following array, shown with array elements in sequence separated by commas:

The leftmost element is at index zero, and the rightmost element is at the highest array index, in our case, 4 (the effective size of our array is 5). The largest element in this effective array (index 0-4) is at index 2. We have shown the largest element and the one at the highest index in bold. We then swap the element at index 2 with that at index 4. The result is:

We reduce the effective size of the array to 4, making the highest index in the effective array now 3. The largest element in this effective array (index 0-3) is at index 1, so we swap elements at index 1 and 3 (in bold):

The next two steps give us:

The last effective array has only one element and needs no sorting. The entire array is now sorted. The algorithm for an array, x, with lim elements is easy to write down:

for (eff_size = lim; eff_size > 1; eff_size--)
          find maxpos, the location of the largest element in the effective
               array: index 0 to eff_size - 1
          swap elements of x at index maxpos and index eff_size - 1

The implementation of the selection sort algorithm in C, together with a driver program is shown in Figure 10.6.

Sample Session:

• Original array:
• 63 75 90 12 27
• Sorted array:
• 12 27 63 75 90

The driver prints the array, calls selection_sort() to sort the array, and prints the sorted array. The code for selection_sort() follows the algorithm exactly; it calls get_maxpos() to get the index of the largest element in an array of a specified size. Once maxpos is found, the element at that index is swapped with the element at index eff_size-1, using the temporary variable, tmp.

We may be concerned about the efficiency of our algorithm and its implementation as a program. The efficiency of an algorithm depends on the number of major computations involved in performing the algorithm. The efficiency of the program depends on that of the algorithm and the efficiency of the code implementing the algorithm. Notice we included the code for swapping array elements within the loop in selection_sort rather than calling a function to perform this operation. A function call requires added processing time in order to store argument values, transfer program control, and retrieve the returned value. When a function call is in a loop that may be executed many times, the extra processing time may become significant. Thus, if the array to be sorted is quite large, we can improve program efficiency by eliminating a function call to swap data elements. Similarly, we may include the code for get_maxpos() in selection_sort():

 

void selection_sort(int x[], int lim)
{    int i, eff_size, maxpos, tmp;

for (eff_size = lim; eff_size > 1; eff_size--) { for (i = 0; i < eff_size; i++) maxpos = x[i] > x[maxpos] ? i : maxpos; tmp = x[maxpos]; x[maxpos] = x[eff_size - 1]; x[eff_size - 1] = tmp; } }

Last modified: February 28, 2008