Selection Sort

 

Selection Sort


  • The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array.


  • In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

  • It is repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

  • The algorithm maintains two subarrays in a given array.
        1) The subarray which is already sorted.
        2) Remaining subarray which is unsorted.


Example:

        0             1            2                3           //Index

       7   4 5       2     // Values


Step 1:  set i, min=0 location and j=1st location


min / i= 0       j=   1               2                3

   7   4 5       2


Step 2: for i in N:   set min=i ie min=0


Step 3: for j in N:

compare arr[ j ]< arr[ min ]              ie arr[ 1 ]< arr[0]                            4<7                

If yes,  min=j min=1


Step 4: repeat to step 3

 compare arr[ j ]< arr[ min ]        ie arr[ 2 ]< arr[1]   5<4               

                    If yes,  min=j    

 compare arr[ j ]<arr[min]             arr[3] < arr[1]     2<4 

If yes,    min =j min=3

Step 5:  Swap the elements   arr[i], arr[min] = arr[min], arr[i]       i= 0         j=1           2           min=  3

                               2 4 5      


Step 6:  Repeat step 2 and 3  from min=i

                                    sorted    i/ min = 1       j=2                3

                                    2 4 5      


 compare arr[ j ]< arr[ min ]   ie arr[2]< arr[1]       5<4

               

If yes,  k=min k=1


compare arr[ j ]<arr[min]       arr[3] < arr[1]     7<4 


If yes,    k =min

    

             sorted    i/ min = 1       2             j=  3

                    2 4 5       7

 

Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending order

then, the worst case occurs.

Best Case Complexity: O(n2)
It occurs when the array is already sorted

Average Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither

ascending nor descending)

No comments

JavaFX Scene Builder

  This is an article about the JavaFX Scene Builder. You will get a short introduction about the installation and usage of the software. The...