current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

I'm trying to learn basic algorithms which are typically taught in an introduction to CS course, which is usually taught in a compiled language like Java. However, I want to focus on JavaScript, so I wrote the algorithms in JavaScript and encapsulated them into a library.

I'm looking for feedback on the efficiency of my implementations (bubbleSort, selectionSort, insertionSort):

/***************************************************************************************************
**ALGORITHMS
***************************************************************************************************/

(function () {
    "use strict";
    var $A,
        $P = {};

    (function manageGlobal() {
        if (window.$A && window.$A.pack) {
            $A = window.$A;
            $A.pack.algo = true;
        }
    }());

    $P.swap = function (arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    };

    // checks to see if sorted
    $P.isSorted = function (arr) {
        var index_outer,
            length = arr.length;
        for (index_outer = 1; index_outer < length; index_outer++) {
            if (arr[index_outer - 1] > arr[index_outer]) {
                return false;
            }
        }
        return true;
    };

    // repeatedly orders two items ( a bubble ) at a time
    $P.bubbleSort = function (arr) {
        var index_outer,
            index_inner,
            swapped = false,
            length = arr.length;
        for (index_outer = 0; index_outer < length; index_outer++) {
            swapped = false;
            for (index_inner = 0; index_inner < length - index_outer; index_inner++) {
                if (arr[index_inner] > arr[index_inner + 1]) {
                    $P.swap(arr, index_inner, index_inner + 1);
                    swapped = true;
                }
            }
            if (swapped === false) {
                break;
            }
        }
        return arr;
    };

    // repeatedly finds minimum and places it the next index
    $P.selectionSort = function (arr) {
        var index_outer,
            index_inner,
            index_min,
            length = arr.length;
        for (index_outer = 0; index_outer < length; index_outer++) {
            index_min = index_outer;
            for (index_inner = index_outer + 1; index_inner < length; index_inner++) {
                if (arr[index_inner] < arr[index_min]) {
                    index_min = index_inner;
                }
            }
            if (index_outer !== index_min) {
                $P.swap(arr, index_outer, index_min);
            }
        }
        return arr;
    };

    // repeatedly places next item in correct spot using a "shift"
    $P.insertionSort = function (arr) {
        var index_outer,
            index_inner,
            value,
            length = arr.length;
        for (index_outer = 0; index_outer < length; index_outer++) {
            value = arr[index_outer];
            for (index_inner = index_outer - 1; (index_inner >= 0 && (arr[index_inner] > value));
                    index_inner--) {
                arr[index_inner + 1] = arr[index_inner];
            }
            arr[index_inner + 1] = value;
        }
        return arr;
    };

    // module complete, release to outer scope
    $A = $A.extendSafe($A, $P);
}());
share|improve this question
    
new version here - codereview.stackexchange.com/questions/39619/… –  anon Jan 19 '14 at 23:51
2  
This one comment linking to the new version is sufficient. Adding the same comment to every answer is a bit spammy IMHO. –  David Harkness Jan 20 '14 at 0:07

4 Answers 4

up vote 3 down vote

Note that isSorted has a bit of an off-by-one error. It will check outside the bounds of its argument. This actually works OK, because it compares the last element of the array to undefined which always results in false. However, you should really only check up to index_outer < length - 1.

I haven't looked too closely at your implementations of the basic sorting algorithms, but assuming they are correct, then there isn't much that could be said about their efficiency that hasn't already. It's all well defined.

share|improve this answer
    
Well, but when index_outer is 0 make sure you're not checking arr[0] > arr[-1]. Either way, you need to adjust the bounds. –  lwburk Jan 5 '14 at 20:39
    
I'm confused? Are you suggesting that subtracting one from length a single time is going to hurt performance? I hope you're not suggesting that. Even taking that into consideration, it's better to be correct than anything else. (Although, by the way, I like your update.) –  lwburk Jan 6 '14 at 15:24
up vote 3 down vote

From a style perspective:

  • Naming variables with $ is discouraged unless those variables are jQuery search results
  • $A and $P are too crypticically named
  • lowerCamelCase is encouraged for variables ( index_outer -> indexOuter which frankly should probably be called outerIndex )
  • Your 2nd for loop in insertionSort is too convoluted, you are doing too much
  • if( swapped === false ) is more readable as if(!swapped)
share|improve this answer
    
Depends on the browser, jsperf.com/falsey, on FF 28 (!swapped) would be fastest. –  konijn Jan 6 '14 at 13:59
up vote 2 down vote

Your implementations look mostly correct besides a couple things.

As mentioned by @Iwburk, your isSorted function will always return false because arr[index_outer + 1] will always be undefined for the last element. You should either iterate arr backwards starting at the last (I'd recommend this way) element or end the loop at index_outer === length -1

$P.isSorted = function (arr) {
    for (var index_outer = arr.length; index_outer >= 1; index_outer--) {
        if (arr[index_outer - 1] > arr[index_outer]) {
            return false;
        }
    }
    return true;
};

In your insertion sort algorithm you can get away without checking index_inner >= 0 which will reduce your total comparisons; one of your goals when designing sorting algorithms.

$P.insertionSort = function (arr) {
    var index_outer,
        index_inner,
        value,
        length = arr.length;
    for (index_outer = 0; index_outer < length; index_outer++) {
        value = arr[index_outer];
        for (index_inner = index_outer - 1; arr[index_inner] > value; index_inner--) {
            arr[index_inner + 1] = arr[index_inner];
        }
        arr[index_inner + 1] = value;
    }
    return arr;
};
share|improve this answer
    
Note that his original implementation of isSorted actually works because the final comparison does not invalidate the check that determines if the items are out of order. I still think it needs to be fixed. Right now it's just working accidentally because of a quirk in the language. –  lwburk Jan 6 '14 at 4:47
up vote 2 down vote

I would like to add some points, however those already mentioned are all valid. You get +1 for encapsulating your code in a function and using 'use strict';. However you should rather return your 'library' than populate it into the global namespace. This way you can later use dependency injection, which is especially important and common in the JavaScript world.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.