Course navigation & on this page
Selection sort
Repeatedly select the smallest item remaining in the unsorted suffix.
Overview
Repeatedly select the smallest item remaining in the unsorted suffix. The suffix is scanned even on sorted input, giving n(n−1)/2 comparisons. Only Θ(n) exchanges are needed.
Step-by-step walkthrough
- Choose the next output position i.
- Scan the suffix to find the minimum.
- Exchange the minimum with position i.
- Repeat for the remaining suffix.
Complexity analysis
| Best case | Θ(n²) |
|---|---|
| Average / aggregate | Θ(n²) |
| Worst case | Θ(n²) |
| Space | Θ(1) auxiliary |
The suffix is scanned even on sorted input, giving n(n−1)/2 comparisons. Only Θ(n) exchanges are needed.
A worked example
[5,3,8,1] → [1,3,8,5] → [1,3,8,5] → [1,3,5,8].
Common mistake / implementation note
The standard exchange-based version is not stable: equal keys may change relative order.
The standard exchange-based version is not stable: equal keys may change relative order.
Original course code
Source: algs4/Selection.java. Original logic, comments, variable names and attribution are retained.
Download Selection.javaSelection.javaJAVA
/****************************************************************************** * Compilation: javac Selection.java * Execution: java Selection < input.txt * Dependencies: StdOut.java StdIn.java * Data files: https://algs4.cs.princeton.edu/21elementary/tiny.txt * https://algs4.cs.princeton.edu/21elementary/words3.txt * * Sorts a sequence of strings from standard input using selection sort. * * % more tiny.txt * S O R T E X A M P L E * * % java Selection < tiny.txt * A E E L M O P R S T X [ one string per line ] * * % more words3.txt * bed bug dad yes zoo ... all bad yet * * % java Selection < words3.txt * all bad bed bug dad ... yes yet zoo [ one string per line ] * ******************************************************************************/ package edu.princeton.cs.algs4; import java.util.Comparator; /** * The {@code Selection} class provides static methods for sorting an * array using <em>selection sort</em>. * This implementation makes ~ ½ <em>n</em><sup>2</sup> compares to sort * any array of length <em>n</em>, so it is not suitable for sorting large arrays. * It performs exactly <em>n</em> exchanges. * <p> * This sorting algorithm is not stable. It uses Θ(1) extra memory * (not including the input array). * <p> * For additional documentation, see * <a href="https://algs4.cs.princeton.edu/21elementary">Section 2.1</a> * of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */public class Selection { // This class should not be instantiated. private Selection() { } /** * Rearranges the array in ascending order, using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { int n = a.length; for (int i = 0; i < n; i++) { int min = i; for (int j = i+1; j < n; j++) { if (less(a[j], a[min])) min = j; } exch(a, i, min); assert isSorted(a, 0, i); } assert isSorted(a); } /** * Rearranges the array in ascending order, using a comparator. * @param a the array * @param comparator the comparator specifying the order */ public static void sort(Object[] a, Comparator comparator) { int n = a.length; for (int i = 0; i < n; i++) { int min = i; for (int j = i+1; j < n; j++) { if (less(comparator, a[j], a[min])) min = j; } exch(a, i, min); assert isSorted(a, comparator, 0, i); } assert isSorted(a, comparator); } /*************************************************************************** * Helper sorting functions. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } // is v < w ? private static boolean less(Comparator comparator, Object v, Object w) { return comparator.compare(v, w) < 0; } // exchange a[i] and a[j] private static void exch(Object[] a, int i, int j) { Object swap = a[i]; a[i] = a[j]; a[j] = swap; } /*************************************************************************** * Check if array is sorted - useful for debugging. ***************************************************************************/ // is the array a[] sorted? private static boolean isSorted(Comparable[] a) { return isSorted(a, 0, a.length - 1); } // is the array sorted from a[lo] to a[hi] private static boolean isSorted(Comparable[] a, int lo, int hi) { for (int i = lo + 1; i <= hi; i++) if (less(a[i], a[i-1])) return false; return true; } // is the array a[] sorted? private static boolean isSorted(Object[] a, Comparator comparator) { return isSorted(a, comparator, 0, a.length - 1); } // is the array sorted from a[lo] to a[hi] private static boolean isSorted(Object[] a, Comparator comparator, int lo, int hi) { for (int i = lo + 1; i <= hi; i++) if (less(comparator, a[i], a[i-1])) return false; return true; } // print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } } /** * Reads in a sequence of strings from standard input; selection sorts them; * and prints them to standard output in ascending order. * * @param args the command-line arguments */ public static void main(String[] args) { String[] a = StdIn.readAllStrings(); Selection.sort(a); show(a); }} /****************************************************************************** * Copyright 2002-2020, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/