Skip to main content

Arrays - Selection Sort in DSA

Selection Sort is an in-place comparison sorting algorithm that divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted. It repeatedly finds the minimum element from the unsorted part and puts it at the beginning of the unsorted part. The algorithm maintains two subarrays in a given array. The subarray which is already sorted and the remaining subarray which is unsorted. In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray.

Speed:

 

Algorithm

  1. The selection sort algorithm divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted.
  2. The algorithm repeatedly finds the minimum element from the unsorted part and puts it at the beginning of the unsorted part.
  3. The algorithm maintains two subarrays in a given array. The subarray which is already sorted and the remaining subarray which is unsorted.
  4. In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray.
  5. The array is sorted.
  6. Exit.
  7. The time complexity of the selection sort is O(n^2).
  8. The space complexity of the selection sort is O(1).

Pseudocode

Selection Sort
procedure selectionSort( A : list of sortable items )
n = length(A)
for i = 0 to n-1 inclusive do
min = i
for j = i+1 to n inclusive do
if A[j] < A[min] then
min = j
end if
end for
swap(A[i], A[min])
end for
end procedure

Diagram

Complexity

The time complexity of the selection sort is O(n^2). The space complexity of the selection sort is O(1).

Example

Selection Sort
function selectionSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
let min = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
}

const arr = [64, 25, 12, 22, 11];

console.log(selectionSort(arr)); // [11, 12, 22, 25, 64]

Practice Problems

Quiz

  1. What is the time complexity of the selection sort?
    • A) O(n)
    • B) O(n^2)
    • C) O(n log n)
    • D) O(1)
  • Correct Answer: B
  1. What is the space complexity of the selection sort?
    • A) O(n)
    • B) O(n^2)
    • C) O(n log n)
    • D) O(1)
  • Correct Answer: D
  • Explanation: The space complexity of the selection sort is O(1).
  1. What is the best-case time complexity of the selection sort?
    • A) O(n)
    • B) O(n^2)
    • C) O(n log n)
    • D) O(1)
  • Correct Answer: B
  1. What is the worst-case time complexity of the selection sort?

    • A) O(n)
    • B) O(n^2)
    • C) O(n log n)
    • D) O(1)
    • Correct Answer: B
  2. Is the selection sort stable?

    • A) Yes
    • B) No
    • Correct Answer: A
Try it yourself
Live Editor
function selectionSort() {
  let arr = [64, 25, 12, 22, 11];
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let min = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
  }
  return (
    <div>
        <h3>Selection Sort</h3>
        <p><b>Array:</b> [64, 25, 12, 22, 11]</p>
        <p>
            <b>Sorted Array:</b> [{arr.join(", ")}]
        </p>
    </div>
  )
}
Result
Loading...

In the above example, we have an array of numbers [64, 25, 12, 22, 11]. We are using the selection sort algorithm to sort the array in ascending order. The selection sort algorithm divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted. It repeatedly finds the minimum element from the unsorted part and puts it at the beginning of the unsorted part. The algorithm maintains two subarrays in a given array. The subarray which is already sorted and the remaining subarray which is unsorted. In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray. The sorted array is [11, 12, 22, 25, 64]. The time complexity of the selection sort is O(n^2) and the space complexity is O(1).

Conclusion

In this article, we learned about the selection sort algorithm. Selection sort is an in-place comparison sorting algorithm that divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted. It repeatedly finds the minimum element from the unsorted part and puts it at the beginning of the unsorted part. The algorithm maintains two subarrays in a given array. The subarray which is already sorted and the remaining subarray which is unsorted. In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray. The time complexity of the selection sort is O(n^2) and the space complexity is O(1). Selection sort is a stable sorting algorithm.