I don't often start an article asking a question, but I'll make an exception today. Can you take the following array [8,3,1,9,6,5,7,2,4] and sort it in ascending order? Fairly easy right? Many programming languages provide sorting functions that make tasks such as this a one liner.
Sometimes it's easy to overlook the implementation details of such a function until you're asked to write your own, which brings me to my next question. Can you sort an array in ascending order without using builtin sort functions?
In this article I'll cover three of the simplest sorting algorithms and how to implement them in JavaScript.
The Bubble Sort algorithm is the simplest to understand and implement. The algorithm works by iterating through a collection and comparing adjacent elements. If the first element is greater than the second element then the two elements are swapped. The next iteration compares the second element with the third element and so on until the iteration is complete. The example below will help demonstrate this better. Consider the following array.
Compare the first element with the second element. 8 is greater than 3. Swap elements.
Compare the second element with the third element. 8 is greater than 1. Swap elements.
Compare the third element with the fourth element. 8 is less than 9. Do not swap elements.
The final result after the first iteration is 3, 1, 8, 9. As you can see, the array is still not sorted. This means another iteration cycle is required until the array if finally sorted. Depending on the size of the array and how the elements are positioned, the Bubble Sort algorithm can take many iteration cycles to sort an array. The following code sample below demonstrates a simple Bubble Sort algorithm.
The Selection Sort algorithm is based on finding the minimum/maximum element in an array and moving it to the start/end position of an array depending on the sort direction. Assume that we want to sort an array in ascending order. The algorithm will first find the smallest value in the array and swap it with the element at the beginning of the array. The next iteration will find the smallest value between the second element and the end of the array. When the smallest value between this range is found, the two elements are once again swapped. This process continues until the array is finally sorted. This algorithm is considered more efficient than the Bubble Sort algorithm because it does not iterate over elements that have been sorted. This means that the search to find the smallest value becomes shorter for each iteration. Let's take a look at a simple example.
First we iterate over the entire collection to find the smallest value. Once found, it is swapped with the element at the beginning of the array. In this case, 1 is the smallest value. After the first iteration, the array now looks like the following.
The next iteration starts at the second element position and continues to the end of the array looking for the smallest value. Once found the two elements are swapped.
Although the array is now sorted, the algorithm will continue to iterate over the remaining array elements. The following code sample below demonstrates a simple Selection Sort algorithm.
The Insertion Sort algorithm sorts an array by shifting and inserting elements at the correct position. The principle is similar to how you would organize a set of cards. Assume you are given a series of random playing cards one at a time. Every time you take a card, you insert it at the correct position by scanning the cards you are holding. When a card is inserted, the positions of the surrounding cards are also affected. The following code sample below demonstrates a simple Insertion Sort algorithm.
Listing 1
console.log([8,3,1,9,6,5,7,2,4].sort());
Sometimes it's easy to overlook the implementation details of such a function until you're asked to write your own, which brings me to my next question. Can you sort an array in ascending order without using builtin sort functions?
In this article I'll cover three of the simplest sorting algorithms and how to implement them in JavaScript.
Bubble Sort
The Bubble Sort algorithm is the simplest to understand and implement. The algorithm works by iterating through a collection and comparing adjacent elements. If the first element is greater than the second element then the two elements are swapped. The next iteration compares the second element with the third element and so on until the iteration is complete. The example below will help demonstrate this better. Consider the following array.
8, 3, 1, 9
Compare the first element with the second element. 8 is greater than 3. Swap elements.
3, 8, 1, 9
Compare the second element with the third element. 8 is greater than 1. Swap elements.
3, 1, 8, 9
Compare the third element with the fourth element. 8 is less than 9. Do not swap elements.
3, 1, 8, 9
The final result after the first iteration is 3, 1, 8, 9. As you can see, the array is still not sorted. This means another iteration cycle is required until the array if finally sorted. Depending on the size of the array and how the elements are positioned, the Bubble Sort algorithm can take many iteration cycles to sort an array. The following code sample below demonstrates a simple Bubble Sort algorithm.
Listing 2
function bubbleSort(array){
let swapped = true;
while(swapped){
swapped = false;
for(let i = 0; i < array.length; i++){
let v1 = array[i];
let v2 = array[i+1];
if(v1 > v2){
array[i] = v2;
array[i+1] = v1;
swapped = true;
}
}
}
return array;
}
Selection Sort
The Selection Sort algorithm is based on finding the minimum/maximum element in an array and moving it to the start/end position of an array depending on the sort direction. Assume that we want to sort an array in ascending order. The algorithm will first find the smallest value in the array and swap it with the element at the beginning of the array. The next iteration will find the smallest value between the second element and the end of the array. When the smallest value between this range is found, the two elements are once again swapped. This process continues until the array is finally sorted. This algorithm is considered more efficient than the Bubble Sort algorithm because it does not iterate over elements that have been sorted. This means that the search to find the smallest value becomes shorter for each iteration. Let's take a look at a simple example.
8, 9, 1, 3
First we iterate over the entire collection to find the smallest value. Once found, it is swapped with the element at the beginning of the array. In this case, 1 is the smallest value. After the first iteration, the array now looks like the following.
1, 9, 8, 3
The next iteration starts at the second element position and continues to the end of the array looking for the smallest value. Once found the two elements are swapped.
1, 3, 8, 9
Although the array is now sorted, the algorithm will continue to iterate over the remaining array elements. The following code sample below demonstrates a simple Selection Sort algorithm.
Listing 3
function selectionSort(array){
for(let i = 0; i < array.length; i++){
let minimum = i;
for(let j = (i + 1); j < array.length; j++){
if(array[j] < array[minimum]){
minimum = j;
}
}
let v1 = array[i];
let v2 = array[minimum];
array[i] = v2;
array[minimum] = v1;
}
return array;
}
Insertion Sort
The Insertion Sort algorithm sorts an array by shifting and inserting elements at the correct position. The principle is similar to how you would organize a set of cards. Assume you are given a series of random playing cards one at a time. Every time you take a card, you insert it at the correct position by scanning the cards you are holding. When a card is inserted, the positions of the surrounding cards are also affected. The following code sample below demonstrates a simple Insertion Sort algorithm.
Listing 4
function insertionSort(array){
for(let i = 1; i < array.length; i++){
let j = i - 1;
let current = array[i];
while(j >=0 && array[j] > current){
array[j+1] = array[j];
j--;
}
array[j+1] = current;
}
return array;
}
Node.js Articles
-
A JavaScript Implementation Of The Logo Programming Language - Part 2
Part 2 of A Javascript Implementation Of The Logo Programming Language. In the previous article I explained how to develop a simple lexer. In this part we develop a TokenCollection class to help traverse the array of tokens returned from the lexer.
10 June 2020 - 2803 views -
A JavaScript Implementation Of The Logo Programming Language - Part 1
In this four part article, I explain how to develop the iconic Logo programming language in JavaScript. In this part, we discuss how to take a source input and convert it into a series of tokens.
06 June 2020 - 5063 views -
Generating Web API Keys
If you're building a REST API, chances are you're going to need to generate secure random API keys. In this article, I explain how to use the Node.js crypto module to generate random secure API keys.
29 May 2020 - 7734 views -
Port Scanner
A simple port scanner to scan a range of ports.
31 January 2020 - 3563 views -
Simple Http Server
This article explains how to create a simple HTTP server using Node.js without using any dependencies.
04 September 2019 - 2287 views -
Reading From Console
Node.Js provides several ways to read user input from the terminal. This article explains how to use the process object to read user input.
16 July 2019 - 2873 views -
Difference Between const, let And var
This article explains the difference between const, let and var.
12 July 2019 - 2022 views