Selection sort, also called naive (selection) sort, is an in-place comparison sort. It may look pretty similar to insertion sort, but it performs worse. It is a quite simple sorting algorithm, and may perform better than more complicated algorithms in particular cases, for example in the ones where the auxiliary memory is limited.
How it works:
First it finds the smallest number in the array and exchanges it with the element from the first position, then it finds the second smallest number and exchanges it with the element from the second position, and so on until the entire list is sorted.
Step by step example :
Having the following list, let’s try to use selection sort to arrange the numbers from lowest to greatest:
6, 3, 5, 4, 9, 2, 7.
First run:
2, 3, 5, 4, 9, 6, 7 (2 was the smallest number and 6 which was the first element were swapped)
Second run:
2, 3, 4, 5, 9, 6, 7 (4 and 5 were swapped, as 3 was already on the good position, with no other element being smaller)
Third run:
2, 3, 4, 5, 6, 9, 7 (6 and 9 were swapped, 5 was already in the good position)
Forth run:
2, 3, 4, 5, 6, 7, 9 (7 and 9 were swapped)
Fifth run:
2, 3, 4, 5, 6, 7, 9 (no swap)
Sixth run:
2, 3, 4, 5, 6, 7, 9 (no swap)
Even though in the last two runs there were no swaps, the algorithm still makes passes, of a total of n-1 passes, where n is the number of elements.
Sample code:
#include < iostream >using namespace std;
int main()
{long int n=100;
long int a[100];
cout << "Please insert the number of elements to be sorted: ";
cin >> n; // The total number of elements
for(int i=0;i < n;i++)
{cout << "Input " << i << " element: ";
cin >> a[i]; // Adding the elements to the array
}cout << "Unsorted list:" << endl; // Displaying the unsorted array
for(int i=0;i < n;i++)
{cout << a[i] << " ";
}for (int i=n-1;i>1;--i)
{int locmax=0;
int maxtemp=a[0];
for (int j=1;j < =i;++j)
{if(a[j]>maxtemp)
{locmax=j;
maxtemp=a[j];
}}a[locmax]=a[i];
a[i]=maxtemp;
}cout << "Sorted list:" << endl; // Displaying the sorted array
for(int i=0;i < n;i++)
{cout << a[i] << " ";
}return 0;
}
Output:
Code explanation:
for (int i=n-1;i>1;--i)
{int locmax=0;
int maxtemp=a[0];
for (int j=1;j < =i;++j)
{if(a[j]>maxtemp)
{locmax=j;
maxtemp=a[j];
}}a[locmax]=a[i];
a[i]=maxtemp;
}
The algorithm executes n-1 iterations always, no matter if the correct order was achieved earlier or the array was already sorted.
The first element is retained in the maxtemp variable, then the next element is checked with maxtemp to see which is greater, and if this is true, maxtemp retains the next big value and so on. After this has been completed, on the last position, there will be the greatest element from the list, so the greatest element ends on the right position after the first run.
This code example of the algorithm sorts the array from greater to lower, as opposing to the step by step example that I gave earlier.
Complexity:
Clearly, the outer loop runs n-1 times. The only complexity in this analysis is the inner loop. If we think about a single time the inner loop runs, we can get a simple bound by noting that it can never loop more than n times. Since the outer loop will make the inner loop complete n times, the comparison can’t happen more than O(n2) times. Also, the same complexity applies to worst case or even best case scenario.
Advantages:
- easy to implement;
- requires no additional storage space.
- it performs well on a small list.
Disadvantages:
- poor efficiency when dealing with a huge list of items
- its performance is easily influenced by the initial ordering of the items before the sorting process.
Conclusion:
Selection sort is sorting algorithm known by its simplicity. Unfortunately, it lacks efficiency on huge lists of items, and also, it does not stop unless the number of iterations has been achieved (n-1, n is the number of elements) even though the list is already sorted.
