*******
Sorting
*******

*  Sorting is not a data structure.
*  Data structures and sorting algorithms are linked.
*  In this topic we will make some assumptions:

   *  Each algorithm is interchangeable.
   *  Each will receive an array of elements.
   *  Each array positions contain data to be sorted.
   *  The arrays are of size :math:`N`.
   *  Each element of the array have the operators :math:`<,>,==` implemented.

Insertion Sort
==============

*  **Insertion Sort** is one of the simplest sorting algorithms.

Algorithm
---------

The idea:

*  Works in :math:`N-1` passes.
*  For pass :math:`p=1` through :math:`N-1`:

   *  Move :math:`p` to the right to have the elements from 0 to :math:`p` sorted.
   *  Based on the fact that elements from 0 to :math:`p-1` are already sorted.

.. admonition:: Example
   :class: example

   *  Below an example of the process:

   .. figure:: ./img/insertion_sort.png
       :align: center

Implementation
--------------

*  We can do a very quick implementation:

.. literalinclude:: ./InsertionSort.java
   :language: java
   :linenos:
   :lines: 3-38

.. admonition:: Activity
    :class: activity

    *  Apply this code to the previous example.



Analysis
--------

*  Now we will calculate the running time of this algorithm.

.. admonition:: Activity
    :class: activity

    *  What is the Big Oh running time of Insertion sort?

*  We can calculate the precise running time.

   *  The number of tests in the inner loop is at most :math:`p+1` for each :math:`p`.
   *  It sums to : :math:`\sum_{i=2}^{N}i=2+3+4+\dots + N = \Theta(N^2)`

Heapsort
========

*  The algorithm is based on binary heap.

*  The idea:

   *  We build a binary heap of :math:`N` elements.
   *  Then, we perform :math:`N` delete operations.
   *  We put these elements in another array.

*  Building the heap takes :math:`O(N)` time.
*  Each delete takes :math:`O(\log N)` time.


.. admonition:: Activity
    :class: activity

    *  What is the running time?

*  The only downside is that it double the memory used.

.. admonition:: Activity
    :class: activity

    *  Sort the following array: :code:`[31,41,59,26,53,58,97]`.
    *  Show each step.

Analysis
--------

*  Building the heap uses less than :math:`2N` comparisons.
*  The :math:`i` th delete uses at most less :math:`2\lfloor \log (N-i+1) \rfloor` comparisons.
*  For a total of :math:`2N\log N - O(N)` if :math:`N\geq 2` comparisons.
*  This is why we have :math:`O(N\log N)`.