# [#2 Sort: Selection Sort](https://leetcode.com/problems/find-the-town-judge/)

###### tags:`Sort`

<br>

## Issue
Write a function that takes in an array of integers and returns a sorted version of that array. Use the Selection Sort algorithm to sort the array.

If you're unfamiliar with Selection Sort, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code.

### Example 1

Input: array = [8, 5, 2, 9, 5, 6, 3]
Output: [2, 3, 5, 5, 6, 8, 9]

### Hints:

:::spoiler Hint 1
Divide the input array into two subarrays in place. The first subarray should be sorted at all times and should start with a length of 0, while the second subarray should be unsorted. Find the smallest (or largest) element in the unsorted subarray and insert it into the sorted subarray with a swap. Repeat this process of finding the smallest (or largest) element in the unsorted subarray and inserting it in its correct position in the sorted subarray with a swap until the entire array is sorted.
:::

### Optimal Space & Time Complexity

:::spoiler Answer
- Best: O(n^2) time | O(1) space - where n is the length of the input array

- Average: O(n^2) time | O(1) space - where n is the length of the input array

- Worst: O(n^2) time | O(1) space - where n is the length of the input array
:::

<br>

## Solutions

### Official

:::spoiler Solution
<br />

// Best: O(n^2) time | O(1) space
// Average: O(n^2) time | O(1) space
// Worst: O(n^2) time | O(1) space

function selectionSort(array) {
    let startIdx = 0;
    while (startIdx < array.length - 1) {
        let smallestIdx = startIdx;
        for (let i = startIdx + 1; i < array.length; i++) {
            if (array[smallestIdx] > array[i]) smallestIdx = i;
        }
        swap(startIdx, smallestIdx, array);
        startIdx++;
    } return array;
}

function swap(i, j, array) {
    const temp = array[j];
    array[j] = array[i];
    array[i] = temp;
}

:::

### Everyone's

:::spoiler 東

// Time O(n^2) | Space O(1) - n is the length of input array
function selectionSort(array) {
  for(let i = 0; i < array.length; i++) {
    let currMinIdx = i;
    for(let j = i + 1; j < array.length; j++) {
      if(array[j] < array[currMinIdx]) currMinIdx = j;
    }
    if(i !== currMinIdx){
      [array[i], array[currMinIdx]] =  [array[currMinIdx], array[i]];
    }
  }
  return array;
}

:::

<br>

:::spoiler Hao

/**
 * Time complexity: O(n^2);
 * Space complexity: O(1);
 */

function selectionSort(array) {
    const len = array.length;

    if (len > 1) {
        let unsortedStartIdx = 0;
    
        for (let i = 0; i < len; i += 1) {
            let [_, curMinIdx] = array.reduce(([curMin, curMinIdx], value, idx) => {
                if (idx < unsortedStartIdx || value >= curMin) return [curMin, curMinIdx];
                else return [value, idx];
            }, [array[unsortedStartIdx], unsortedStartIdx]);

            [array[unsortedStartIdx], array[curMinIdx]] = [array[curMinIdx], array[unsortedStartIdx]];

            unsortedStartIdx += 1;
        }
    }

    return array;
}

:::

<br>

:::spoiler YC

/*
  time: O(n^2) - where n is the length of the input array 
  space: O(1)
*/

function selectionSort(array) {
  for(let i = 0; i < array.length; i++){
    let smallest = i;
    for(let j = i + 1; j < array.length; j++){
      if(array[smallest] > array[j]){
        smallest = j;
      }
    }
    if(i !== smallest){
      [array[i], array[smallest]] = [array[smallest], array[i]];
    }
  }
  return array;
}

:::

<br>

:::spoiler 月薪

/* Time: O(n^2), Space O(1)
   n is the length of the array.
*/
function selectionSort(array) {
    for(let i = 0; i < array.length; i+=1){
        let minIdx = i;
        for(let j = i; j < array.length; j+=1){
            if(array[j] < array[minIdx]){
                minIdx = j;
            }
        }
        [array[minIdx], array[i]] = [array[i] , array[minIdx]];
    }
    return array
}

:::

<br>

## Discussion
### Selection Sort

[初學者學演算法｜排序法入門：選擇排序與插入排序法](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff)