Selection Sort

Selection sort is a sorting algorithm in which the list is considered into two parts, sorted part at left and unsorted part at right. It selects the smallest element from the unsorted list, in each iteration, and places that element at the beginning of unsorted list. Intitially, the sorted part in empty, that is, the whole list is unsorted. With each iteration, the smallest element is swapped with the leftmost element of the unsorted part of the list. After required iterations, we obtain a sorted list of elements.

Illustration:

Algorithm:

for all elements in list,step=from step=0 to step=length(list)-1

    min_idx=step

    for i from step+1 to length(list)-1 

        if value at index i < value at index min_idx

            min_idx = i

    swap as (list[step],list[min_idx])=(list[min_idx],list[step])

Time Complexity:

• Worst Case: O(n²)
• Average Case: O(n²)
• Best Case: O(n²)

Space Complexity: O(1)

Program for Selection Sort:

Output: