Blog

Sorting algorithms are fundamental in computer science and play a crucial role in organizing data efficiently. One such sorting algorithm is the Selection Sort, known for its simplicity and efficiency on small datasets. In this blog post, we’ll dive into Selection Sort, explore how it works, and implement it in TypeScript step by step.

What is Selection Sort?

Selection Sort is an in-place, comparison-based sorting algorithm. It works by dividing the input array into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, and the unsorted part contains all elements. The algorithm repeatedly selects the minimum (or maximum) element from the unsorted part and moves it to the end of the sorted part. This process continues until the unsorted part becomes empty, and the sorted part contains all elements in sorted order.

Step 1: Understanding the Algorithm

Let’s walk through the steps of Selection Sort with an example:

Input Array: [64, 25, 12, 22, 11]

1. The initial state:

• Sorted Part: []
• Unsorted Part: [64, 25, 12, 22, 11]

1. Find the minimum element in the unsorted part (11) and swap it with the first element (64).

• Sorted Part: [11]
• Unsorted Part: [25, 12, 22, 64]

1. Find the minimum element in the remaining unsorted part (12) and swap it with the second element (25).

• Sorted Part: [11, 12]
• Unsorted Part: [25, 22, 64]

1. Continue this process until the array is sorted.

Step 2: TypeScript Implementation

Now, let’s translate the Selection Sort algorithm into TypeScript code:

function selectionSort(arr: number[]): number[] {
    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] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap the found minimum element with the first element
        const temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }

    return arr;
}

const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray); // Output: [11, 12, 22, 25, 64]

Step 3: Explaining the TypeScript Code

1. selectionSort is a TypeScript function that takes an array of numbers as input and returns a sorted array.
2. We determine the length of the input array n.
3. The outer loop iterates through the array from the first element to the second-to-last element.
4. Inside the outer loop, we initialize minIndex to the current index i, assuming that the current element is the minimum.
5. The inner loop runs from i + 1 to the end of the array to find the index of the minimum element.
6. If we find an element smaller than the current minimum, we update minIndex.
7. After finding the minimum element in the unsorted part, we swap it with the element at index i.
8. Finally, we return the sorted array.

Conclusion

Selection Sort is a simple and straightforward sorting algorithm, making it easy to understand and implement. However, it may not be the most efficient choice for large datasets, as it has a time complexity of O(n^2). For larger datasets, more advanced sorting algorithms like Quick Sort or Merge Sort are typically preferred. Nevertheless, understanding Selection Sort is a great starting point for grasping the core concepts of sorting algorithms in computer science.