Selection Sort
Introduction
Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.
How does it work?
The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it with the first element of the unsorted portion. This process is repeated for the remaining unsorted portion of the list until the entire list is sorted.
begin selectionSort(list)
last := length(list) - 1;
nextMax := list[last];
for i := last - 1 downto 0 do
if list[i] > nextMax then
nextMax := list[i];
while (last > 0) and (list[last] = nextMax) do
last := last - 1;
while last > 0 do begin
prevMax := nextMax;
nextMax := list[last];
for i := last - 1 downto 0 do
if list[i] > nextMax then
if list[i] != prevMax then
nextMax := list[i];
else begin
swap(list[i], list[last]);
last := last - 1;
end
while (last > 0) and (list[last] = nextMax) do
last := last - 1;
end;
end selectionSort
Step By Step
Implementation (JavaScript)
function selectionSort(values) {
let minIndex;
for (let i = 0; i < values.length - 1; i++) {
minIndex = i;
for (let j = i + 1; j < n; j++) {
if (values[j] < values[minIndex])
minIndex = j;
}
// swap
let temp = values[minIndex];
values[minIndex] = values[i];
values[i] = temp;
}
}