.. _Sorting2:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Sorting2";ODSA.SETTINGS.MODULE_LONG_NAME = "Sorting: Faster Sorts";ODSA.SETTINGS.MODULE_CHAPTER = "Sorting"; ODSA.SETTINGS.BUILD_DATE = "2020-08-23 13:21:52"; ODSA.SETTINGS.BUILD_CMAP = false;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/Sorting/QuickSortPartitionAnalysisCON.css

.. odsalink:: AV/Sorting/QuickSortWorstCaseCON.css

.. odsalink:: AV/Sorting/QuickSortBestCaseCON.css

.. odsalink:: AV/Sorting/QuickSortAverageCaseCON.css

.. odsalink:: AV/Sorting/HeapSortAnalysisCON.css
.. 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: Faster Sorts
=====================

Faster Sorts
------------

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

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