sort an array
selection sort
[ nested for loops ]

Sort an array

Write a function, using the Selection Sort algorithm, that takes an array of numbers or an array of strings and returns the array sorted in ascending order. The original array will be updated.


Sorting algorithms are a set of instructions that takes an array or list as an input and arranges the items into a particular order.

Selection Sort algorithm is one of the simplest sorting algorithms; It is also one of the least efficient.

Some sorting algorithms are more efficient than others.

The effectiveness of a sorting algorithm is usually defined by the following performance measures ↴

Time complexity the amount of time it takes for the algorithm to run.

Space complexity the amount of memory space it takes to perform the sorting based on an algorithm.


Selection Sort divides the list into a sorted and an unsorted region.

It repeatedly selects the smallest (or largest, depending on the order) element from the unsorted region and moves it to the end of the sorted region. This process continues until the entire list is sorted.

Selection Sort has a time complexity of O(n2) for all cases (worst, average, and best), where n is the number of elements in the list. This is because it always performs n(n-1)/2 comparisons.

Selection Sort has a space complexity of O(1), meaning it sorts the list in place and requires only a constant amount of additional memory.


Example ...

Enter an array ...

[10, 8, 4, 6, 2] original array

[2, 4, 6, 8, 10] array sorted in ascending order

The original array will be updated.

Arrays are used to store multiple values in a single variable.

Each value is called an element, and each element has a numeric position in the array, known as its index.

Arrays are zero-indexed, meaning the first element is at index 0, the second at index 1, and so on.

Arrays can contain any data type, including numbers, strings, and objects.

const arr1 = [2, 4, 6]; array

arr1[0]; element at index 0 → 2

arr1[1]; element at index 1 → 4

arr1[2]; element at index 2 → 6

arr1[3]; element at index 3 → undefined index not found


Strings are a sequence of zero or more characters written inside quotes used to represent text.

Strings may consist of letters, numbers, symbols, words, or sentences.

Strings are immutable, they cannot be changed.

Each character in a string has an index.

The first character will be index 0 the second character will be index 1 and so on.

There are two ways to access an individual character in a string.

charAt() method

const str1 = "abc"; string

str1.charAt(0); character at index 0 → "a"

str1.charAt(1); character at index 1 → "b"

str1.charAt(2); character at index 2 → "c"

str1.charAt(3); character at index 3 → "" index not found

Alternatively use at() or slice() methods

bracket notation []

const str2 = "abc"; string

str2[0]; character at index 0 → "a"

str2[1]; character at index 1 → "b"

str2[2]; character at index 2 → "c"

str2[3]; character at index 3 → undefined index not found


Numbers are used to represent both integer and floating-point values.

Numbers are most commonly expressed in literal forms like 255 or 3.14159 ↴

let num1 = 5; → number

let num2 = 2.5; → number

let num3 = num1 + num2;

console.log(num3); returns ↴

7.5 → number


Sort an array using the Selection Sort algorithm using nested for loops


for loop repeatedly executes a block of code until a specified condition evaluates to false.

The loop runs a block of code a set number of times, defined by an initialization, a condition, and an increment.

for (let x = 0; x < 4; x++) {

console.log(x);

}

Loop variable x is initialized to 0

Condition x < 4 is checked before each iteration.

The loop will continue to run as long as x is less than 4

The loop repeatedly executes a block of code 4 times, from 0 to 3

For each iteration of the loop, the current value of x is printed to the console.

After each iteration, x is incremented by 1 x++

When x reaches 4 the condition evaluates to false, terminating the loop.

0

1

2

3 → printed to console


Nested for loops

A nested loop is a loop inside another loop.

A nested for loop consists of an outer for loop and one or more inner for loops

Each time the outer for loop repeats, the control re-enters inside the inner for loop and starts a new execution.

const rows = [1, 2, 3];

const columns = ["A", "B", "C"];

for (let x = 0; x < rows.length; x++) { → outer loop

for (let y = 0; y < columns.length; y++) { → inner loop

console.log(`row ${rows[x]} : column ${columns[y]}`);

}

}

returns ↴

row 1 : column A

row 1 : column B

row 1 : column C

row 2 : column A

row 2 : column B

row 2 : column C

row 3 : column A

row 3 : column B

row 3 : column C → printed to console

Generate a multiplication table.

for (let x = 1; x <= 12; x++) { → outer loop

let row = "";

for (let y = 1; y <= 10; y++) { → inner loop

row += (x * y) + "\t";

}

console.log(row);

}

returns ↴

1  2  3  4  5  6  7  8  9  10

2  4  6  8  10 12 14 16 18 20

3  6  9  12 15 18 21 24 27 30

4  8  12 16 20 24 28 32 36 40

5  10 15 20 25 30 35 40 45 50

6  12 18 24 30 36 42 48 54 60

7  14 21 28 35 42 49 56 63 70

8  16 24 32 40 48 56 64 72 80

9  18 27 36 45 54 63 72 81 90

10 20 30 40 50 60 70 80 90 100

11 22 33 44 55 66 77 88 99 110

12 24 36 48 60 72 84 96 108 120 → printed to console

rows ⇣ outer loop

columns ⇢ inner loop

The outer loop iterates through the rows ⇣ 1 to 12

The inner loop iterates through the columns ⇢ 1 to 10.


Initialize an array to sort.

const array1 = [8, 4, 6, 2]; → user input


Define a function selectionSort() to sort an array.

function selectionSort(arr) {}

The function takes an array as input arr and returns the array sorted in ascending order, using the Selection Sort algorithm.

The original array will be updated.

Selection Sort is a comparison-based sorting algorithm that divides the input list into two parts: a sorted and an unsorted region.

The algorithm iteratively selects the smallest element from the unsorted region and moves it to the end of the sorted region.

Outer loop to iterate through each element in arr input array.

for (let x = 0; x < arr.length-1; x++) {}

Assume the first unsorted element is the minimum.

let = x minIndex

Inner loop to find the index of the minimum element in the unsorted section.

for (let y = x + 1; y < arr.length; y++)

If a smaller element is found, update minIndex

if (arr[y] < arr[minIndex]) {}

Update minIndex if a smaller element is found.

minIndex = y

Swap the found minimum element with the first unsorted element.

Store the minimum element.

let temp = arr[minIndex] temp

Place the first unsorted element arr[x] in minIndex

arr[minIndex] = arr[x]

Place the minimum element temp in the original position.

arr[x] = temp

Return the sorted array.

return arr


Call the function with ↴

selectionSort(array1);


In each iteration, the algorithm searches through the unsorted portion to find the minimum element.

Once the minimum element is found, it is swapped with the first element of the unsorted portion.

This effectively grows the sorted portion of the array.

Sort an array using the Selection Sort algorithm.

[10, 4, 8, 2, 6] → unsorted array

Iteration ↴

0 [10, 4, 8, 2, 6] [2, 4, 8, 10, 6] swap

1 [2, 4, 8, 10, 6] [2, 4, 8, 10, 6] no swap

2 [2, 4, 8, 10, 6] [2, 4, 6, 10, 8] swap

3 [2, 4, 6, 10, 8] [2, 4, 6, 8, 10] swap

[2, 4, 6, 8, 10] → sorted array


Sort an array using the Selection Sort algorithm.

const array1 = [10, 4, 8, 2, 6];

function selectionSort(arr) {

for (let x = 0; x < arr.length-1; x++) {

let minIndex = x;

for (let y = x + 1; y < arr.length; y++) {

if (arr[y] < arr[minIndex]) {

minIndex = y;

}

}

let temp = arr[minIndex];

arr[minIndex] = arr[x];

arr[x] = temp;

}

return arr;

}

call function

selectionSort(array1); returns ↴

[2, 4, 6, 8, 10];


To sort a mixed numeric alphanumeric array ↴

Separate the strings and numbers into different arrays, sort them individually, and then merge them back together.

const arr1 = [1, 2, 3]; sorted numbers

const arr2 = ["a", "b", "c"]; sorted strings

const arr3 = [...arr1, ...arr2]; merge

console.log(arr3); returns ↴

[1, 2, 3, "a", "b", "c"]


Alternatives to sort order of array.

Change the comparison test ↴

arr[y] < arr[minIndex] ⇡ ascending order

arr[y] > arr[minIndex] ⇣ descending order


Alternative to swap 2 array elements using destructuring

const arr4 = [2, 4];

[arr4[0], arr4[1]] = [arr4[1], arr4[0]];

returns [4, 2] → elements swapped

Sort an array