Selection Sort Algorithm

Advertisements
Advertisements

 26 total views

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, A[1\cdots n].
  2. Find the smallest element in the array, A[1\cdots n].
  3. Replace with A[1] with the resultant smallest element and repeat the process again for a[2], and so on.
  4. Stop the search process when n -1 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.

Advertisements
\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 2 \hspace{2px} loops each time,  the outer loop runs n -1 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 \theta(n^2) 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 \theta(n^2).

Bestseller

Introduction to Algorithms, 3rd Edition (The MIT Press) 3rd Edition

Best book for students with little programming experience. The algorithms are designed and explained in easy to understand manner. The book includes many exercises and problems. The text is intended primarily for students studying algorithms or data structures. As it discusses engineering issues in algorithm design, as well as mathematical aspects, it is equally well suited for self-study by technical professionals.

Advertisements
Advertisements
Advertisements