Testing Merge Sort with Jasmine

Posted: October 19, 2013 | Author: Carlos | Filed under: Algorithms, JavaScript |Comments Off on Testing Merge Sort with Jasmine

When designing algorithms you are looking to get the correct results in the least number of steps possible.  The running time of an algorithm is part of the analysis of any algorithm.  A key question in this analysis is:  When your data set grows what happens to the run time of your solution? For that reason I am running my algorithm class homework solutions through test runners and I’ll post them here.

A few observations during this process :

• It’s generally better to run these tests on the command line.  Making a test suite run within a blog post has its challenges.
• You’re probably more interested in the results than in me figuring out how to do this within the confines of a blog post.
• Hence, in future posts I will probably post the code for a Node JS set-up and not for the browser.
• I used Jasmine JS which is very nice and easy to use and it does provide test results.  However, I did make the mistake of running a failing spec on a 100k entry array which yielded 100k errors and crashed my browser!
• I used a 100k array for the run time to be observable.  To make my life easier I will run several tests off the browser and instead post a chart of the results.
• I was curious to see how long it takes to sort a large array in the browser.  Why did I want to see this happen? I don’t know.

The Merge Sort code is here (in my previous post).

In order to run the algorithm on this page I decided to load a file with random entries.  The code for the load uses the jQuery Ajax function.  It’s very straightforward to set up.  In the txt file, each line is a new entry.  Hence, the success function creates an array by doing a split on the regexp: /\n|\r\n|\r/ which is just matching a new line.  Each entry is then forced to be an integer.

	$.ajax({
        type: "GET",
        url: "./jslib/IntegerArray.txt",
        dataType: "text",
        success: function (data) {

        	var array = data.split(/\r\n|\r|\n/);
        	for(var i =0; i<array.length; i++) {
        		array[i] = parseInt(array[i]);
        	}
        	A = array.slice(0);

        }

    }).done(function(){ 
    	console.log("loaded"); 
    	runSpec();
    });

 

When the load is complete, the runSpec function is called.  This is the test suite for Jasmine.  I run four tests:

1. Make sure the length of the array is 100k
2. Call Merge Sort and make sure every item in the array is in ascending order.
3. Call JavaScript sort and make sure every item in the array is in ascending order.
4. Verify that the native (JavaScript) sort if faster.

The test suite is below:

describe("Load file",function(){

			it("Should split into array correctly", function(){

				expect(A.length).toBe(100000);

			});

		});

		describe("Items should be sorted", function(){
			it("It is sorted if all items are in ascending order", function(){
				mst = new Date();
				M = splitArray(A);
				met = new Date();
				for (var n=0; n<M.length-1; n++) {
					expect(M[n]).toBeLessThan(M[n+1]);
				}
			});
		});

		describe("JavaScript Sort", function(){
			it("It is sorted if all items are in ascending order", function(){
				nst = new Date();
				X = A.sort(function(a,b) { return a-b; });
				net = new Date();
				for (var n=0; n<X.length-1; n++) {
					expect(X[n]).toBeLessThan(X[n+1]);
				}
			});
		});

		describe("Native vs Merge Sort", function () {
			it("Native sort should be quicker", function(){

				expect(net-nst).toBeLessThan(met-mst);

			});
		});

All those tests are run on this post.  So keep scrolling down to see the Jasmine Spec runner test output!

Run time Summary:

---