What is Selection Sort? And how it works?

Click here for more contents


Selection Sort

Selection Sort algorithm is used to arrange a list of elements in a particular order (Ascending or Descending). In selection sort, the first element in the list is selected and it is compared repeatedly with remaining all the elements in the list. If any element is smaller than the selected element (for Ascending order), then both are swapped. Then we select the element at second position in the list and it is compared with remaining all elements in the list. If any element is smaller than the selected element, then both are swapped. This procedure is repeated till the entire list is sorted.

The selection sort algorithm is performed using following steps...

• Step 1: Select the first element of the list (i.e., Element at first position in the list).
• Step 2: Compare the selected element with all other elements in the list.
• Step 3: For every comparision, if any element is smaller than selected element (for Ascending order), then these two are swapped.
• Step 4: Repeat the same procedure with next position in the list till the entire list is sorted.

To sort a unsorted list with 'n' number of elements we need to make ((n-1)+(n-2)+(n-3)+......+1) = (n (n-1))/2 number of comparisions in the worst case. If the list already sorted, then it requires 'n' number of comparisions.

Worst Case : O(n²)
Best Case : Ω(n²)
Average Case : Θ(n²)

Java programe

public class SelectionSort {

public static void main(String[] args) {

int list[]={5,3,8,9,2,1,11,0};

for(int i=0;i<list.length;i++){

for(int j=i+1;j<list.length;j++)

{

if(list[i]>list[j]){

int swap=list[i];

list[i]=list[j];

list[j]=swap;

}

}

}

System.out.println(Arrays.toString(list));

}

}

Click here for more