Search

Shellsort

Shellsort is an unstable comparison sort algorithm with poor performance. Shellsort uses the insertion method and performs at O(n(log(n))) in the best case, and at O(n(log(n))2) in the average and worst case.

Table of contents

Performance

Best
Ω(n log(n))
Average
Θ(n (log(n))2)
Worst
O(n (log(n))2)

Code

public static void main(String[] args)
{
    int[] array = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    shellSort(array);
    System.out.println(java.util.Arrays.toString(array));
}

static void shellSort(int[] array)
{
    /*
     * for-loop setup:
     *      1. set the gapSize to the length of the arrray / 2
     *      2. run the loop as long as gapSize > 0
     */
    for (int gapSize = array.length / 2; gapSize > 0; gapSize /= 2)
    {
        for (int currentIndex = gapSize; currentIndex < array.length; currentIndex++)
        {
            // save the currentIndex
            int currentIndexCopy = currentIndex;
            // save the value of the currentIndex
            int item = array[currentIndex];

            while (currentIndexCopy >= gapSize && array[currentIndexCopy - gapSize] > item)
            {
                array[currentIndexCopy] = array[currentIndexCopy - gapSize];
                currentIndexCopy -= gapSize;
            }

            array[currentIndexCopy] = item;
        }
    }
}
public class ShellsortGeneric<T extends Comparable<? super T>> {
    public static void main(String[] args)
    {
        // example using Strings
        String[]                 arrayOfStrings  = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", "Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
        ShellsortGeneric<String> stringShellsort = new ShellsortGeneric<>();
        stringShellsort.shellsort(arrayOfStrings);
        System.out.println(java.util.Arrays.toString(arrayOfStrings));

        // example using Doubles
        Double[]                 arrayOfDoubles  = {0.35, 0.02, 0.36, 0.82, 0.27, 0.49, 0.41, 0.17, 0.30, 0.89, 0.37, 0.66, 0.82, 0.17, 0.20, 0.96, 0.18, 0.25, 0.37, 0.52};
        ShellsortGeneric<Double> doubleShellsort = new ShellsortGeneric<>();
        doubleShellsort.shellsort(arrayOfDoubles);
        System.out.println(java.util.Arrays.toString(arrayOfDoubles));
    }

    void shellsort(T[] array)
    {
        /*
         * for-loop setup:
         *      1. set the gapSize to the length of the array / 2
         *      2. run the loop as long as gapSize > 0
         */
        for (int gapSize = array.length / 2; gapSize > 0; gapSize /= 2)
        {
            for (int currentIndex = gapSize; currentIndex < array.length; currentIndex++)
            {
                // save the currentIndex
                int currentIndexCopy = currentIndex;
                // save the value of the currentIndex
                T item = array[currentIndex];
                while (currentIndexCopy >= gapSize && array[currentIndexCopy - gapSize].compareTo(item) > 0)
                {
                    array[currentIndexCopy] = array[currentIndexCopy - gapSize];
                    currentIndexCopy -= gapSize;
                }
                array[currentIndexCopy] = item;
            }
        }
    }
}
#include <iostream>
#include <vector>

void shellSort(std::vector<int> &arr) {
    /*
     * for-loop setup:
     *      1. set the gapSize to the size of the array / 2
     *      2. run the loop as long as gapSize > 0
     */
    for (int gapSize = arr.size() / 2; gapSize > 0; gapSize /= 2) {
        for (int currentIndex = gapSize; currentIndex < arr.size(); currentIndex++) {
            // save the currentIndex
            int currentIndexCopy = currentIndex;
            // save the value of the currentIndex
            int item = arr[currentIndex];

            while (currentIndexCopy >= gapSize && arr[currentIndexCopy - gapSize] > item) {
                arr[currentIndexCopy] = arr[currentIndexCopy - gapSize];
                currentIndexCopy -= gapSize;
            }

            arr[currentIndexCopy] = item;
        }
    }
}

int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    shellSort(arr);
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}
func shellSort(array: inout [Int])
{
    /*
     * for-loop setup:
     *      1. set the gapSize to the length of the arrray / 2
     *      2. run the loop as long as gapSize > 0
     */
    for (int gapSize = array.length / 2; gapSize > 0; gapSize /= 2)
    {
        for (int currentIndex = gapSize; currentIndex < array.length; currentIndex++)
        {
            // save the currentIndex
            int currentIndexCopy = currentIndex;
            // save the value of the currentIndex
            int item = array[currentIndex];

            while (currentIndexCopy >= gapSize && array[currentIndexCopy - gapSize] > item)
            {
                array[currentIndexCopy] = array[currentIndexCopy - gapSize];
                currentIndexCopy -= gapSize;
            }

            array[currentIndexCopy] = item;
        }
    }
}

var array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
shellsort(array: &array)
print(array)
function shellSort(array) {
  /*
   * for-loop setup:
   *      1. set the gapSize to the length of the array / 2
   *      2. run the loop as long as gapSize > 0
   */
  for (let gapSize = Math.floor(array.length / 2); gapSize > 0; gapSize = Math.floor(gapSize / 2)) {
    for (let currentIndex = gapSize; currentIndex < array.length; currentIndex++) {

      // save the currentIndex
      let currentIndexCopy = currentIndex
      // save the value of the currentIndex
      let itemValue = array[currentIndex]

      while (currentIndexCopy >= gapSize && array[currentIndexCopy - gapSize] > itemValue) {
        array[currentIndexCopy] = array[currentIndexCopy - gapSize]
        currentIndexCopy -= gapSize
      }

      array[currentIndexCopy] = itemValue
    }
  }
}

let array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
shellSort(array)
alert(array)

Discussion