In Bubble Sort, we

]]>Bubble sort is one of the least efficient sorting algorithms but it is also the simplest to understand. This post covers the essentials of bubble sort using JavaScript. We will use a simple array to demonstrate the concepts of Bubble Sort before getting into code.

In Bubble Sort, we start from the first element in the array and compare this with the adjacent element in the array. If the first element is greater than the second, we swap their positions. If not, we compare the second element with the third element and so on. At the end of Pass 1, we will have the highest number at the last position of the array. Following images demonstrate Pass 1 of bubble sort.

Compare the first element with second element of the array. If the element is larger, swap the positions. In this case, number 4 is greater than 3. We should swap the positions.

Compare second element with third element. This time, 4 < 5. We will not swap the numbers.

Again, 5 > 1. So, we swap the positions.

Here 5 < 7. Don’t swap the numbers

7 > 6. Swap 6 and 7.

7 < 8. Don’t swap

8 > 2. Swap the numbers.

After swapping the numbers, Number 8 (Largest number in the array) is positioned at the end of the array. This completes Pass 1 of bubble sort as below:

Pass 1

Once we have completed Pass 1, we repeat the compare and swap step starting from the first element of the array but till the second last element of the array. We don’t compare the last element as we know that the last element is already the largest after completion of Pass 1.

Pass 2

At the end of Pass 2, we will have the second largest number at second last position of the array.

In Pass 3, we will start comparing the numbers starting at first position till the third last position of the array (Pass 1 and Pass 2 has already completed)

Pass 3

Similarly:

Pass 4

Pass 5

and so on.

Finally, after all the passes, we will have a sorted array as follows:

Sorted Array

Let’s calculate the complexity involved in Bubble Sort algorithm using Big-O notation.

For an array of size N, it requires N steps to complete Pass 1 but it requires N-1 steps to complete Pass 2 as we don’t traverse last element. Similarly, we need N-2 steps for Pass 3 and so on.

Total number of steps required to sort an array using bubble sort is:

N + (N-1) + (N-2) + … ≈ (N * (N-1)) / 2 (sum of N natural numbers)

For N → ∞ :

Number of steps ≈ N².

Implementing Bubble Sort is very straight-forward once the concept is clear. Following function takes an array as argument and sort the content using bubble sort.

```
function bubbleSort(items) {
var length = items.length;
for (var i = 0; i < length; i++) { //Number of passes
for (var j = 0; j < (length - i - 1); j++) { //Notice that j < (length - i)
//Compare the adjacent positions
if (items[j] > items[j + 1]) {
//Swap the numbers
var tmp = items[j]; //Temporary variable to hold the current number
items[j] = items[j + 1]; //Replace current number with adjacent number
items[j + 1] = tmp; //Replace adjacent number with current number
}
}
}
}
```

Another form of bubble sort includes starting at the end of the array and placing the smallest element first and going till the largest. So, at the end of Pass 1, smallest number will be placed at the first position. Following JavaScript code illustrates this.

```
function bubbleSort(items) {
var length = items.length;
for (var i = (length - 1); i >= 0; i--) {
//Number of passes
for (var j = (length - i); j > 0; j--) {
//Compare the adjacent positions
if (items[j] < items[j - 1]) {
//Swap the numbers
var tmp = items[j];
items[j] = items[j - 1];
items[j - 1] = tmp;
}
}
}
}
```

You would not use Bubble Sort for sorting an array in your day to day code. Instead, use `items.sort()`

from the JavaScript inbuilt Array method. The aim of this post was to illustrate the Bubble Sort Technique. Even though bubble sort is most inefficient, it is still the most common sorting algorithm because of its simplicity.

- Write a program in JavaScript to sort following list in ascending order using Bubble Sort Algorithm.var nums = [34, 23, 12, 45, 9, 1, 24];
- Sort the list present in Q1 in descending order.
- Sort the following array of Persons in ascending order of ‘age’ using Bubble Sort.

```
var persons = [
{
"name": "john",
"age": "23"
},
{
"name": "harry",
"age": "21"
},
{
"name": "jack",
"age": "25"
}
];
```

]]>In selection sort, we start by assuming that

]]>This post covers the essentials of selection sort using javascript. Selection Sort is a low-efficiency sorting algorithms but is easy to implement and understand. We will use a simple array to demonstrate the concepts of Selection Sort before getting into code.

In selection sort, we start by assuming that the first number in the array is the minimum. We then find out the smallest number in the array and if there is any number smaller than the first number, we exchange the numbers after one pass through the array. After this, the number in first position is smallest and array is sorted till position 1.

Next, we assume that the number at second position is the smallest in the remainder of the array. We pass through the array comparing each number with this number. After the pass is complete, we exchange this number with the smallest number in the remainder of the array. At the end of this, we will have first and second number in the array in sorted order. We repeat this step for rest of the numbers until all the numbers are sorted.

Let’s understand this using the images below:

We assume that the number at first position is the smallest number. We compare this number with the number at position 2.

Since 2 < 3, 2 is still the minimum number.

Compare the current minimum with the next number in the array. Still, 2 < 5. Current minimum remain as 2.

This time, 2 > 1, so we change the minimum number position to be 3 (index for number 1) as:

Now that we have a new number which is smallest, we will use this number for comparing with the rest of the array elements. Our aim is to find the smallest number in the array.

Since 1 < 4, 1 is the smallest number in the array. We exchange the initial minimum number (number at first position) with the smallest number (i.e 1) as follows:

This completes Pass 1 of sorting the array and at the end of Pass 1, we have the smallest number in the array at first position. Next, we need to find the smallest number in remainder of the array and exchange that with the number in the second position. We again assume that the number at position 2 is the smallest number and repeat the steps 1 to 5 above. At the end of Pass 2, we will have:

Pass 2

Similarly, after pass 3:

Pass 3

Pass 4

Finally, after all the passes, we will have the sorted array as follows:

Pass 5

Complexity of Selection Sort: O(N²)

Implementing Selection Sort is very straight-forward once the concept is clear. Following function takes an array as argument and sort the content using selection sort.

```
function selectionSort(items) {
var length = items.length;
for (var i = 0; i < length - 1; i++) {
//Number of passes
var min = i; //min holds the current minimum number position for each pass; i holds the Initial min number
for (var j = i + 1; j < length; j++) { //Note that j = i + 1 as we only need to go through unsorted array
if (items[j] < items[min]) { //Compare the numbers
min = j; //Change the current min number position if a smaller num is found
}
}
if (min != i) {
//After each pass, if the current min num != initial min num, exchange the position.
//Swap the numbers
var tmp = items[i];
items[i] = items[min];
items[min] = tmp;
}
}
}
```

You would not use selection Sort for sorting an array in your day to day code. Instead, use `items.sort()`

from the JavaScript inbuilt Array method. The aim of this post was to illustrate the Selection Sort Technique.

- Write a program in JavaScript to sort following list in ascending order using Selection Sort Algorithm.var nums = [34, 23, 12, 45, 9, 1, 24];
- Sort the list present in Q1 in descending order.
- Sort the following array of Persons in ascending order of ‘age’ using Selection Sort.var persons = [{"name": "john","age": "23"},{"name": "harry","age": "21"},{"name": "jack","age": "25"}];

In insertion sort, we divide the initial unsorted array into two parts; sorted part and unsorted part. Initially the sorted part just

]]>This post covers the essentials of insertion sort using JavaScript. We will use a simple array to demonstrate the concepts of Insertion Sort before getting into code.

In insertion sort, we divide the initial unsorted array into two parts; sorted part and unsorted part. Initially the sorted part just has one element (Array of only 1 element is a sorted array). We then pick up element one by one from unsorted part; insert into the sorted part at the correct position and expand sorted part one element at a time.

Let’s see this using illustration below:

Number 5 is in sorted part of the array. We need to pick up the first number in unsorted part, i.e 3, and insert it into the sorted part at correct position. We make a copy of number 3 and compare this copy with the numbers in the sorted part starting at the last element in the sorted part, in this case, 5.

Since 5 > 3, we expand the sorted part by replacing number 3 in the unsorted part by 5. Next, we insert the number 3 (using the copy we stored earlier) at the previous position of 5. Now, the sorted part has expanded to 2 elements while unsorted part is reduced to 3 elements.

We pick the next number in the unsorted part, number 1. Again, we make a copy of this number and compare it with numbers in sorted part one by one.

Since 5 > 1, we expand the sorted part by replacing number 1 in the unsorted part by 5. We compare the copy of number 1 with the next element in sorted array, 3.

Since 3 > 1, we need to shift 3 to next position in the sorted part. We replace the number 5 at the second position with number 3. Since there are no more numbers, we insert copy of number 1 at 1st position.

Repeating the same process with number 2, we expand the sorted part and shift numbers 3 and 5:

Next, we compare number 2 with number 1. This time, 1 < 2. So, we need to insert the number 2 after number 1. We replace the number 3 at the second position with number 2.

Similarly:

Best CaseAverageWorst CaseO(n)O(n²)O(n²)## Insertion Sort in Javascript

Implementation of Insertion Sort:

```
function insertionSort(unsortedList) {
var len = unsortedList.length;
for (var i = 1; i < len; i++) {
var tmp = unsortedList[i]; //Copy of the current element.
/*Check through the sorted part and compare with the number in tmp. If large, shift the number*/
for (var j = i - 1; j >= 0 && (unsortedList[j] > tmp); j--) {
//Shift the number
unsortedList[j + 1] = unsortedList[j];
}
//Insert the copied number at the correct position
//in sorted part.
unsortedList[j + 1] = tmp;
}
}
var ul = [5, 3, 1, 2, 4];
insertionSort(ul);
console.log(ul);
```

- Write a program in JavaScript to sort following list in ascending order using Insertion Sort Algorithm.var nums = [34, 23, 12, 45, 9, 1, 24];
- Sort the list present in Q1 in descending order.
- Sort the following array of Persons in ascending order of ‘age’ using Insertion Sort.var persons = [{"name": "john","age": "23"},{"name": "harry","age": "21"},{"name": "jack","age": "25"}];

Install the following modules:

`npm install`

Install the following modules:

`npm install -g request https-proxy-agent`

In case you are connecting to an `http://`

endpoint, you could install:

`npm install -g http-proxy-agent`

Then:

```
var HttpsProxyAgent = require('https-proxy-agent');
var request = require('request');
var proxy = 'http://127.0.0.1:3128';
var agent = new HttpsProxyAgent(proxy);
request({
uri: "https://example.com/api",
method: "POST",
headers: {
'content-type': 'application/x-www-form-urlencoded'
},
agent: agent,
timeout: 10000,
followRedirect: true,
maxRedirects: 10,
body: "name=john"
}, function(error, response, body) {
console.log("Error" + error);
console.log("Response: " + response);
console.log("Body: " + body);
});
```

```
var https = require('https');
var HttpsProxyAgent = require('https-proxy-agent');
var proxy = 'http://127.0.0.1:3128';
var agent = new HttpsProxyAgent(proxy);
var post_req = https.request({
host: 'example.com',
port: '443',
path: '/api',
method: 'POST',
headers: {
'Content-Type': 'application/x-www-form-urlencoded'
},
agent: agent,
timeout: 10000,
followRedirect: true,
maxRedirects: 10
}, function(res) {
res.setEncoding('utf8');
res.on('data', function(chunk) {
console.log('Response: ' + chunk);
});
});
post_req.write("name=john");
post_req.end();
```

https://nodejs.org/api/https.html

http://blog.vanamco.com/proxy-requests-in-node-js/ (Custom implementation of HttpsProxyAgent)

]]>