Selection Sort:
Selection sort is the most conceptually simple of all the sorting algorithms. It's inefficient on large lists, and generally performs worse than the similar insertion sort. It works by selecting the smallest (or largest, if you want to sort from big to small) element of the array and placing it at the head of the array. Then the process is repeated for the remainder of the array; the next largest element is selected and put into the next slot, and so on down the line.
Because a selection sort looks at progressively smaller parts of the array each time (as it knows to ignore the front of the array because it is already in order), a selection sort is slightly faster than bubble sort, and can be better than a modified bubble sort.
Here is an example of this sort algorithm sorting five elements:
31 25 12 22 11
11 25 12 22 31
11 12 25 22 31
11 12 22 25 31
And here is the code for a simple selection sort:
Insertion Sort:
Insertion sort is a simple sorting algorithm. It inserts each element of the array into its proper position, leaving progressively larger stretches of the array sorted. What this means in practice is that the sort iterates down an array, and the part of the array already covered is in order; then, the current element of the array is inserted into the proper position at the head of the array, and the rest of the elements are moved down, using the space just vacated by the element inserted as the final space.
It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:
Here's a simple implementation of insertion sort in C/C++:
Insertion Sort:
Insertion sort is a simple sorting algorithm. It inserts each element of the array into its proper position, leaving progressively larger stretches of the array sorted. What this means in practice is that the sort iterates down an array, and the part of the array already covered is in order; then, the current element of the array is inserted into the proper position at the head of the array, and the rest of the elements are moved down, using the space just vacated by the element inserted as the final space.
It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:
- Simple to implement
- Efficient on (quite) small data sets
- Efficient on data sets which are already substantially sorted
- More efficient in practice than most other simple algorithms such as selection sort or bubble sort.
- Stable (does not change the relative order of elements with equal keys)
- In-place (only requires a constant amount of extra memory space)
- It is an online algorithm, in that it can sort a list as it receives it
Here's a simple implementation of insertion sort in C/C++:
