### Shell Sort

Continuing our sorting algorithm discussion, today’s article will cover a technique known as Shell Sort.

Shell sort is a quadratic (O(n2)) in-place comparison sort algorithm developed by Donald Shell in 1959 that is basically Insertion Sort with a gap between comparing indexes. The assumption is that comparing farther apart elements can move some out-of-place elements into position faster.

### How do it…

The first thing we need is an algorithm to calculate the gaps to evaluate. Here is a simple algorithm that was created by Shell (gaps are an array of values created by `n / 2 ^ k`):

```function createGaps(a) {
// if a is an array of 100, gaps would be [50, 25, 12, 6, 3, 1]
var gaps = [];

for (var i = 0, j = a.length, t; 1 <= (t = Math.floor(j / Math.pow(2, i + 1))); i += 1) {
gaps[i] = t;

if (t === 1) {
break;
}
}

if (gaps[i] !== 1) {
gaps.push(1);
}

return gaps;
}
```

Here is a the shell sort algorithm in JavaScript:

```function shellSort(a) {
var gaps = createGaps(a),
temp;

for (var i = 0, j = gaps.length, gap; i < j; i += 1) {
gap = gaps[i];

for (var x = gap, y = a.length; x < y; x += 1) {
temp = a[x];

// this performs insertion sort on subarrays
for (var z = x; z >= gap && a[z - gap] > temp; z -= gap) {
a[z] = a[z - gap];
}

a[z] = temp;
}
}
}
```

Here it is in action:

Restart Shell Sort With a New Array

If we take a 10,000 element array and sort it, here is how shell sort compares to native array sort (prints to the console):

shell Sort Comparison Tests

### How it works…

The gap algorithm is simple and there are more efficient ones (see the wikipedia article), but I choose it because it was easy to implement and understand. It creates an array of values `n / 2 ^ k`, where `n` is the length of the array and `k` is an incrementing integer. We stop appending to the array when the final value of `1` is reached. The gap algorithm is critical to reducing the number of swaps made by the inner insertion sort.

The shell sort algorithm breaks the array up into sub-arrays and order them. This is a little tricky to understand by looking at the code, so we’ll analyze the first few comparisons made to a 100 value array. The initial gap will be `50`, so we will perform insertion sort on the two element sub-arrays made from the values at 0 and 50, 1 and 51, 2 and 52, etc. (i.e. 50 sub-arrays with two values). The second gap will be `25`, so we perform insertion sort on the four element sub-arrays made from the values at indexes: 0, 25, 50, and 75; 1, 26, 51, and 76; 2, 27, 52, and 77; etc. (i.e. 25 sub-arrays with four values). And so on until we perform a complete insertion sort on all values once (the complete array with all 100 values).

For a random distribution shell sort tends to perform better than other quadratic comparison sorting algorithms, because it moves the values farthest from their final position to that position quicker. However, it will perform worse when the array is sorted already, or the values at each index are near their final position. Additionally, the number of elements in the gap array will affect the performance of this algorithm, so the better the gap the better the performance of shell sort.

### There’s more…

For more information on shell sort and creating shell gaps, see the Shell Sort Wikipedia article.

### Encrypting Settings Files

When I was developing for Votizen, I always felt uneasy that we had our settings files with many important passwords and auth keys stored unencrypted on a third-party service. Sure, SSL was used for fetching and committing code, and only a few SSH public keys were allowed access to our repository, but it is one more opportunity for your site to be hacked. I recently read John Resig’s post Keeping Passwords in Source ...

### Cross Browser and Legacy Supported RequestFrameAnimation

There is an awesome new feature in HTML 5, `window.requestAnimationFrame`, which tells the browser that you wish to perform an animation and requests that the browser schedule a repaint of the window for the next animation frame1. This allows you to do animations more efficiently and without using `setInterval` or series of `setTimeout` function(s). I have created a Demo that attempts to use the browser’s `requestAnimationFrame` side-by-side with the legacy polyfill executing.

### Processing.js Frame Animation Queue

A couple weeks ago, I mentioned that I was using Processing.js to animate a visualization tool for work. Today’s article showcases the class-based strategy we used to handle animation frames. There is a simple Demo available, if you would like to see Processing.js in action.

To start using processing, you will need three things: the latest Processing.js code, a canvas element on an HTML page with the ...

### Django Template Tags for JavaScript Deferment

I have been slowly working to improve my Django Shared project, which I use as the basis for all my Django projects. Recently, I added several new templatetags for deferring content and scripts: `async_script`, `defer_html`, `defer_script`, and `render_deferred_html`. Today’s article will cover how to use these templatetags in your own projects.

You will need to include django-shared in your own project, or extract the parts from `templatetags/common.py`. If you use pip, ...

### Query Parameter Parsing Function

I needed a straight (ie. no framework) JavaScript function for parsing query parameters the other day and found one on stack overflow that I liked. Most functions that lookup query parameters, search the url string each time it performs a key lookup. However, the query parameters never change once your JavaScript code starts to run, so it is inefficient and unnecessary to search the query parameters string on each lookup. The lookup function in ...

### Parsing JavaScript Function Argument Names

Lately, I have been experimenting with various JavaScript MVCs, and I was surprised when AngularJS threw an error, when I changed the argument name in a controller function declaration using a factory resource. The library was obviously doing some magic to parse the names of the arguments of a function and validating it against a previously defined namespace. This was interesting, so I thought I would discover how they were doing it and some possible ...

### Selection Sort

Continuing our sorting algorithm discussion, today’s article will cover a technique known as Selection Sort. Selection sort is a simple, quadratic (O(n2)) in-place comparison sort algorithm that divides the array into two lists: an already sorted part and a to-sort part. The algorithm moves for through the array and inserts the next value in-place by searching the unsorted part of the array for the next value. In practice, the selection sort is useful when memory ...

### Insertion Sort

Continuing our sorting algorithm discussion, today’s article will cover a technique known as Insertion Sort. Insertion sort is a simple, quadratic (O(n2)) sorting algorithm that iterates forward through the array, sorting the current index value in-place by inserting it into the correct position among the values at smaller indices, which were sorted in previous passes. In practice it out performs the other quadratic sorting algorithms, such as bubble sort and selection sort.

### Super Simple Image Viewer V3

I have had several inquiries lately about the Super Simple Image Viewer widget that I built several years back. As it is still being used, I thought I would take a minute to revamp the code and get it into a public version control. If you are unfamiliar with the software, it is a simple JavaScript widget that allows developers to create an image slide show on their site. Here is a list of ...