SELECTION SORT

• The idea of selection sort is rather simple, It basically determines the minimum (or) maximum of the list and swaps it with the element at the index where it supposed to be. The process is repeated such that the n minimum  (or) maximum element is swapped with the element at the n-1 index of the list.
• The principle of selection sort is different .if the array contains 'n' element is compared with the remaining (n-1) elements & which is the lower element, place that element in the first position .continue this process until all the elements in an array are sorted.  

EXAMPLE
      Consider the following array as an example.   
                       
For the first position in the sorted list,the whole list is scanned sequentially.The first position 24 is stored presently,we search the whole list and find that 8 is the lowest value. 
                       
So replace 8 with 23.after one iteration 8 which happens to be the minimum value in the list appears in the first position of the sorted list.
                
For the second position where 75 is residing we start scanning the rest of the list in a linear manner.we find 23 is the second lowest value in the list.
               
After two iterations two least values are positioned at the beginning in a sorted manner.
                
For the third position where 44 is residing we start scanning the rest of the list in a linear manner.we find 34 is the third lowest value in the list.
                
So replace 34 with 44.
               
The same process is applied to the rest of the item in the array.
                
Finally replace 44 with 75.we get the sorted list.
                

Efficiency of selection sort:

 Assume that an array containing 'n' elements is sorted using selection sort technique.

Now,

  The no.of comparisons made during first pass=n-1.

  No.of comparisons made during second pass=n-2.

  No.of comparisons made during last pass=1.

Total no.of comparisons=(n-1)+(n-2)+....+1

                                         =n*(n-1)/2

                                         =O(n^2)

Thus, efficiency of selection sort=O(n^2)

Advantages:

• It is one of the important simplest sorting technique.
• It is easy to understand and implement.
• It performs well in case of smaller list.
• It does not require additional memory.

Disadvantages:

• The efficiency of O(n^2) is not well suited for large sized list.
• It does not leverage the presence of any existing sort pattern in the list.

                             *****