Home Data Structures Selection Sort Algorithm

Selection Sort Algorithm

Selection sort is an in-place sorting algorithm that works on the notion of finding the minimum element(if sorting in ascending order) or maximum element(if sorting in descending order) in the unsorted array and placing it in its correct position.

It divides the entire unsorted array into two subarrays: sorted and unsorted. In every iteration, it picks the minimum/maximum element from the unsorted subarray and places it in the sorted subarray. Hence it runs n times.

Let’s understand how selection sort works
  1. Start from the first element and search for the smallest element in the entire array.
  2. Replace the minimum element with the first element of the array.
  3. Repeat steps 1 and 2 for each element until the entire array is no sorted.

Selection Sort
Selection Sort

Algorithm

Following is the algorithm for selection sort.

selection_sort( arr ){
    for i in range 0 to (n-1){
        min = i;
        for j in range (i+1) to (n-1){
            if(arr[j] < arr[min])
                min = j;
        }
        swap(arr[i],arr[j]);
    }
    return arr;
}

Implementation in CPP

Time Complexity

The time complexity of the above algorithm in the worst case is O(N²), and O(N) in the best case i.e, when the entire array will be sorted.

Remember:
1. Best case time complexity = O(N)
2. Worst-case time complexity = O(N²)
3. Auxiliary space requirement = O(1)
4. The total number of swaps done = O(N).

Did, we miss something, or do you want to add some other key points?🤔
Please comment.

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here