Time Complexity of Selection Sort in Data Structure

What is Time Complexity?

The term “Time complexity” can be defined as the number of times executions made of a particular sequence of instructions and not the total amount of time taken. This is because the total time required also depends on external factors such as the compiler used, processor speed, etc.

There are mainly 3 types of Time Complexities:

Best Time complexity

The best time complexity displays the minimum time taken to compute the lower bound of the algorithm.

Example: In linear search, the best case occurs when the search data is in the first place of the big data. 

Average Time Complexity

In the average time complexity case, we take all random inputs and compute the computation time for all inputs and divide it by the total number of inputs. 

Worst Time Complexity

The worst time complexity defines the input that takes the longest time to execute the algorithm. It calculates the upper bound of the worst-case algorithm.

For example: linear search has the worst case when the search data is in the last place of the big data.

Time Complexity of Selection Sort Algorithm

Selection sort algorithm is used for sorting an array of elements. It works by repeatedly selecting the smallest elements from the unsorted portion of the array and swapping it with the first element of the unsorted portion.

The time complexity of selection sort is O(n²). This implies that the time taken by the algorithm grows quadratic rapidly with the size of the input. This makes selection sort’s efficiency less than other sorting algorithms, such as mergesort and quicksort, which have a time complexity of O(n log n).

Selection sort works by repeatedly selecting the minimum element from the unsorted portion of the array and swapping it with the element at the current position. This process repeats until the whole array gets sorted.

The time complexity of selection sort can be analyzed by considering the number of steps required to sort an array of size n. In the best case complexity, the array is already sorted and the selection sort algorithm takes O(n) time to complete. In the worst case complexity, the array is arranged in reverse order and the selection sort algorithm takes O(n²) time to complete.

In the average case, time complexity of selection sort is also O(n²). This means that, on average, the selection sort algorithm will take O(n²) time to sort an array of size n.

Selection sort is not a very efficient sorting algorithm, especially for large inputs. There are many other sorting algorithms that have a better time complexity, such as quicksort and mergesort, which have a time complexity of O(n log n).This is because the algorithm requires two nested loops to sort the elements in the list. The inner loop is used to find the minimum element in the unsorted part of the list, and the outer loop is used to iterate through the entire list. Since both the loops run in O(n) time, the overall time complexity turns out is O(n²).

Selection sort is not a very efficient sorting algorithm, especially when compared to more advanced algorithms such as quick sort and merge sort. However, selection sort is relatively simple to implement and can be useful in certain situations, such as when the input list is very small or when the list is almost sorted and only requires a few swaps to be completely sorted.

Selection sort has a quadratic time complexity because it uses nested loops to sort the elements in the list. The inner loop iterates over the unsorted portion of the list, while the outer loop iterates over the entire list. This as a result gets a running time of O(n × n) = O(n²).

• Best case Time Complexity of Selection Sort: O(n)
• Average case Time Complexity of Selection Sort: O(n²)
• Worst case Time Complexity of Selection Sort: O(n²)

Algorithm for Selection Sort:

Selection_Sort(arr, size)
start loop and repeat (size - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element< minimum
set element as new_minimum
swap minimum with first unsorted position
endselection_Sort

Pseudo-code for the Selection Sort Algorithm:

procedure selectionSort(A: list of sortable items)
    n = length(A)
fori = 1 to n - 1
minIndex = i
for j = i + 1 to n
if A[j] < A[minIndex]
minIndex = j
swap A[i] and A[minIndex]