A package for sort algorithms

Question

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);
}());

• anon: new version here - codereview.stackexchange.com/questions/39619/…
• David Harkness: This one comment linking to the new version is sufficient. Adding the same comment to every answer is a bit spammy IMHO.

Answer 1

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.

• Wayne: 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.
• Wayne: 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.)

Answer 2

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)

• konijn: Depends on the browser, jsperf.com/falsey, on FF 28 (!swapped) would be fastest.

Answer 3

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;
};

• Wayne: 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.

Answer 4

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.