Selection Sort -- an inplace sort

Selection Sort:

               Sort...from the word itself , It tells that arranging the elements in some order. Selection...taking some integer or any element that we will be taken as our wish. Totally we can say that picking up one integer and doing sorting by that number(for that iteration).

Working:

 

            Let us take an array of integers. 

                 

                  Lets select the first integer i.e. 1^st element of array (A[0] ) and compare it with the rest of the elements.If it is greater swap those two elements.Likewise for 2^nd iteration select the next element of array (A[1]) with the next succeding elements of the array.Similiarly we have to perform it ,for 3^rd ,4^th ....up to the last element.Any way for the last element there will be no successor to compare it with d next one .

                  For the first iteration the first element is selected. Here the first element is 19. It is compared with the rest of the elements in the array.

For 1^st iteration:

                        After this we will get the smallest element at the index 0. i.e. 6

           

                        Now we will take the second integer A[1]=19

For 2^nd iteration :

  

For 3^rd iteration:

For 4^rd iteration:

For 5^rd iteration:

                      
                 If the array has N elements ,Selection sort requires N-1 iterations.

Algorithm :

       Selection(int a[],int n)

·                                                           for i=0:n-2                            // A[] is length of 0 to n-1

◦                                                                for j=i+1 : n-1

▪                                                                        if A[i] >A[j]

·                                                           Swap(A[i], A[j])

·                   end

Analysis :

           

• By analysing the run time ,one might conclude that this sort should never be used in u programs as it takes more time for a larger numbers (for greater than 1000 numbers ).

                               O(n^2) comparisions

• The running time is also a quadratic equation in all cases.

                Best case : O(n^2)

               Average case : O(n^2)

               Wrost case : O(n^2)

• It is specifically an In-place comparison sort. It takes O(1) extra space (for swaping one extra interger is used)
  
  
• The difference between the Bubble sort and Selection sort is that Bubble sort selects the maximum element from the unsorted array and selection sort gets the minimum element from the array.
  
  
• However, Selection Sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, Selection Sort very well may be the algorithm of choice.

                                    O(n) swaps

Code :
                TO DOWNLOAD THE CODE 

           

                                 CLICK HERE