Selection Sort Algorithm in Javascript

Overview

• O(n²) Time Complexity in all cases.

• Does less “Memory writes” when compared with other algorithms such as Quick sort, Merge sort, Insertion sort and Bubble sort.

• However, not an optimal algorithm in terms of “Memory writes”. There is other algorithm called Cycle sort which is optimal in terms of memory writes.

• Basic idea for Heap sort.

• Not Stable (order of elements may change).

• In-Place Algorithm

Idea

• Iterate through loop

• First iteration, find the minimum element and put it in the first place.

• Second iteration, find the minimum element and put it in the second place.

• Repeat this process, at the end the array is sorted.

Code

Time Complexity

The internal for-loop runs:

$$\begin{align*} (n-1) + (n-2) + \dots + 2 + 1 \\ = \frac{n(n-1)}{2} \\ \theta(n^2) \end{align*}$$