
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 
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 Cimplementation. After that you can "objectify", javafy" or "Cppfy" 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 objectoriented 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 preexisting 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 (n1) 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.
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.

Switchboard  
Latest  
Past week  
Past month 
Visualizers
Algorithms covered:
 Bubble Sort  incorrect implementation
 Insertion Sort
 Merge Sort
 Quick Sort
 Selection Sort
 Shell Sort
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
void selectionSort(int numbers[], int array_size) { int i, j; int min, temp; for (i = 0; i < array_size1; 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; } }
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 ...)
inplace sort.Specialization (... is a kind of me.)
bingo sort.See also strand sort, heapsort, FisherYates shuffle.
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 04) 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 03) 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  1The 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_size1, 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; } }
Google matched content 
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 ITrelated 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) ObjectOriented 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 (19502000): 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 19872006 : 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 ManMonth : 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 Editorrelated Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPLrelated 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 : Perlrelated 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 : Assemblerrelated 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 © 19962021 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