Selection sort

Selection sort is a very simple sorting technique. In this sorting, the smallest element of the array is selected first, and that element is replaced with the first element of the array. After that, the second small element is selected and replaced with the second element of the array. This process continues until the entire array is sorted.

In this sorting technique, the array is divided into two parts. The first part is the sorted portion, which is written on the left side in the array. The second part is the unsorted portion, which is written on the right side in the array.

Complexity table of Selection sort

ComplexityBest caseAverage caseWorst case
TimeO(n2)O(n2)O(n2)
Space  O(1)

Selection sort algorithm

Step 1: All unsorted elements in the array are compared, and the smallest element is selected, and that element is replaced with the first element of the array.

Step 2: The second smallest element is selected, and that element is replaced with the second element of the array.

Step 3: Thus, this process continues until the entire array is sorted.

SELECTION SORT(ARR, N)
Step 1: Repeat Steps 2 and 3 for K = 1 to N-1
Step 2: CALL SMALLEST(ARR, K, N, POS)
Step 3: SWAP A[K] with ARR[POS]
             [END OF LOOP]
Step 4: EXIT  

Smallest algorithm

SMALLEST (ARR, K, N, POS)
Step 1: [INITIALIZE] SET SMALL = ARR[K]
Step 2: [INITIALIZE] SET POS = K
Step 3: Repeat for J = K+1 to N -1
             IF SMALL > ARR[J]
             SET SMALL = ARR[J]
             SET POS = J
             [END OF IF]
             [END OF LOOP]
Step 4: RETURN POS

Example of Selection sort

Suppose we have the following array, which we have to sort.

1186192

There are 6 elements in this array, so you will need 5 steps to sort it.

Step 1: The first position in the array has 11 stores. If you search in the whole array, you get the smallest value 1, and then you replace 11 with 1.

Selection sort

Step 2: The second position in the array has 8 stores. If you search in the whole array, you get the second smallest value 2, and then you replace 8 with 2.

Selection sort

Step 3: The third position in the array has 6 stores, but there will be no change in this place because there is no element smaller than 6, which means that it is already sorted. 

Selection sort

Step 4: The fourth position in the array has 11 stores. If you search in the whole array, you get the second smallest value 8, and then you replace 11 with 8.

Selection sort

Step 5: The fifth position in the array has 9 stores, but there will be no change in this place because there is no element smaller than 9, which means that it is already sorted.

1268911

Selection sort program in C language.

Output

Selection sort program in java language:

Pin It on Pinterest

Share This