{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation of Shell Sort\n",
    "\n",
    "The shell sort improves on the insertion sort by breaking the original list into a number of smaller sublists, each of which is sorted using an insertion sort. The unique way that these sublists are chosen is the key to the shell sort. Instead of breaking the list into sublists of contiguous items, the shell sort uses an increment i, sometimes called the gap, to create a sublist by choosing all items that are i items apart."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Resources for Review\n",
    "\n",
    "Check out the resources below for a review of Shell sort!\n",
    "\n",
    "* [Wikipedia](https://en.wikipedia.org/wiki/Shellsort)\n",
    "* [Visual Algo](http://visualgo.net/sorting.html)\n",
    "* [Sorting Algorithms Animcation with Pseudocode](http://www.sorting-algorithms.com/shell-sort)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def shell_sort(arr):\n",
    "    sublistcount = len(arr)/2\n",
    "    \n",
    "    # While we still have sub lists\n",
    "    while sublistcount > 0:\n",
    "        for start in range(sublistcount):\n",
    "            # Use a gap insertion\n",
    "            gap_insertion_sort(arr,start,sublistcount)\n",
    "\n",
    "      \n",
    "\n",
    "        sublistcount = sublistcount / 2\n",
    "\n",
    "def gap_insertion_sort(arr,start,gap):\n",
    "    for i in range(start+gap,len(arr),gap):\n",
    "\n",
    "        currentvalue = arr[i]\n",
    "        position = i\n",
    "\n",
    "        # Using the Gap\n",
    "        while position>=gap and arr[position-gap]>currentvalue:\n",
    "            arr[position]=arr[position-gap]\n",
    "            position = position-gap\n",
    "        \n",
    "        # Set current value\n",
    "        arr[position]=currentvalue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 4, 6, 7, 21, 23, 24, 45, 45, 67, 90]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [45,67,23,45,21,24,7,2,6,4,90]\n",
    "shell_sort(arr)\n",
    "arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}