1. Introduction
In coding tests and algorithm problem-solving, sorting algorithms are an essential topic to learn. Among various methods of sorting arrays, Selection Sort is considered a good algorithm to learn in the initial stages due to its simple implementation and intuitive process. In this tutorial, we will explore the concept and principles of Selection Sort, as well as how to implement it in JavaScript in detail.
2. What is Selection Sort?
Selection Sort is a simple algorithm for sorting arrays that operates by repeatedly finding the smallest (or largest) value in the given array and swapping it with the current position. This algorithm works by dividing the process into sorted and unsorted sections with each iteration.
2.1. How It Works
Selection Sort operates as follows:
- Starting from the first element of the array, find the smallest element among the remaining elements and swap it with the first element.
- Repeat the same process starting from the second element, swapping the second element with the smallest element among the second and subsequent elements.
- Continue this process until the last element of the array.
2.2. Time Complexity of Selection Sort
The time complexity of Selection Sort is O(n²) in both the worst and average cases. This means that performance can degrade sharply depending on the size of the array. Therefore, Selection Sort is most suitable for use with small datasets.
3. Implementing Selection Sort
In this section, we will implement Selection Sort in JavaScript.
3.1. Basic Implementation
The code below is a basic JavaScript function implementing Selection Sort:
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
// Initialize the current index (i) as a candidate
let minIndex = i;
// Scan the remaining array to find the index of the smallest element
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // Update minIndex if a smaller value is found
}
}
// Swap the candidate minimum value with the current position (i)
// Swap only if the current position is not the minimum
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray); // [11, 12, 22, 25, 64]
3.2. Code Explanation
The code above is a function that uses the Selection Sort algorithm. Let’s analyze the function step by step:
const n = arr.length;: This calculates the length of the array.for (let i = 0; i < n - 1; i++): The first loop iterates through each element of the array.let minIndex = i;: This initializes the index of the current smallest value.for (let j = i + 1; j < n; j++): The second loop iterates through the remaining array to find the index of the smallest element.if (arr[j] < arr[minIndex]) { minIndex = j; }: If the current element of the array is less than the current minimum, it updates the index of the minimum value.if (minIndex !== i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; }: Finally, if the minimum value is not at the current index, it performs the swap.
4. Optimized Selection Sort
The basic Selection Sort can be optimized. By reducing unnecessary swaps, we can improve performance slightly. For instance, adding a check to see if sorting is already complete and terminating the loop when no further swaps are needed can enhance performance. The code below shows the optimized Selection Sort:
function optimizedSelectionSort(arr) {
const n = arr.length;
let isSorted = true;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
isSorted = false; // Remember that a swap will occur
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
// Exit the loop if the array is already sorted
if (isSorted) break;
}
return arr;
}
// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = optimizedSelectionSort(unsortedArray);
console.log(sortedArray); // [11, 12, 22, 25, 64]
4.1. Optimization Explanation
The optimized Selection Sort function uses let isSorted = true; in the initialization stage to track whether the array is sorted. After each iteration, if an actual swap occurs in the array, this flag is set to false. If no swap occurs in the current iteration, it indicates that the array is fully sorted, and the loop is exited.
5. Practical Example
Let me show you an example of sorting actual data using Selection Sort, such as sorting student grade data. This can help compare students’ scores or provide necessary information.
const students = [
{ name: "Emily", score: 85 },
{ name: "David", score: 92 },
{ name: "Sophie", score: 76 },
{ name: "John", score: 89 },
{ name: "Max", score: 90 },
];
function selectionSortByScore(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j].score < arr[minIndex].score) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
const sortedStudents = selectionSortByScore(students);
console.log(sortedStudents);
5.1. Practical Example Explanation
The code above demonstrates how to sort an array based on students’ scores. Each student is represented as an object with a name and score, and the selectionSortByScore function sorts them in ascending order of scores and provides the output.
6. Conclusion
Selection Sort is a simple implementation that is very useful for beginners to understand the basic principles of algorithms. However, due to its O(n²) time complexity, its efficiency decreases with large datasets, and it is recommended to use better algorithms such as Quick Sort or Merge Sort in real production environments. Nevertheless, building a foundation in algorithms through Selection Sort is an important learning process. I hope this knowledge will be of great help in preparing for coding tests.