Skip to content

Latest commit

 

History

History
61 lines (43 loc) · 3.09 KB

2. Selection Sort.md

File metadata and controls

61 lines (43 loc) · 3.09 KB
Raw

Selection Sort

The Selection Sort algorithm sorts an array by repeatedly finding the smallest element (considering ascending order) from the unsorted part and putting it at the beginning. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list.

Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Time Complexity

  • Selecting the minimum value requires scanning n elements (taking n - 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n - 1 elements and so on. Therefore, the total number of comparisons is (n - 1) + (n - 2) + ... + 1, which is of time complexity O(n2). Each of these scans requires one swap for n - 1 elements (the final element is already in place).
  • One thing which distinguishes Selection Sort from other sorting algorithms is that it makes the minimum possible number of swaps, n − 1, in the worst case. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

Exercise

Write a function called selectionSort that takes an array of numbers, and returns the sorted array with all the numbers sorted from smallest to largest. Additionally, you should be able to see how the smallest values get "selected" into their proper position for each pass.

Examples:

  • Random

    selectionSort([9,0,7,3,4,6,8,2,1,5]) // [0,1,2,3,4,5,5,6,7,8,9]

  • Nearly Sorted

    selectionSort([8,1,2,3,4,5,6,7]) // [1,2,3,4,5,5,6,7,8]

  • Reversed

    selectionSort([9,8,7,6,5,4,3,2,1]) // [1,2,3,4,5,5,6,7,8,9]

  • Few Unique

    selectionSort([4,5,2,4,5,1,3,5,4,5,3,5,3,2,4]) // [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]

Note: You should also see the status of the array after each pass in the console!

Solution

function selectionSort(arr) {
  //  Loop over the array
  for(let i = 0; i < arr.length - 1; i++) {
    //  Initialize a value to store the index of the smallest element
    let minIdx = i;
    //  Create an inner loop to select the next smallest element
    for(let j = i + 1; j < arr.length; j++) {
      //  If current element is smaller than the smallest element,
      //  save its index
      if(arr[j] < arr[minIdx]) minIdx = j;
    }
    //  Place the smallest element into its proper spot
    if(minIdx !== i) [arr[minIdx], arr[i]] = [arr[i], arr[minIdx]];
  }
  //  Return the sorted array
  return arr;
}

References

Toptal - Selection Sort Visualization

Wikipedia - Selection Sort

GeeksforGeeks - Selection Sort