.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer

==============
Sorting Part 3
==============



Binsort
-------

.. codeinclude:: Sorting/Binsort
   :tag: simplebinsort

.. inlineav:: binsortS1CON ss
   :long_name: Binsort Slideshow 1
   :links: 
   :scripts: AV/Sorting/binsortS1CON.js
   :output: show


Radix Sort: Linked List
-----------------------

.. revealjs-slide::

.. avembed:: AV/Sorting/radixLinkAV.html ss


Radix Sort: Array
-----------------

.. revealjs-slide::

.. avembed:: AV/Sorting/radixArrayAV.html ss


Radix Sort Implementation
-------------------------

.. revealjs-slide::

.. codeinclude:: Sorting/Radixsort
   :tag: Radixsort


Radix Sort Analysis
-------------------

.. revealjs-slide::

.. inlineav:: RadixSortAnalysisCON ss
   :long_name: Radix Sort Analysis Slideshow
   :links: AV/Sorting/RadixSortAnalysisCON.css
   :scripts: AV/Sorting/RadixSortAnalysisCON.js
   :output: show


Empirical Analysis
------------------

.. revealjs-slide::

.. math::

   \begin{array}{l|rrrrrrrr}
   \hline
   \textbf{Sort} & \textbf{10}& \textbf{100} & \textbf{1K}&
   \textbf{10K} & \textbf{100K}& \textbf{1M}& \textbf{Up} & \textbf{Down}\\
   \hline
   \textrm{Insertion} & .00023 & .007 & 0.66 &  64.98 &  7381.0 &  674420 & 0.04 & 129.05\\
   \textrm{Bubble}    & .00035 & .020 & 2.25 & 277.94 & 27691.0 & 2820680 &  70.64 & 108.69\\
   \textrm{Selection} & .00039 & .012 & 0.69 &  72.47 &  7356.0 &  780000 &  69.76 &  69.58\\
   \textrm{Shell}     & .00034 & .008 & 0.14 &   1.99 &    30.2 &     554 &   0.44 &   0.79\\
   \textrm{Shell/O}   & .00034 & .008 & 0.12 &   1.91 &    29.0 &     530 &   0.36 &   0.64\\
   \textrm{Merge}     & .00050 & .010 & 0.12 &   1.61 &    19.3 &     219 &   0.83 &   0.79\\
   \textrm{Merge/O}   & .00024 & .007 & 0.10 &   1.31 &    17.2 &     197 &   0.47 &   0.66\\
   \textrm{Quick}     & .00048 & .008 & 0.11 &   1.37 &    15.7 &     162 &   0.37 &   0.40\\
   \textrm{Quick/O}   & .00031 & .006 & 0.09 &   1.14 &    13.6 &     143 &   0.32 &   0.36\\
   \textrm{Heap}      & .00050 & .011 & 0.16 &   2.08 &    26.7 &     391 &   1.57 &   1.56\\
   \textrm{Heap/O}    & .00033 & .007 & 0.11 &   1.61 &    20.8 &     334 &   1.01 &   1.04\\
   \textrm{Radix/4}   & .00838 & .081 & 0.79 &   7.99 &    79.9 &     808 &   7.97 &   7.97\\
   \textrm{Radix/8}   & .00799 & .044 & 0.40 &   3.99 &    40.0 &     404 &   4.00 &   3.99\\
   \hline
   \end{array}


Sorting Lower Bound (1)
-----------------------

.. revealjs-slide::

* We would like to know a lower bound for the problem of sorting

* Sorting is :math:`O(n \log n)` (average, worst cases) because we know of
  algorithms with this upper bound.

* Sorting I/O takes :math:`\Omega(n)` time. You have to look at all records
  to tell if the list is sorted.

* We will now prove :math:`\Omega(n log n)` lower bound for sorting.


Sorting Lower Bound (2)
-----------------------

.. revealjs-slide::

.. inlineav:: SortingLowerBoundCON ss
   :long_name: Sorting Lower Bound
   :links: AV/Sorting/SortingLowerBoundCON.css
   :scripts: AV/Sorting/SortingLowerBoundCON.js
   :output: show