.. _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 = "Week 7-8"; ODSA.SETTINGS.BUILD_DATE = "2016-11-29 20:59:56"; 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:


.. 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 1
==============

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

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

   * Measures of cost:
      * Comparisons
      * Swaps

Insertion Sort
~~~~~~~~~~~~~~
   .. inlineav:: insertionsortCON ss
      :long_name: Insertion Sort Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Sorting/insertionsortCON.js

Analysis: Worst Case
~~~~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/Sorting/InsertionSortWorstCaseCON.css

   .. inlineav:: InsertionSortWorstCaseCON ss
      :long_name: Insertion Sort Worst Case Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Sorting/InsertionSortWorstCaseCON.js


Analysis: Best Case
~~~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/Sorting/InsertionSortBestCaseCON.css

   .. inlineav:: InsertionSortBestCaseCON ss
      :long_name: Insertion Sort Best Case Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Sorting/InsertionSortBestCaseCON.js


Analysis: Average Case
~~~~~~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/Sorting/InsertionSortAverageCaseCON.css

   .. inlineav:: InsertionSortAverageCaseCON ss
      :long_name: Insertion Sort Average Case Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Sorting/InsertionSortAverageCaseCON.js


Bubble Sort
~~~~~~~~~~~
   .. inlineav:: bubblesortS1CON ss
      :long_name: Bubble Sort Slideshow 1
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. inlineav:: bubblesortS2CON ss
      :long_name: Bubble Sort Slideshow 2
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Sorting/bubblesortS1CON.js
   .. odsascript:: AV/Sorting/bubblesortS2CON.js


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

   .. inlineav:: BubbleSortAnalysisCON ss
      :long_name: Bubble Sort Analysis Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Sorting/BubbleSortAnalysisCON.js


Selection Sort
~~~~~~~~~~~~~~
   .. inlineav:: selectionsortS1CON ss
      :long_name: Selection Sort Slideshow 1
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. inlineav:: selectionsortS2CON ss
      :long_name: Selection Sort Slideshow 2
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Sorting/selectionsortS1CON.js
   .. odsascript:: AV/Sorting/selectionsortS2CON.js


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

   .. inlineav:: SelectionSortAnalysisCON ss
      :long_name: Selection Sort Analysis Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Sorting/SelectionSortAnalysisCON.js


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
~~~~~~~~~~~
   * 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 avoid self-swaps: Does not work
      * Bubble Sort avoid/count comparisions: Does not work

Exchange Sorting
~~~~~~~~~~~~~~~~
   * All of the sorts so far rely on exchanges of adjacent records.
   * Inversions
   * What is the average number of exchanges required?

   .. odsalink:: AV/Sorting/ExchangeSortCON.css

   .. inlineav:: ExchangeSortCON ss
      :long_name: Exchange Sort Analysis Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Sorting/ExchangeSortCON.js