.. _Sorting2:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Sorting2";ODSA.SETTINGS.MODULE_LONG_NAME = "Sorting Part 2";ODSA.SETTINGS.MODULE_CHAPTER = "Slides"; ODSA.SETTINGS.BUILD_DATE = "2019-04-01 22:21:50"; ODSA.SETTINGS.BUILD_CMAP = true;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:



.. odsalink:: AV/Sorting/quicksortCON.css

.. odsalink:: AV/Development/QuickSortPartitionAnalysisCON.css

.. odsalink:: AV/Development/QuickSortWorstCaseCON.css

.. odsalink:: AV/Development/QuickSortBestCaseCON.css

.. odsalink:: AV/Development/QuickSortAverageCaseCON.css

.. odsalink:: AV/Development/HeapSortAnalysisCON.css

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

.. avmetadata::
   :author: Cliff Shaffer


==============
Sorting Part 2
==============

Sorting Part 2
--------------

Shellsort
~~~~~~~~~
   .. avembed:: AV/Sorting/shellsortAV.html ss
      :module: Sorting2


Shellsort (2)
~~~~~~~~~~~~~
   .. codeinclude:: Sorting/Shellsort
      :tag: Shellsort


Mergesort
~~~~~~~~~
   .. avembed:: AV/Sorting/mergesortAV.html ss
      :module: Sorting2


Mergesort cost
~~~~~~~~~~~~~~
   * Mergesort cost:

   * Mergsort is also good for sorting linked lists.

   * Mergesort requires twice the space.


Quicksort
~~~~~~~~~
   .. codeinclude:: Sorting/Quicksort
      :tag: Quicksort

   .. codeinclude:: Sorting/Quicksort
      :tag: findpivot


Quicksort Partition
~~~~~~~~~~~~~~~~~~~
   .. inlineav:: quicksortCON ss
      :long_name: Quicksort Partition Slideshow
      :output: show


Quicksort Partition Cost
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: QuickSortPartitionAnalysisCON ss
      :long_name: Quicksort Partition Analysis Slideshow
      :output: show


Quicksort Summary
~~~~~~~~~~~~~~~~~
   .. avembed:: AV/Sorting/quicksortAV.html ss
      :module: Sorting2


Quicksort Worst Case
~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: QuickSortWorstCaseCON ss
      :long_name: Quicksort Worst Case Analysis Slideshow
      :output: show


.
~
   .

Quicksort Best Case
~~~~~~~~~~~~~~~~~~~
   .. inlineav:: QuickSortBestCaseCON ss
      :long_name: Quicksort Best Case Analysis Slideshow
      :output: show


.
~
   .

Quicksort Average Case
~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: QuickSortAverageCaseCON ss
      :long_name: Quicksort Average Case Analysis Slideshow
      :output: show


Optimizations for Quicksort
~~~~~~~~~~~~~~~~~~~~~~~~~~~
   * Better Pivot
   * Inline instead of function calls
   * Eliminate recursion
   * Better algorithm for small sublists: Insertion sort
      * Best: Don't sort small lists at all, do a final Insertion Sort to
        clean up.


Heapsort
~~~~~~~~
   .. inlineav:: heapsortCON ss
      :long_name: Heapsort Slideshow
      :output: show


Heapsort Analysis
~~~~~~~~~~~~~~~~~
   .. inlineav:: HeapSortAnalysisCON ss
      :long_name: Heapsort Analysis Slideshow
      :output: show


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

   .. inlineav:: binsortS1CON ss
      :long_name: Binsort Slideshow 1
      :output: show


Radix Sort: Linked List
~~~~~~~~~~~~~~~~~~~~~~~
   .. avembed:: AV/Sorting/radixLinkAV.html ss
      :module: Sorting2


.
~
   .


Radix Sort: Array
~~~~~~~~~~~~~~~~~
   .. avembed:: AV/Sorting/radixArrayAV.html ss
      :module: Sorting2


Radix Sort Implementation
~~~~~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Sorting/Radixsort
      :tag: Radixsort


.
~
   .

Radix Sort Analysis
~~~~~~~~~~~~~~~~~~~
   .. inlineav:: RadixSortAnalysisCON ss
      :long_name: Radix Sort Analysis Slideshow
      :output: show


Empirical Analysis
~~~~~~~~~~~~~~~~~~
   .. 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)
~~~~~~~~~~~~~~~~~~~~~~~
   * 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)
~~~~~~~~~~~~~~~~~~~~~~~
   .. avembed:: AV/Development/SortingLowerBound.html ss
      :module: Sorting2

.. odsascript:: AV/Sorting/quicksortCODE.js
.. odsascript:: AV/Sorting/quicksortCON.js
.. odsascript:: AV/Development/QuickSortPartitionAnalysisCON.js
.. odsascript:: AV/Development/QuickSortWorstCaseCON.js
.. odsascript:: AV/Development/QuickSortBestCaseCON.js
.. odsascript:: AV/Development/QuickSortAverageCaseCON.js
.. odsascript:: DataStructures/binaryheap.js
.. odsascript:: AV/Sorting/heapsortCON.js
.. odsascript:: AV/Development/HeapSortAnalysisCON.js
.. odsascript:: AV/Sorting/binsortS1CON.js
.. odsascript:: AV/Development/RadixSortAnalysisCON.js