Sathish's Blog

June 21, 2011

Queue in JavaScript

Queue is an ADT (Abstract Data Type), which has the basic operations like enque/dequeue. Enqueue operation will insert an item to the queue. Dequeue will return the first inserted element. The constructor will accept max size for the queue. On overflow both enqueue & dequeue will return false.

function Queue(max){

this.max = max;

}

Queue.prototype = (function(){

var queue = [];

return {

enqueue: function(item){

if(queue.length == this.max){

return false;

}

queue.push(item);

dequeue: function(){

if(queue.length == 0){

return false;

}

return queue.shift();

isEmpty:function(){

return queue.length == 0;

}

)();

Stack in JavaScript

Stack is an ADT (Abstract Data Type), which has basic operations like push and pop. Push will insert a new item to the stack. If the stack is empty then it'll initialize it. Pop operation will remove the last inserted item and returns it. The simple implementation of stack in JavaScript is here (Using JavaScript array which already has push & pop implementation).

function Stack(max){
this.max = max;
}
Stack.prototype = (function(){
var stack = [];
return {
push: function(item){
if(stack.length == this.max){
//Stack overflow.
return false;
}
stack.push(item);
},

pop: function(){

if(stack.length == 0){

return false;//Stack is empty.

}

return stack.pop();

isEmpty:function(){

return stack.length == 0;

}

}
}
)();

Merge sort in JavaScript

Merge sort follows the divide and conquer approach to sort the given list. The important step in this sorting approach is the merging step.

function merge(lo, m, hi) {
var i, j, k;
i=0; j=lo;
// copy first half of array a to auxiliary array b
while (j<=m)
b[i++] = a[j++];

i=0; k=lo;
// copy back next-greatest element at each time
while (k<j && j<=hi)
if (b[i]<=a[j])
a[k++]=b[i++];
else
a[k++]=a[j++];

// copy back remaining elements of first half (if any)
while (k<j)
a[k++]=b[i++];
}

Here is the function to sort the array.

function mergesort(lo, hi) {
if (lo<hi) {
var m=(lo+hi)/2;
mergesort(lo, m);
mergesort(m+1, hi);
merge(lo, m, hi);
}
}

June 15, 2011

Insertion sort in JavaScript

Insertion sort is efficient algorithm to sort the substantially sorted data set.

function insertionSort(numbers){ // numbers is an array which has to be sorted.

var max = numbers.length, i, j, temp;

for(i=0; i< max; i++) {

temp = numbers[i];

j = i-1;

while(temp < numbers[j] && j >= 0) {

numbers[j+1] = numbers[j];

j--;

}

numbers[j+1] = temp;

}

Selection sort in JavaScript

Selection sort is one of the simplest sorting algorithm which is inefficient for the larger set of data.

function selectionSort(numbers){ // numbers is an array which has to be sorted.

var iMin, iMax; max = numbers.length, iPos, j, temp;

for(iPos=0; iPos< max; i++) {

iMin = i;

for(j=iPos+1; iPos < max; i++){

if(numbers[iPos] > numbers[iMin]) {

iMin = j;

}

if(iMin != iPos){ // Swap elements between iPos & iMin

temp = numbers[iPos];

numbers[iPos] = numbers[iMin];

numbers[iMin] = temp;

}

June 14, 2011

Bubble sort in JavaScript

Bubble sort is a simple sorting algorithm also known as sinking sort that works by iterating the given array in a nested loop. Here is the sample code for bubble sorting in JavaScript.

function bubbleSort(numbers){

var max = numbers.length, i, j, temp;

for(i=0; i< max; i++) {

for(j=i+1; j < max; j++) {

if(numbers[i] > numbers[j]) {

temp = numbers[i];

numbers[i] = numbers[j];

numbers[j] = temp;

}

DataStructures and Algorithms in JavaScript

If you're a front-end developer and interested in learning data structures and algorithms in JavaScript, then you're in the right place. If you're aware of JavaScript you can know more about it from wiki and step by step JavaScript tutorial. I'll try post articles here frequently.

Basic Data Structures:

Stack
Queue

Sorting: