selection sort algorithm and selection sort Time Complexities

In this tutorial, you'll find out how the selection sort algorithm works. Also, you'll find working samples of selection sort in C, C++, Java, and Python.

Selection sort is an algorithm that selects the littlest element from an unsorted list in each iteration and places that element at the start of the unsorted list.

Learn How the Selection Sort Works

•  Set the primary element as a minimum.

check the first minimum number

• Compare minimum with the second element. If the second number is smaller than minimum, so assign the second number as minimum in the selection sort algorithm.
  
  Compare minimum with the third element. Again, if the third number is smaller, then assign minimum to the third number in the selection sort algorithm or do nothing. the method goes on until the last element. 

Compare the number with the remaining number

 

• After each iteration, minimum is placed within the front of the unsorted list.

Swap the first number with the minimum in sorting algorithm

 

• For each iteration, indexing starts from the primary unsorted element. Step 1 to three are repeated until all the weather are placed at their correct positions.

step - 0 for sorting

 

step - 1 for sorting

 

step - 2 for sorting

 

step - 3 for sorting

 

 Algorithm For Selection Sort

selectionSort(array, size)
 repeat (size - 1) times
 set the primary unsorted element because the minimum
 for every of the unsorted elements
 if element < currentMinimum
 set element as new minimum
 swap minimum with first unsorted position
end selectionSort

Number of comparisons: (n - 1) + (n - 2) + (n - 3) + ..... + 1 = n(n - 1) / 2 nearly equals to n2.

Complexity for selection sort algorithm = O(n2)

Also, we will analyze the complexity by simply observing the number of loops. There are 2 loops therefore the complexity is n*n = n2.

Time Complexities:

Time Complexities Selection Sort Algorithm

•  Worst Case Complexity: O(n2)

 If we would like to sort in ascending order and therefore 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 weather of the array are in jumbled order (neither ascending nor descending).

The time complexity of the choice sort is that the same altogether cases. At every step, you've got to seek out the minimum element and put it within the right place. The minimum element isn't known until the top of the array isn't reached.

Space Complexity:

Space complexity is O(1) because an additional variable temp is employed.

• Selection Sort Applications

The selection sort is employed when:

•  a little list is to be sorted

•  cost of swapping doesn't matter

•  checking of all the weather is compulsory

•  cost of writing to a memory matter like in non-volatile storage (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)