Hello Friends... Come-On... Let's learn about "SELECTION SORT"

SELECTION SORT

->It is one of the easiest method of Sorting the given unsorted values/elements.

->Let's take an example:

->There's an array 'A' having 5 elements in it.

Unsorted Array:

->Now a search is performed to locate an element which is smallest among all the elements.

->When that element is found it is interchanged with the first element of the unsorted array.

->Here 1 is smallest element among all the elements and it's at 3rd position. Hence this smallest element interchange it's position with the element which is at 1st position. i.e.

-> Now, the search for the second smallest element is carried out.

-> Now this search of examining the second smallest element is made from 2nd position of the array because the element at the first position is already sorted off. i.e.

->Now the element which is the second smallest element is interchanged with the element that is located in the second position of array

-> Thus, this process of searching for the next smallest element and placing it on its appropriate position goes on until and unless all the elements are being sorted off.

-> Hence the remaining steps to sort the elements will be :

->Now elements 4 and 5 are already at their appropriate place. So, final sorted result would be:

-> Now we will write the PseudoCode for this whole Selection Sort Process:

SelectionSort(A[],n)      
//Function takes an array A[ ] having 'n' elements.
{           int i,j
           for i <- 0 to n-2
             {
                         Min <- i
                         for j<- i+1 to n-1
                         {
                                  if(A[j] < A[Min])
                                  Min <- j
                         }

// Extra space is created to store value of A[i] at temp
              

              temp <- A[i]          
              A[i] <- A[Min]
              A[Min] <- temp
             }
}

-> Implementation Of Selection Sort in C++ :

#include<iostream.h>
#include<conio.h>

void SelectionSort(int A[], int n)
{
       for(int i=0; i<n-1;i++)
       {
         int min=i;
         for(int j=i+1;j<n;j++)
         {
           if (A[j]<A[min])
           min=j;
         }
         int temp=A[i];
         A[i]=A[min];
         A[min]=temp;
       }
}

int main()
{
       int k;
       clrscr();
       int A[ ] = {4,5,1,3,2};
       SelectionSort(A,5);
       for(k=0;k<5;k++)
         cout<<A[k]<<"  ";
       getch();
       return 0;
}

-> OUTPUT:

-> Time Complexity of this program :

Best Case :        O(n^2)
Average Case :  O(n^2)
Worst Case:      O(n^2)


THANK-YOU..!!
JAI-HIND..!!