Today after two posts [#1, #2] in the past days here’s something that shows again the JavaScript power. This is not a complete example, but it’s good to start.

var str = '/text/1/text/2/';
var a = str.match(/(\d+)/gi);
console.log(a);

in that example you’ll get an array with all the numbers in the string ["1", "2"] – yet another flexible js snippet!

After reviewing a chunk of my code for today I continue to admire the flexibility of JavaScript. It’s really powerful. In that example you can get a string split it by a given symbol to an array and than get the Nth element of it. All this on one line! Amazing!

var str = 'my-long-string';
str.split('-')[0]; // will contain "my"

the 1st and 2nd indexes contain respectively “long” and “string”!

JavaScript Objects

As you may know there are different notations of objects in JavaScript, and there are slight differences. However here I’m gonna achieve the same thing with different notations. The first one is the object notation in JavaScript known mostly from JSON. There you’ve to construct a key/value pairs, divided by a colon:

var class1 = {
    a : 0,
    func1 : function() {
        console.log(class1.a);
    },
    func2 : function(a) {
        this.a = a;
    }
}
class1.func2(3);

Here we have two functions – func1 and func2 and one member variable. Func2 is setting up the member variable, it’s something like a setter in some languages like Java and PHP, and the func1 is printing the value of that variable via console.log(). Note that in the body of func1() the variable “a” is accessed with the class name: class1.a. Here the notation can be changed to this.a, which will result in the same thing.

...
console.log(this.a);
...

Notation #2

While in the notation I’ve just used is not possible to have two different instances from the same class, in the next example this is possible. In JavaScript the objects are even the functions, and you can access the function’s private variables with the dot notation.

var class2 = function() {
    this.a = 0;
    this.func1 = function() {
        console.log(this.a);
    }
 
    this.func2 = function(a) {
        this.a = a;
    }
}

To use this object you’ve to use the “new” operator.

var c = new class2();
c.func2(4);

This helps you create more than one instance of the same class.

var c = new class2();
var d = new class2();
c.func2(3);
d.func2(4);

Algorithms and Data Structures

Instead of writing about “pure” algorithms this time I’ve decided to write about data structures and to start with a stack implementation in JavaScript. However algorithms and data structures live together since the very beginning of the computer sciences. Another reason to write about data structures is that many algorithms need a specific data structure to be implemented. Most of the search algorithms are data structure dependent. You know that searching into a tree is different from searching into a linked list.

I’d like to write more about searching in my future algorithm posts, but first we need some data structure examples. The first one is, as I mentioned – stack.

Implemented in JavaScript this is really a simple example, which don’t need much to be understood. But in first place what is a stack?

You can thing of the “computer science” stack as a stack of sheets of paper, as it’s shown on the picture. You’ve three basic operations. You can add new element to the stack by putting it on the top of the stack, so the previous top of the stack becomes the second element in the stack. Another operation is to “pop” from the stack – remove the “first” element in the stack – the top most element, and to return it. And finally print the stack. This is difficult to define as an operation, but let say you’ve to show somehow every element from the stack.

Here’s a little diagram:

Source Code

At the end some source code:

var node = function()
{
    var data;
    var next = null;
}
 
var stack = function()
{
    this.top = null;
 
    this.push = function(data) {
        if (this.top == null) {
            this.top = new node();
            this.top.data = data;
        } else {
            var temp = new node();
            temp.data = data;
            temp.next = this.top;
            this.top = temp;
        }
    }
 
    this.pop = function() {
        var temp = this.top;
        var data = this.top.data;
        this.top = this.top.next;
        temp = null;
        return data;
    }
 
    this.print = function() {
        var node = this.top;
        while (node != null) {
            console.log(node.data);
            node = node.next;
        }
    }
}
 
var s = new stack();
 
s.push(1);
s.push(2);
s.push(3);
 
s.print();
 
var a = s.pop();
 
s.print();

Bubble Sort

This is one of the most slowest algorithms for sorting, but it’s extremely well known because of its easy to implement nature. However as I wrote past Fridays there are lots of sorting algorithms which are really fast, like the quicksort or mergesort. In the case of bubble sort the nature of the algorithm is described in its name. The smaller element goes to the top (beginning) of the array as a bubble goes to the top of the water.

There is a cool animation showing how bubble sort works in compare to the quick sort and you can practically see how slow is bubble sort because of all the comparing.

QuickSort vs. BubbleSort

Pseudo Code

Actually what I’d like to show you is how you can move from pseudo code to code in practice. Here’s the pseudo code from Wikipedia.

procedure bubbleSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length(A) - 2 inclusive do:
      if A[i] > A[i+1] then
        swap( A[i], A[i+1] )
        swapped := true
      end if
    end for
  while swapped
end procedure

JavaScript Source

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];
 
function bubbleSort(a)
{
    var swapped;
    do {
        swapped = false;
        for (var i=0; i < a.length-1; i++) {
            if (a[i] > a[i+1]) {
                var temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
}
 
bubbleSort(a);
console.log(a);

As a result you’ve a sorted array!