Lecture
Selection sort – is perhaps the simplest sorting algorithm to implement. As with most other similar algorithms, it is based on a comparison operation. By comparing each element with every other and swapping them when necessary, the method brings the sequence into the required ordered form.
The idea of the algorithm is very simple. Let there be an array A of size N, then selection sort reduces to the following:
With each subsequent step, the size of the subarray the algorithm works with decreases by 1, but this does not affect the sorting method, which remains the same at every step.
Let us consider the algorithm's operation using a specific sequence of integers as an example. Given an array consisting of five integers 9, 1, 4, 7, 5 (see figure). It is required to arrange its elements in ascending order using selection sort. Let's start comparing the elements in order. The second element is smaller than the first – we remember this (key=2). Next we see that it is also smaller than all the rest, and since key≠1, we swap the first and second elements. Let us continue ordering the remaining part, trying to find a replacement for the element with value 9. Now key will be assigned 3, since the element with index 3 has the smallest value. As we can see, key≠2, therefore we swap the 2nd and 3rd elements. We continue placing elements in their positions until, at some step, the size of the subarray becomes equal to 1.
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include "stdafx.h"
#include using namespace std; int i, j; void SelectionSort(int A[], int n) //selection sort { int count, key; for (i=0; i{ count=A[i]; key=i; for (j=i+1; jif (A[j]if (key!=i) { A[i]=A[key]; A[key]=count; } } cout<<"Resulting array: "; for (i=0; i} //main function void main() { setlocale(LC_ALL, "Rus"); int n, A[1000]; cout<<"Number of elements > "; cin>>n; for (i=0; i{ cout< "; cin>>A[i]; } SelectionSort(A, n); system("pause>>void"); } |
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
program SelectSort;
uses crt; const max=1000; type arr=array[1..max] of integer; var i, j, n: integer; A: arr; procedure SelectionSort(A: arr; n: integer); {selection sort} var key, count: integer; begin for i:=1 to n do begin count:=A[i]; key:=i; for j:=i+1 to n do if (A[key]>A[j]) then key:=j; if (key<>i) then begin A[i]:=A[key]; A[key]:=count; end; end; write('Resulting array: '); for i:=1 to n do write(A[i], ' '); {output the array} end; {main block of the program} begin write('Number of elements > '); read(n); for i:=1 to n do {input the array} begin write(i,' element > '); read(A[i]); end; SelectionSort(A, n); readkey; end. |
Selection sort is easy to implement, and in some situations it is worth preferring it over more complex and sophisticated methods. But in most cases this algorithm is less efficient than the latter, since in the worst, best, and average case it requires O(n2) time
Comments