HomeOur TeamContact
Sorting
Selection Sort
Nisar
January 28, 2022
1 min

# .css-10kjd3a{box-sizing:border-box;margin:0;min-width:0;display:block;color:var(--theme-ui-colors-heading,#2d3748);font-weight:900;-webkit-text-decoration:none;text-decoration:none;margin-bottom:1rem;font-size:1.875rem;position:relative;}@media screen and (min-width:640px){.css-10kjd3a{font-size:2.25rem;}}@media screen and (min-width:1024px){.css-10kjd3a{font-size:3rem;}}Selection Sort

As the loop repeats over a collection, this algorithm finds and “chooses” the index with the lowest value and replaces it with the start index wherever appropriate.

The complexity of Space and Time

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

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

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

n is the length of the input array.

Input

`[8, 5, 1, 9, 5, 6, 2]`

Output

`[1, 2, 5, 5, 6, 8, 9]`

Hint

Split the input array into two subarrays. The first subarray must be sorted at all times, and it should begin with a length of zero, while the second subarray must be unsorted. In an unsorted array, find the smallest (or biggest) element and insert it into the sorted subarray with a swap method. Until the complete array is sorted, repeat these steps.

Pseudo Code

```DEFINE FUNCTION selectionSort(array):
SET currentIdx TO 0
WHILE currentIdx < len(array) - 1:
SET smallestIdx TO currentIdx
FOR i IN range(currentIdx + 1, len(array)):
IF array[smallestIdx] > array[i]:
SET smallestIdx TO i
swap(currentIdx, smallestIdx, array)
currentIdx += 1
RETURN array
```

Typescript Code

```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;
}

mocha.setup("bdd");
describe("Selection Sort", () => {
it("Test Case #1", function () {
const input = [8, 5, 1, 9, 5, 6, 2];
chai.expect(selectionSort(input)).to.deep.equal([1, 2, 5, 5, 6, 8, 9]);
});

it("Test Case #2", function () {
const input = [5, 3, 1, 2, 4];
chai.expect(selectionSort(input)).to.deep.equal([1, 2, 3, 4, 5]);
});
});

mocha.run();
```

Demo

https://codepen.io/evalteam/pen/rNYNgBB

Previous Article
Insertion Sort

Heap Sort
January 31, 2022
1 min