Note: This is not a "professionally written" post. This is a post sharing personal notes I wrote down while preparing for FAANG interviews.
See all of my Google, Amazon, & Facebook interview study notes
Selection Sort Breakdown
- Worst Complexity: n^2
- Average Complexity: n^2
- Best Complexity: n^2
- Space Complexity: 1
- Method: Selection
- Stable: No
- Class: Comparison Sort
Selection Sort Notes
In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(n²) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort.
Selection Sort JavaScript Implementation
/*----------------------------------------------------------
| Selection Sort
*----------------------------------------------------------
|
| Time Complexity
| . Best: O(n^2)
| . Aver: O(n^2)
| . Worst: O(n^2)
|
| Space Complexity
| . O(1)
|
*/
const SelectionSort = (items = []) => {
for (let passes = 0; passes < items.length; passes++)
{
let min = passes
for (let i = passes; i < items.length; i++)
if (items[min] > items[i])
min = i
if (min != passes)
{
let temporary = items[passes]
items[passes] = items[min]
items[min] = temporary
}
}
return items
}
module.exports = SelectionSort
FAANG Study Resource: Cracking the Coding Interview
(Google Recommended)
Top comments (1)