Select sort implementation idea
Ideas:
Start with the first number and compare each subsequent number to find the smallest (ascending by default), then swap and so on until the sorting is complete.
Code implementation steps:
- First, take the subscript value of the first number as variable min, and iterate over the length of the number group
- In the loop, the first number is used to compare each number separately, and finally the subscript value of the smallest number is assigned to min
- Let’s switch these two numbers. So that’s what minimizes the first number
- Finally in the whole set of a cycle, cycle above the train of thought
Reference animation:
Code implementation
class ArrayList {
array = [];
// Used to insert numbers
insert(item) {
this.array.push(item);
}
// Switch two numbers
swap(m, n) {
let temp = this.array[m];
this.array[m] = this.array[n];
this.array[n] = temp;
}
// Select sort
selectSort() {
// Start at 0 and end at the penultimate position, length-2
for (let j = 0; j < this.array.length - 1; j++) {
let min = j;
// Start at min+1 and compare with the following number
for (let i = min + 1; i < this.array.length; i++) {
if (this.array[min] > this.array[i]) { min = i; }}this.swap(min, j); }}}let list = new ArrayList();
list.insert(12);
list.insert(2);
list.insert(45);
list.insert(123);
list.insert(481);
list.insert(56);
console.log(list.array); // [12, 2, 45, 123, 481, 56]
// Call selection sort
list.selectSort();
console.log(list.array); // [2, 12, 45, 56, 123, 481]
Copy the code
Efficiency of selection algorithm
It’s also about as efficient as bubble sort
Time complexity :O(N²)