Lably
Skip to content

Selection sort

Sorting algorithm

  • 11 min read
  • 5 chapters

Related on Lably

Through Computer science, In-place algorithm and Big O notation

Lab · Class 10–11NLP PipelinesLab · Class 3–8Place Value & CarryingLab · Class 11Algorithm Visualizer

The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

The time efficiency of selection sort is quadratic, so there are a number of sorting techniques which have better time complexity than selection sort.

Example

Here is an example of this sort algorithm sorting five elements:

(Nothing appears changed on these last two lines because the last two numbers were already in order.)

Selection sort can also be used on list structures that make add and remove efficient, such as a linked list. In this case it is more common to remove the minimum element from the remainder of the list, and then insert it at the end of the values sorted so far. For example:

arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning <11> 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 <12> 25 22 64 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 <22> 25 64 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 <25> 64

Sign in to keep reading

4 more chapters are free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard