Understanding Selection Sorting Using Pseudo Codes And Example In Java


Selection Sorting Algorithm -

As the name suggest, this sorting algorithm based on selection of smallest element of the list.

In this algorithm, we pick smallest element of the list in each iteration, compares with list element and do swapping. 

During this process we can see that a new sorted list starts generating from right of the list and left part is for unsorted part of the list.  

Same as Insertion sort Selection sort is also performs better than Bubble sort. 

Complexity of selection sort is O(n2) where n is number of data values being sorted. 

Same as Bubble sort this sort is also not advisable for large amount of data.

Assuming that i have list of unsorted array.
20, 55, 2, 71, 10

Let's start with the process ...

Step-1 . Run loop from 0 to array size.

Step-2 . Search the smallest element of the list

Start reading every element of the array one by one, compare each element with other element, array[0] will compare with array[1] , array[2], array[3], array[4] elements and smallest one will be stored into variable (here we are using min as variable). 

Get smallest element's array index, it would require during swapping process.     
  
This process will repeat again after step-4, in next loop process array[1] will be compared with other 2,3,and 4 indexes and will get next smallest element of the list. 

Taking i variable to run the loop.

/* min = array[0] i.e. 22 */

initially min = array [0]     


loop 0 to array_Size 


/* min value will compare with    

each array's element and  min 


will have smallest element of the list. */


if ( min > array[i] ) {   


min = array[i]             

smallest_element_index = i;           
                              
}           
           
end loop 

}

Step-3 .  
Compare smallest element with array elements and do swapping. 

Compare smallest element with array indexes if array element is greater than smallest element then swap smallest element with it's index.

example: first time, if smallest element is 1, loop will run to read all array's element check if 1 is less than array[0] then swap it with array[0] otherwise check with another array's index.

if ( min < array[i] ) {


array[smallest_element_index] = array[i];

array[i] = min;

         
}
         
Step-4 .  
After 1st smallest element's swapping process next smallest element would be search, for that repeat step-1.

As you can see that from right side sorted list will be generated and left side will have remaining unsorted list.


Selection-Sorting
Understanding Selection Sorting Algorithm. ByTechAchievers.com


 Selection Sort Implementation In Java –

public class SelectionSortExample {

  public static void main(String []args) {


    System.out.println("Selection Sorting Process ...\n");

    int array[] = {22,55,2,71,1};

    int min = array[0];

    int listSize = 5;   

    int j = 0;

    int smallest_element_index = 0;   

    
    while ( j != listSize-1 ) {

    
    if ( j >0 )


      min = array[j];

      for ( int i=j+1; i<=4; i++) {
     

       if (min > array[i]) {

          min = array[i];    

          smallest_element_index = i; 

      }

    }

    System.out.println("Smallest element of list - "+min);

    
    System.out.println("Compare smallest element - "+  min+" 

    with array's "+j +"-index element - "+array[j]);
        
    
    if (min < array[j]) {
           

       System.out.println("Smallest element  - "+min + 

       " will be swapped with - "+array[j]);

       array[smallest_element_index] = array[j];

       array[j] = min;

    }

    
    System.out.println("\nUpdated list would be  - ");

    printList (array, listSize);

    System.out.println("\n");

        
    j = j + 1;

   }

  } // end of main method

   
   /* Method to print list */ 

   public static void printList (int array[], int listSize) {

   
   for (int i=0 ; i<=listSize-1; i++) {
                 
     System.out.print (array[i] + ",");

   }


  } // end of method


} // end of class


   OUTPUT -               

    Selection Sorting Process ...
   Smallest element of list - 1
Compare smallest element - 1 with array's index element - 22
Smallest element  - 1 will be swapped with - 22

Updated list would be  -
1,55,2,71,22

Smallest element of list - 2
Compare smallest element - 2 with array's 1-index element - 55
Smallest element  - 2 will be swapped with - 55

Updated list would be  -
1,2,55,71,22

Smallest element of list - 22
Compare smallest element - 22 with array's 2-index element - 55
Smallest element  - 22 will be swapped with - 55

Updated list would be  -
1,2,22,71,55

Smallest element of list - 55
Compare smallest element - 55 with array's 3-index element - 71
Smallest element  - 55 will be swapped with - 71

Updated list would be  -
1,2,22,55,71


No comments

Powered by Blogger.