Selection Sort Algorithm

The selection sort algorithm is a sorting algorithm that selects the smallest element from an array of unsorted elements called a pass. In each pass, it selects an unsorted element from the array and compares it with the rest of the unsorted array.

If any element smaller than the current smallest is found, replace it with a new element. This process is repeated until there are no more small elements. The entire array is sorted in this way.

The steps performed in each pass is as follows.

1. Given an array, .
2. Find the smallest element in the array, .
3. Replace with with the resultant smallest element and repeat the process again for , and so on.
4. Stop the search process when smallest elements are found, the last one is the largest in the array.

Selection-Sort Algorithm

Algorithm Selection-Sort(A)
{

for i = 1 to n-1
    i:= min

for j:= i +1 to n
    if A[j] < A[min]) then
        T: = A[min]
        A[min] := A[j]
        A[j] := T
}

Example of Selection Sort

In this example, we will sort 5 unsorted numbers.

\begin{aligned}
Array : (44, 7, 10, 77, 33)\\
Pass 1: (7, 44, 10, 77, 33)\\
Pass 2: (7, 10, 44, 77, 33)\\
Pass 3: (7, 10, 33, 77, 44)\\
Pass 3: (7, 10, 33, 77, 44)\\
Pass 4: (7, 10, 33, 44, 77)\\
The \hspace{1mm}sorted\hspace{1mm} array \hspace{1mm}is\hspace{1mm} (7, 10, 33, 44, 77)
\end{aligned}

Analysis of Selection Sort

The selection-sort algorithm has each time,  the outer loop runs time and the inner loop runs as follows.

\begin{aligned}
&for \hspace{1mm} 1^{st}  \hspace{1mm}element  \hspace{1mm}of  \hspace{1mm}outer  \hspace{1mm}loop = n-1  \hspace{1mm}times\\
&for  \hspace{1mm}2^{nd}  \hspace{1mm}element  \hspace{1mm}of  \hspace{1mm}outer  \hspace{1mm}loop = n-2  \hspace{1mm}times, so \hspace{1mm} on\\
&for  \hspace{1mm} n-1^{th}  \hspace{1mm} element  \hspace{1mm}or  \hspace{1mm} outer  \hspace{1mm}loop = 1  \hspace{1mm}time
\end{aligned}

= ((n)(n-1))/2

= (5(5 - 1))/2

= 20/2

= 10 

Let T(n) be the total running time of selection sort then,

\begin{aligned}
&T(n) = (4 + 3 + 2 + 1) \\
&= 10 \hspace{1mm}operations
\end{aligned}

The running time of the selection sort algorithm is then for both best-case and worst-case. Even in best-case, we will run a comparison in sub-array in the same manner as worst-case. Thus, the running time is .