.. _Sorting1:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Sorting1";ODSA.SETTINGS.MODULE_LONG_NAME = "Sorting Part 1";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/InsertionSortWorstCaseCON.css

.. odsalink:: AV/Sorting/InsertionSortBestCaseCON.css

.. odsalink:: AV/Sorting/InsertionSortAverageCaseCON.css

.. odsalink:: AV/Sorting/BubbleSortAnalysisCON.css

.. odsalink:: AV/Sorting/SelectionSortAnalysisCON.css

.. odsalink:: AV/Sorting/ExchangeSortCON.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 Part 1
==============

Sorting Part 1
--------------

Sorting
~~~~~~~
   * Each record contains a field called the key.
      * Linear order: comparison.

   * Measures of cost:
      * Comparisons
      * Swaps

Insertion Sort
~~~~~~~~~~~~~~
   What would you do if you have a stack of phone bills from the past
   two years and you want to order by date?
   A fairly natural way to handle this is to look at the first two
   bills and put them in order.
   Then take the third bill and put it into the right position with
   respect to the first two, and so on.


Initial Step
~~~~~~~~~~~~ 
   Consider this start to the process.

   .. inlineav:: insertionsortCON ss
      :long_name: Insertion Sort Slideshow
      :output: show
            

Analysis: Worst Case
~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: InsertionSortWorstCaseCON ss
      :long_name: Insertion Sort Worst Case Slideshow
      :output: show


Analysis: Best Case
~~~~~~~~~~~~~~~~~~~
   .. inlineav:: InsertionSortBestCaseCON ss
      :long_name: Insertion Sort Best Case Slideshow
      :output: show


Analysis: Average Case
~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: InsertionSortAverageCaseCON ss
      :long_name: Insertion Sort Average Case Slideshow
      :output: show


Bubble Sort
~~~~~~~~~~~
   .. inlineav:: bubblesortS1CON ss
      :long_name: Bubble Sort Slideshow 1
      :output: show

   .. inlineav:: bubblesortS2CON ss
      :long_name: Bubble Sort Slideshow 2
      :output: show


Analysis
~~~~~~~~
   .. inlineav:: BubbleSortAnalysisCON ss
      :long_name: Bubble Sort Analysis Slideshow
      :output: show


Selection Sort
~~~~~~~~~~~~~~
   .. inlineav:: selectionsortS1CON ss
      :long_name: Selection Sort Slideshow 1
      :output: show

   .. inlineav:: selectionsortS2CON ss
      :long_name: Selection Sort Slideshow 2
      :output: show


Analysis
~~~~~~~~
   .. inlineav:: SelectionSortAnalysisCON ss
      :long_name: Selection Sort Analysis Slideshow
      :output: show


Summary
~~~~~~~
   .. math::

      \begin{array}{rccc}
      &\textbf{Insertion}&\textbf{Bubble}&\textbf{Selection}\\
      \textbf{Comparisons:}\\
      \textrm{Best Case}&\Theta(n)&\Theta(n^2)&\Theta(n^2)\\
      \textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\
      \textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\
      \\
      \textbf{Swaps:}\\
      \textrm{Best Case}&0&0&\Theta(n)\\
      \textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\
      \textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\
      \end{array}

Code Tuning (1)
~~~~~~~~~~~~~~~
   * General strategy: Test to avoid work
      * Balance test cost, success probability, work saved

   * "Optimizations" for quadratic sorts:
      * Insertion Sort shift vs swaps: Works
      * Selection Sort viewed as an optimization of Bubble Sort: Works
      * Selection Sort avoid self-swaps: Does not work
      * Bubble Sort "i" vs "1": Works
      * Bubble Sort count comparisions/avoid unnecessary iterations:
        Does not work
      * Bubble Sort O(n) best case claim (Wikipedia): Bogus

Exchange Sorting
~~~~~~~~~~~~~~~~
   * All of the sorts so far rely on exchanges of adjacent records: Inversions

   .. inlineav:: ExchangeSortCON ss
      :long_name: Exchange Sort Analysis Slideshow
      :output: show

.. odsascript:: AV/Sorting/insertionsortCON.js
.. odsascript:: AV/Sorting/InsertionSortWorstCaseCON.js
.. odsascript:: AV/Sorting/InsertionSortBestCaseCON.js
.. odsascript:: AV/Sorting/InsertionSortAverageCaseCON.js
.. odsascript:: AV/Sorting/bubblesortS1CON.js
.. odsascript:: AV/Sorting/bubblesortS2CON.js
.. odsascript:: AV/Sorting/BubbleSortAnalysisCON.js
.. odsascript:: AV/Sorting/selectionsortS1CON.js
.. odsascript:: AV/Sorting/selectionsortS2CON.js
.. odsascript:: AV/Sorting/SelectionSortAnalysisCON.js
.. odsascript:: AV/Sorting/ExchangeSortCON.js