Selection Sort

Selection sort is probably the simplest sorting algorithm to implement so it can be blazingly fast on short arrays. It is  one of two most efficient algorithms for small sets (say up to 20) if array is close to random. The only better one for small sets is the insertion sort. It is the worst possible sort method for large already sorted arrays or arrays with just one permutation.

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 a 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 much simpler to understand in flowcharts and C or assembler (and that's why I really hate Data Structures and Algorithms book from object-oriented jerks -- they don't understand this or, worse, pretend that they don't understand ;-). Implementation consists of two nested 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.

The key deficiency of this sorting algorithm  that it is unable to make the 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 just on the number of elements to sort. So if the array is already sorted the algorithm will perform all the operations on it anyway. This fact diminishes (or eliminates) its usefulness for applications where we definitely know that input data came largely presorted with just few permutations.

This algorithm has good locality properties and is able to utilize cache effectively.  It is not a stable sorting algorithm.

Here is the skeleton implementation in C. For notes on coding style see Sorting Algorithms Coding Style. Note that the outer loop iterates only to (n-1) while the inner loop (finding minimum) iterates from the first element of the unsorted area 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; } // the element is already in right place
   a[imin]=a[i]; // overwrite the position of found minimum
                   //with the top cell of the unsorted area
   a[i]=amin; // replace the top cell of the unsorted area
               //with newly found minimum
   // now repeat the same process for an unsorted area an element less.
} // for i

There are three typical errors in C or C++ implementations on the net:

• Incorrect boundaries for outer and inner loops (outlook should run from 1 to n-1, while inner loop should run from j to n.)
• No check if swap is necessary at all
• Usage of full swap instead of "half-swap" (you always has the element in the variable amin so it is unnecessary to copy it to an additional temp variable for swapping)

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 is a is not very promising idea, as it does not cut substantially the number of comparisons (only the number of passes), but complicates logic way too much:

The other way to speed the sort is to use stack for all min values and their indexes found during each pass and insert them one by one after the pass. Note that the last element that we dropped before selecting the minimum is the second smallest element in the array. And so on. but the problem is that you need to keep track of what you exchanges or you can do it twice.  So the only way to do it properly is to have the second array equal in size to original and move elements to it. But there are much better algorithms if you can allow to double the required space.  Also in worst case (reverse sorted array) full stack requires 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 fixed power of two (for example 16) or estimated based on the size of the array (circular array implementation of stack should be used in the latter case to avoid overflow).  In any case here return on increasing complexity is negative. In other words the game is not worth the candles.

Note:

If you main platform is Linux and you write you programs in gcc to speed debugging you can do the following trick. Write the program in Perl first and use Perl debugger to debug it.

After that remove all $ from variable names and replace "#" with "//" to convert commentaries and you have (mostly) correct C algorithm. Couple of runs with gcc and gdb and you are done.

NEWS CONTENTS

• 20090410 : Selection Sort - C++, Java, Algorithm and Data Structure Tutorials by Denis Kulagin ( Selection Sort - C++, Java, Algorithm and Data Structure Tutorials, Apr 10, 2009 )
• 20090410 : Animator for selection sort ( Animator for selection sort, )
• 20090410 : Java Sorting Animation Page - Selection Sort ( Java Sorting Animation Page - Selection Sort, )
• 20090410 : Selection Sort ( Selection Sort, )
• 20090410 : NIST Selection sort ( NIST Selection sort, )
• 20090410 : Selection Sort ( Selection Sort, )

Old News ;-)

[Apr 10, 2009] Selection Sort - C++, Java, Algorithm and Data Structure Tutorials by Denis Kulagin

Contains Java and C++ implementation... Implementation does not take into account "half-swap" possibility. Otherwise it looks good. It does check if swap is necessary at all.

Visualizers

1. Selection Sort Animation (with source code line by line visualization)
2. Selection Sort in Java Applets Centre
3. Animated Sorting Algorithms: Selection Sort

Animator for selection sort

Provided by - Peter Brummund through the Hope College Summer Research Program.

Algorithms covered:

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

Java Sorting Animation Page - Selection Sort

Contains very nice animation, that permits inputting 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; } } 

	 

Recommended Links

Softpanorama Recommended

Top articles

Sites

• Selection sort - Wikipedia, the free encyclopedia (implementation uses the function swap which is the wrong idea -- it makes "half swap" with already going minimum into full swap of two elements. )
• Selection Sort - Kent State University, A Top Ohio University
• Selection Sort -- from Wolfram MathWorld

Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes :  Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce :  Bernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS :  Programming Languages History : PL/1 : Simula 67 : C : History of GCC development :  Scripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month :  How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March 12, 2019