Softpanorama

May the source be with you, but remember the KISS principle ;-)
Home Switchboard Unix Administration Red Hat TCP/IP Networks Neoliberalism Toxic Managers
(slightly skeptical) Educational society promoting "Back to basics" movement against IT overcomplexity and  bastardization of classic Unix

Selection Sort

News

Sorting Algorithms Recommended Books Recommended Links Insertion sort Bubblesort
Animations Sorting Algorithms Coding Style Donald Knuth Testing Sorting Algorithms Humor Etc

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:

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:

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.


Top Visited
Switchboard
Latest
Past week
Past month

NEWS CONTENTS

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:

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:

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

Google matched content

Softpanorama Recommended

Top articles

Sites



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 quotesSomerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose BierceBernard 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 DOSProgramming Languages History : PL/1 : Simula 67 : C : History of GCC developmentScripting 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-MonthHow 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


Copyright © 1996-2021 by Softpanorama Society. www.softpanorama.org was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP) without any remuneration. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.

FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.

This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...

You can use PayPal to to buy a cup of coffee for authors of this site

Disclaimer:

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