Sorting algorithms Pt1. Shellsort

Now I’m learning sorting algorithms with JavaScript so I wrote about the results and my thoughts on it. In this blog post, I picked up “Shellsort” for the part 1.

About Shellsort

Shellsort is a variation of insertion sort. This sorting algorithm is devised by Donald L. Shell in 1959. That’s why the sorting algorithm is called “Shellsort”. It’s sometimes called “diminishing increment sort” as well. It improves on the insertion sort by breaking the original list into a number of smaller sublists. Each sublist is sorted using the insertion sort.

Well, I’ll explain about the flow of Shellsort.

Firstly, sublists are created. The shell sort uses a “gap” h, sometimes called the “increment”. The sublist is made by choosing all items that are h items apart. Then, each sublist is sorted by the insertion sort, which is called h-sorted.

Although this list is not completely sorted, by h-sorted, the items have been moved closer to where these items actually belong. It means a whole list can become partially sorted.

Next, the value of h is reduced and then sublists are created, then these sublists are sorted. In Shellsort, we have to repeat this cycle until h becomes 1. Finally, when h is 1, the list is sorted by using this normal insertion sort.

Why Shellsort is better than insertion sort?

It is said that the insertion sort is generally effective in “roughly sorted” list (items), which means the list is not completely sorted but sorted to some extent. The insertion sort moves elements only one position ahead. When an element has to be moved far ahead, many movements are involved. That’s why the sorting speed is slow. The Shellsort allows the swap of items located far away. In the Sellsort, when the value of h become 1, the list can be roughly sorted. It means the sorting speed is faster.

Pseudocode

Before starting actual code, here’s a Pseudocode.

class ShellSort {
  constructor(array) {
    //set an array
  }

  //h-sorted
  sort(h) {
    //Start with a big gap, then reduce the gap
    //Set a gap with a value of h 
    // Do an insertion sort for this gap size (h) until h is greater than 0
    // The first elements array[0...h-1] are already in order
    // Keep adding one more element until the entire array is sorted

      // Add array[i] to the elements that have been sorted
      // Save array[i] in temp
        // tmp = array[i]

      // Shift earlier sorted elements up until the correct
      // location for array[i] is found

        // Put temp (the original array[i]) in its correct location
          // array[i] = tmp

    // Return sorted array
  }
}

Full code

Here is a full code:

class ShellSort {
  constructor(array) {
    this.array = array;
  }

  sort(h) {
    let gap = h;

    while (gap > 0){
      for (let i = 0; i < this.array.length; i += 1){
        let unsortedIndex = i;

        let tmp = this.array[i];
        while ((unsortedIndex >= gap) && (this.array[unsortedIndex - gap] > tmp)){
          this.array[unsortedIndex] = this.array[unsortedIndex - gap];
          unsortedIndex = unsortedIndex - gap;
        }
        this.array[unsortedIndex] = tmp;
      }

      if (Math.floor(gap/2) !== 0) {
        gap = Math.floor(gap/2);
      } else if (gap === 1) {
        gap = 0;
      } else {
        gap = 1;
      }
    }
    return this.array;
  }
}

Resources

• https://www.geeksforgeeks.org/shellsort/
• http://interactivepython.org/runestone/static/pythonds/SortSearch/TheShellSort.html
• https://en.wikipedia.org/wiki/Shellsort