******************
Topic 14 - 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

   *  Below an example of the process:

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

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

*  We can do a very quick implementation:

.. code-block:: cpp
    :linenos:

    template <typename Comparable>
    void insertionSort( vector<Comparable> & a )
    {
        for(int p = 1; p < a.size( ); ++p)
        {
            Comparable tmp = a[p];

            int j;
            for(j = p; j > 0 && tmp < a[j-1]; --j)
            {
                a[j] = a[ j - 1 ];
            }
            a[j] = tmp;
        }
    }

.. admonition:: Activity
    :class: warning

    *  Apply this code to the previous example.


STL Implementation
------------------

*  The STL library is not using a vector.
*  It is using a pair of iterator, which represents the start and the end of a range.

.. code-block:: cpp

    /*
    * The two-parameter version calls the three-parameter version,
    * using C++11 decltype
    */
    template <typename Iterator>
    void insertionSort( const Iterator & begin, const Iterator & end )
    {
        insertionSort( begin, end, less<decltype(*begin)>{ } );
    }

    template <typename Iterator, typename Comparator>
    void insertionSort( const Iterator & begin, const Iterator & end, Comparator lessThan )
    {
        if( begin == end )
            return;
        
        Iterator j;
        
        for( Iterator p = begin+1; p != end; ++p )
        {
            auto tmp = std::move( *p );
            for( j = p; j != begin && lessThan( tmp, *( j-1 ) ); --j )
                *j = std::move( *(j-1) );
            *j = std::move( tmp );
        }
    }

*  As you can see it is the same algorithm, but more general.


Analysis
--------

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

.. admonition:: Activity
    :class: warning

    *  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 :doc:`binary heap <topic10b>`.

*  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: warning

    *  What is the running time?

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

.. admonition:: Activity
    :class: warning

    *  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)`.