Selection Sort explaination – Tech Incent

Selection sort is a simple sorting algorithm that repeatedly selects the smallest (or largest, depending on sorting order) element from an unsorted portion of the list and swaps it with the element in the next position of the sorted portion of the list. This process continues until the entire list is sorted.

Explanation of how selection sort works:

1. Selection of the Smallest Element: The algorithm divides the input list into two parts: the sorted part at the beginning and the unsorted part at the end. Initially, the sorted part is empty, and the unsorted part contains the entire list.
2. Find the Minimum: It then iterates through the unsorted part to find the smallest element.
3. Swap Elements: Once the smallest element is found, it swaps it with the first element of the unsorted part (which becomes a part of the sorted portion).
4. Expand the Sorted Portion: Now, the sorted portion is expanded by one element, and the unsorted portion is reduced by one element.
5. Repeat Until Sorted: Steps 2-4 are repeated for the remaining unsorted portion of the list until the entire list is sorted.

Algorithm execution process

Here’s an example of selection sort on an array [23, 7, 39, 19, 9, 14].

1. Initial Array: [23, 7, 39, 19, 9, 14]
2. Pass 1: Find the smallest element in the unsorted part (7), swap it with the first element.
   • Array becomes [7, 23, 39, 19, 9, 14].
3. Pass 2: Find the smallest element in the unsorted part (9), swap it with the second element.
   • Array becomes [7, 9, 39, 19, 23, 14].
4. Pass 3: Find the smallest element in the unsorted part (14), swap it with the third element.
   • Array becomes [7, 9, 14, 19, 23, 39].
5. Pass 4: The array is now fully sorted.
6. Pass 5: The array is now fully sorted.
7. Pass 6: The array is now fully sorted.

So, the sorted array using selection sort for [23, 7, 39, 19, 9, 14] would be [7, 9, 14, 19, 23, 39].

Selection sort has a time complexity of O(n^2), where ‘n’ is the number of elements in the list. This makes it inefficient for large lists, but it has the advantage of requiring only a small amount of additional memory space.

Selection sort algorithm

/**
 * @approach Align small digit to big digit [ 7 -> 9 -> 14 -> ...]
 * @complexity
 * - Time complexity: O(n2); Call: Order of n square
 * - Space complexity: O(1); Call: Order of 1
 */
function selectionSort(arr: number[]): number[] {
  let min_index: number,
    i: number = 0,
    j: number,
    temp: number;
  for (i; i < arr.length; i++) {
    min_index = i;
    for (j = i + 1; j < arr.length; j++) {
      if (arr[min_index] > arr[j]) {
        min_index = j;
      }
    }
    if (min_index !== i) {
      temp = arr[i];
      arr[i] = arr[min_index];
      arr[min_index] = temp;
    }
  }
  return arr;
}

const arr = [23, 7, 39, 19, 9, 14];
console.log(selectionSort(arr)); // [ 7, 9, 14, 19, 23, 39 ]