Selection Sort
Selection Sort
Time Complexity: O(n^2).
Concept: Repeatedly finds the minimum element from the unsorted portion of the array and swaps it with the first unsorted element.
Steps:
- Find the minimum element in the unsorted part of the array.
- Swap it with the first element of the unsorted part.
- Repeat steps 1 and 2 until the entire array is sorted.
Selection sort uses ~n2/2 compares and n exchanges to sort an array of length n.
Selection sort: One of the simplest sorting algorithms works as follows:
First, find the smallest item in the array, and exchange it with the first entry. Then, find the next smallest item and exchange it with the second entry. Continue in this way until the entire array is sorted. This method is called selection sort because it works by repeatedly selecting the smallest remaining item.
Animation of selection sort in action:
In each step, the smallest element in the unsorted section is highlighted. That element is swapped with the first element in the unsorted section.
S E L E |C| T I O N S O R T
--|
C | |E| L E S T I O N S O R T
-----|
C E | L |E| S T I O N S O R T
-----|
C E E |L S T |I| O N S O R T
----|
C E E I | S T |L| O N S O R T
----|
C E E I L | T S O |N| S O R T
-----|
C E E I S N | S |O| T S O R T
----|
C E E I S N O | S T S |O| R T
----|
C E E I S N O O | T S S |R| T
----|
C E E I S N O O R ||S| S T T
----|
C E E I S N O O R S ||S| T T
----|
C E E I S N O O R S S ||T| T
----|
C E E I S N O O R S S T ||T|
----|
C E E I S N O O R S S T T |