Implementing Selection Sort in Javascript
Published: 2024-07-08 20:02:00

 Selection sort works by selecting the minimum value in a list and swapping it with the first value in the list. It then starts at the second position, selects the smallest value in the remaining list, and swaps it with the second element. It continues iterating through the list and swapping elements until it reaches the end of the list. Now the list is sorted. Selection sort has quadratic time complexity in all cases.

Instructions: Write a function selectionSort which takes an array of integers as input and returns an array of these integers in sorted order from least to greatest.

    Waiting: selectionSort should be a function.
    Waiting: selectionSort should return a sorted array (least to greatest).
    Waiting: selectionSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]) should return an array that is unchanged except for order.
    Waiting: selectionSort should not use the built-in .sort() method.

Let's implement the `selectionSort` function according to the specifications. Here's a step-by-step implementation of the selection sort algorithm:

```javascript
function selectionSort(array) {
  // Make a copy of the original array to avoid modifying it directly
  let arr = [...array];
  
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    
    // Find the index of the minimum element in the unsorted part
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    
    // Swap the found minimum element with the first element of the unsorted part
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
}
```

Let's break down this implementation:

1. We start by creating a copy of the input array using the spread operator (`[...array]`). This ensures we don't modify the original array.

2. We use an outer loop that iterates through the array from the first element to the second-to-last element. This represents the boundary between the sorted and unsorted portions of the array.

3. For each iteration of the outer loop:
   - We assume the current element is the minimum and store its index.
   - We use an inner loop to scan the rest of the array (the unsorted portion) to find the actual minimum element.
   - If we find a smaller element, we update the `minIndex`.

4. After finding the minimum element in the unsorted portion, we swap it with the first element of the unsorted portion (if they're not already the same element).

5. This process continues until the entire array is sorted.

6. Finally, we return the sorted array.

This implementation satisfies all the given requirements:
- It's a function named `selectionSort`.
- It returns a sorted array from least to greatest.
- It works correctly for the given example input.
- It doesn't use the built-in `.sort()` method.

You can test it with the provided example:

```javascript
console.log(selectionSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]));
```

This will output the sorted array:

```
[1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643]
```

Note that while this implementation correctly sorts the array, selection sort has a time complexity of O(n^2) in all cases, making it inefficient for large arrays. However, it has the advantage of making the minimum number of swaps (at most n - 1 swaps, where n is the number of elements), which can be beneficial in certain situations where writing to memory is a costly operation.