A simple implementation of selection sort in javascript using ES6.
An algorithm to sort the given array of elements in ascending or descending order.
The selection sort algorithm sorts the array by finding the smallest or biggest element from the array and swapping it with the element at first position than finding the next smallest or biggest and swapping it at the second position. It repeats this until all the elements are sorted in the given order.
While sorting it maintains two subarrays.
1). Arrays with sorted elements.
2). Arrays with unsorted elements.
Characteristics of Selection Sort.
- This is the most simplest and the slowest sorting algorithm.
- Also it is in-place sorting algorithm, Which means it does not require extra space while sorting.
Example
Input: 1 8 2 4 5 Output 1 2 8 4 5 1 2 4 8 5 1 2 4 5 8
Check out the following image for better understanding
Implementation
- We will use two loops to sort the arrays.
- In first loop we will loop till the second last element as we need to compare it with last element.
- In the second loop we will start from 1 element after first loop’s element till the last element of the array.
- Depending upon the sorting order we will swap the elements.
let selectionSort = (arr) => {
//Loop till the second last element
for(let i = 0; i < arr.length - 1; i++){
//Loop after the i till the last element
for(let j = i + 1; j < arr.length; j++){
//if jth element is less than the ith element then swap
//change < to > for sorting in descending order
if(arr[j] < arr[i]){
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
//return the sorted array
return arr;
}
Using ES6 Array Destructuring to swap the elements.
if(arr[j] < arr[i]){
[ arr[i], arr[j] ] = [ arr[j], arr[i] ];
}
Input: console.log(selectionSort([1, 8, 2, 4, 5])); Output: [1, 2, 4, 5, 8]
Time complexity: O(n ^ 2).
Space complexity: O(1).
Time and Space complexity
- We are using two nested loops to sort the array, so Time complexity is O(n ^ 2).
- We are using constant space, so Space complexity is O(1).