# Bubble-sorting a vector

Sunday, Jan 19, 2020
JavaScript Algorithms

As I explained in an earlier note that binary search is much faster than linear search, but to use binary search the array has to be sorted first. Well, here I jump into learning to sort an array. I'll start with the simplest one to understand - bubble sort and move to more interesting ones later.

The idea behind bubble sort is pretty simple. You start by comparing first and second numbers and swap if these are not sorted. Then move to comparing second and third and swap if those are not sorted. Continue this until the end of the vector. Repeat the above process until no further swaps happen in that pass. Then return the vector.

Here's how it looks in the pseudocode:

function BubbleSort(v)
length = LENGTH(v)
for (0 < i < length - 1)
count = 0
for (0 < j < length - 1)
if (v[j + 1] < v[j] )
swap(v[j + 1], v[j])
count = 1
if (count == 0)
return v

function swap(v, i, j)
tmp = v[i]
v[i] = v[j]
v[j] = tmp
return v


And here is the JavaScript implementation. I also used Math.round to generate a random array for testing.


function swap(array, index1, index2)
{
var x = array[index2];
array[index2] = array[index1]
array[index1] = x;
return array;

}

function BubbleSort(array)
{
var len = array.length;
for (var i = 0; i < len - 1; i++)
{
var count = 0;
for (var j = 0; j < len - 1; j++)
{
if (array[j + 1] < array[j])
{
swap(array, j, j+1);
count++;
}
}
if (count == 0)     // break out of loop if no swap is done
{
break;
}
}
return array;

}



## Let's test it

function genRandomArray(n)
{
var arr = [];
for (var i = 0; i < n; i++)
{
arr[i] = Math.round(100 * Math.random());
}
return arr;
}
var array = genRandomArray(8);
console.log("unsorted array:")
console.log(array);
console.log("sorted array:")
console.log(BubbleSort(array));

unsorted array:
[
75,  4, 28, 96,
80, 79, 91, 99
]
sorted array:
[
4, 28, 75, 79,
80, 91, 96, 99
]


## What I don't know (yet)

1. A way to check performance of bubble sort and compare with built-in JavaScript array methods for sorting.
2. I know that merge sort is much faster than bubble sort. So it would be cool to learn, implement and compare its performance with bubble sort.