Elementary sorting algorithm in Javascriptby@jayaprakash

# Elementary sorting algorithm in Javascript

by ashok5mAugust 12th, 2019

In this story we are going to learn about implementing Bubble Sort, Insertion Sort & Selection sort in Javascript. The upper bound worst case complexity for all the three algorithms are Quadratic Time O (n^2) as per Big-0 Notation. There are more advanced sorting algorithms available which will be posted in upcoming stories. In order to visualize the flow of above mentioned algorithms in animation, check out this geeky website by Dr Steven Halim, https://visualgo.net/en/sorting.net/.

### Coin Mentioned

In this story am going to walk through about elementary sorting algorithm and its performance. There many type of sorting algorithm, here we are going to learn about implementing Bubble Sort, Insertion Sort & Selection sort in Javascript.

Bubble Sort

The bubble sort repeatedly traverse all unsorted elements and compare the consecutive elements then interchange each other when they are out of order.

Pseudo Code

``````(A is an array of elements, where N is the length of an array)
FOR I = 0 to N - 2
FOR J = 0 to N - 2
IF A[J] > A[J + 1]
TEMP = A[J]
A[J] = A[J + 1]
A[J + 1] = A[J]
END-FOR
END-FOR``````

Implementation

``````function bubbleSort(a) {
const n = a.length;
// Iteration of array till last before element
for (let i = 0; i < (n - 2); i++) {
// Iteration of array till last before element
for (j = 0; j < (n - 2); j++) {
if (a[j] > a[j + 1]) {
//Swap the consecutive elements
let temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
return a;
}

const input = [5, 4, 2, 6, 7];
const result = bubbleSort(input);
// Expected Output: [ 2, 4, 5, 6, 7 ]``````

The given program will result the sorted array in ascending order. For example when the given input is [5,4,2,6,7] it will return output array as [2,4,5,6,7]

Insertion Sort

Traverse all elements in an array and insert each element within a sorted array.

Pseudo Code

``````(A is an array of elements, where N is the length of an array)
FOR I = 0 to N - 1
J = 1
WHILE J > 0 AND A[J] < A[J - 1]
TEMP = A[J]
A[J] = A[J - 1]
A[J - 1] = TEMP
END-WHILE
END-FOR``````

Implementation

``````function insertionSort(a) {
const n = a.length;
// Iteration of array till last element
for (i = 0; i < n; i++) {
let j = i;
// Iterate over the sorted part of array and insert the element
while (j >= 0 && a[j] < a[j - 1]) {
let temp = a[j];
a[j] = a[j - 1]
a[j - 1] = temp;
j--;
}
}
return a;
}``````

Selection Sort

Traverse all elements in an array and find the smallest element in unsorted array and swap it with the first element

Pseudo Code

``````(A is an array of elements, where N is the length of an array)
For I = 0 to N-1 do:
leastElementIndex = I
For J = I + 1 to N-1 do:
If A(J) < A(leastElementIndex)
leastElementIndex = J
End-If
End-For
Temp = A(I)
A(I) = A(leastElementIndex)
A(leastElementIndex) = Temp
End-For``````

Implementation

``````function selectionSort(a) {
const n = a.length;
// Iteration of array till last element
for (let i = 0; i < (n - 1); i++) {
let leastElementIndex = i;
for (let j = i + 1; j < (a.length - i); j++) {
// Check for least element and override least element index
if (a[j] < a[leastElementIndex]) {
leastElementIndex = j;
}
}
// Swap elements
let temp = a[i];
a[i] = a[leastElementIndex];
a[leastElementIndex] = temp;
}
return a;
}
selectionSort([5, 4, 2, 6, 7])
// Output : [ 2, 4, 5, 6, 7 ]``````

Algorithm Time Complexity Analysis

All the above mentioned sorting algorithms are inefficient algorithms, there are more advanced sorting algorithms available which will be posted in upcoming stories. The upper bound worst case complexity for all the three algorithms are Quadratic Time O (n^2) as per Big-0 Notation.

Visualization

In order to visualize the flow of above mentioned algorithms in animation, check out this geeky website by Dr Steven Halim, https://visualgo.net/en/sorting. It has visualization collection of many data structures and algorithms

Reference

https://users.csc.calpoly.edu/~jdalbey/SWE/pdl_std.html

L O A D I N G
. . . comments & more!