Sans Pareil Technologies, Inc.

Key To Your Business

Lab 6 - Sort Algorithms


In this lab session we will implement the quicksort and merge sort algorithms. We will run the same sequence of tests against both sort algorithms, and will also test with different data types.
Quicksort 
// quicksort.h
#pragma once

#include <iterator>

namespace csc280
{
  namespace internal
  {
    template <typename Iterator, typename Comparator>
    Iterator partition( Iterator first, Iterator last, Comparator comparator )
    {
      auto mid = first;
      auto pivot = *( first++ );
      std::advance( last, -1 );

      while ( first <= last )
      {
        while ( comparator( *first, pivot ) && ( first != last ) ) std::advance( first, 1 );
        while ( comparator( pivot, *last ) ) std::advance( last, -1 );
        if ( first >= last ) break;

        std::iter_swap( first, last );
        std::advance( first, 1 );
      }

      std::iter_swap( mid, last );
      return last;
    }
  }

  template <typename Iterator, 
    typename Comparator = std::less<typename std::iterator_traits<Iterator>::value_type>>
  void quickSort( Iterator first, Iterator last, Comparator comparator = {} )
  {
    if ( std::distance( first, last ) < 2 ) return;

    auto pivot = internal::partition( first, last, comparator );
    quickSort( first, pivot, comparator );
    quickSort( pivot + 1, last, comparator );
  }
}
Merge sort 
// mergesort.h
#pragma once

#include <algorithm>
#include <vector>

namespace csc280
{
  namespace internal
  {
    template<typename InputIt, typename OutputIt, typename Comparator>
    OutputIt merge( InputIt lbegin, InputIt lend, InputIt rbegin, InputIt rend,
      OutputIt output, Comparator comparator )
    {
      for ( ; lbegin != lend; ++output )
      {
        if ( rbegin == rend ) return std::copy( lbegin, lend, output );

        if ( comparator( *rbegin, *lbegin ) )
        {
          std::iter_swap( output, rbegin );
          ++rbegin;
        }
        else
        {
          std::iter_swap( output, lbegin );
          ++lbegin;
        }
      }

      return std::copy( rbegin, rend, output );
    }

    template<typename InputIt, typename OutputIt, typename Comparator>
    void mergeSort( InputIt sbegin, InputIt send,
      OutputIt tbegin, OutputIt tend, Comparator comparator )
    {
      const auto distance = std::distance( sbegin, send );
      if ( distance < 2 ) return;

      auto middle = distance / 2;

      mergeSort( tbegin, tbegin + middle, sbegin, sbegin + middle, comparator );
      mergeSort( tbegin + middle, tend, sbegin + middle, send, comparator );

      merge( sbegin, sbegin + middle,
        sbegin + middle, send,
        tbegin, comparator );
    }
  }

  template<typename Iterator,
    typename Comparator = std::less<typename std::iterator_traits<Iterator>::value_type>>
  void mergeSort( Iterator begin, Iterator end, Comparator comparator = {} )
  {
    const auto distance = std::distance( begin, end );
    if ( distance < 2 ) return;

    using value_type = typename std::iterator_traits<Iterator>::value_type;
    std::vector<value_type> aux{ begin, end };
    internal::mergeSort( aux.begin(), aux.end(), begin, end, comparator );
  }
}
common 
// common.h
#pragma once

#define INT_VALUES { 5, 3, 4, 2, 9, 1, 8, 6, 7, 0 }
#define INT_RESULTS { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

#define STRING_VALUES { "Bother", "Dog", "Cancer", "Another" }
#define STRING_RESULTS { "Another", "Bother", "Cancer", "Dog" }
Point 
// Point.h
#pragma once

#include <ostream>

#define POINT_VALUES {\
 csc280::Point{1.0, 0.0},\
 csc280::Point{0.0, 1.0 },\
 csc280::Point{1.0, 1.0},\
 csc280::Point{0.0, 0.0 },\
 csc280::Point{2.0, 2.0} \
}
#define POINT_RESULTS {\
 csc280::Point{0.0, 0.0},\
 csc280::Point{0.0, 1.0 },\
 csc280::Point{1.0, 0.0},\
 csc280::Point{1.0, 1.0 },\
 csc280::Point{2.0, 2.0}\
}

namespace csc280
{
  struct Point { double x; double y; };

  inline std::ostream& operator << ( std::ostream& stream, const Point& point )
  {
    stream << "Point - x: " << point.x << ", y: " << point.y << std::endl;
    return stream;
  }

  inline bool operator == ( const Point& left, const Point& right )
  {
    return ( left.x == right.x ) && ( left.y == right.y );
  }

  inline bool operator != ( const Point& left, const Point& right )
  {
    return !( left == right );
  }

  inline bool operator < ( const Point& left, const Point& right )
  {
    return ( ( left.x == right.x ) ? ( left.y < right.y ) : ( left.x < right.x ) );
  }

  inline bool operator > ( const Point& left, const Point& right )
  {
    return ( ( left.x == right.x ) ? ( left.y > right.y ) : ( left.x > right.x ) );
  }
}

namespace std
{
  template <>
  inline void swap( csc280::Point& lhs, csc280::Point& rhs ) noexcept
  {
    swap( lhs.x, rhs.x );
    swap( lhs.y, rhs.y );
  }
}
Quicksort Test 
// quicksort.cpp
#include "catch.hpp"
#include "../main/quicksort.h"
#include "common.h"
#include "Point.h"

#include <array>
#include <iterator>
#include <vector>

SCENARIO( "Quicksort can sort numbers" )
{
  GIVEN( "An array of integers" )
  {
    int array[] = INT_VALUES;
    const int results[] = INT_RESULTS;

    THEN( "Sorted array matches expected result" )
    {
      csc280::quickSort( std::begin( array ), std::end( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when ordered in descending order" )
    {
      csc280::quickSort( std::rbegin( array ), std::rend( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::crbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a less than lambda" )
    {
      csc280::quickSort( std::begin( array ), std::end( array ),
        [] ( int lhs, int rhs ) { return lhs < rhs; } );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a greater than lambda" )
    {
      csc280::quickSort( std::begin( array ), std::end( array ),
        [] ( int lhs, int rhs ) { return lhs > rhs; } );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::crbegin( results ) ) );
    }
  }
}

SCENARIO( "Quicksort can sort text" )
{
  GIVEN( "An array of strings" )
  {
    std::array<std::string, 4> array STRING_VALUES;
    const std::array<std::string, 4> results STRING_RESULTS;

    THEN( "Sorted array matches expected result" )
    {
      csc280::quickSort( std::begin( array ), std::end( array ) );
      REQUIRE( array == results );
    }

    AND_THEN( "Sorted array matches expected result when ordered in descending order" )
    {
      csc280::quickSort( std::rbegin( array ), std::rend( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::crbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a less than lambda" )
    {
      csc280::quickSort( std::begin( array ), std::end( array ),
        [] ( const std::string& lhs, const std::string& rhs ) { return lhs < rhs; } );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a greater than lambda" )
    {
      csc280::quickSort( std::begin( array ), std::end( array ),
        [] ( const std::string& lhs, const std::string& rhs ) { return lhs > rhs; } );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::crbegin( results ) ) );
    }
  }
}

SCENARIO( "Quicksort can sort custom objects" )
{
  GIVEN( "A vector of Point objects" )
  {
    std::vector<csc280::Point> vector POINT_VALUES;
    const std::vector<csc280::Point> results POINT_RESULTS;

    THEN( "Sorted vector matches expected result" )
    {
      csc280::quickSort( vector.begin(), vector.end() );
      REQUIRE( vector == results );
    }

    AND_THEN( "Sorted vector matches expected result when using a less than lambda" )
    {
      csc280::quickSort( std::begin( vector ), std::end( vector ),
        [] ( const csc280::Point& lhs, const csc280::Point& rhs ) { return lhs < rhs; } );
      REQUIRE( std::equal( std::cbegin( vector ), std::cend( vector ),
        std::cbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a greater than lambda" )
    {
      csc280::quickSort( std::begin( vector ), std::end( vector ),
        [] ( const csc280::Point& lhs, const csc280::Point& rhs ) { return lhs > rhs; } );
      REQUIRE( std::equal( std::cbegin( vector ), std::cend( vector ),
        std::crbegin( results ) ) );
    }
  }

  GIVEN( "A vector of Point objects" )
  {
    std::vector<csc280::Point> vector POINT_VALUES;
    std::vector<csc280::Point> results POINT_VALUES;
    std::sort( results.begin(), results.end() );

    THEN( "Sorted vector matches std::sort" )
    {
      csc280::quickSort( vector.begin(), vector.end() );
      REQUIRE( vector == results );
    }
  }
}

SCENARIO( "Quicksort implementation leaves pre-sorted data intact" )
{
  GIVEN( "A pre-sorted array of integers" )
  {
    int array[] = INT_RESULTS;
    const int results[] = INT_RESULTS;

    THEN( "Sorted array matches expected result" )
    {
      csc280::quickSort( std::begin( array ), std::end( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }
  }
}
Merge sort test 
// mergesort.cpp
#include "catch.hpp"
#include "../main/mergesort.h"
#include "common.h"
#include "Point.h"

#include <array>
#include <iterator>
#include <vector>

SCENARIO( "Merge sort can sort numbers" )
{
  GIVEN( "An array of integers" )
  {
    int array[] = INT_VALUES;
    const int results[] = INT_RESULTS;

    THEN( "Sorted array matches expected result" )
    {
      csc280::mergeSort( std::begin( array ), std::end( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when ordered in descending order" )
    {
      csc280::mergeSort( std::rbegin( array ), std::rend( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::crbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a less than lambda" )
    {
      csc280::mergeSort( std::begin( array ), std::end( array ),
        [] ( int lhs, int rhs ) { return lhs < rhs; } );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a greater than lambda" )
    {
      csc280::mergeSort( std::begin( array ), std::end( array ),
        [] ( int lhs, int rhs ) { return lhs > rhs; } );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::crbegin( results ) ) );
    }
  }
}

SCENARIO( "Merge sort can sort text" )
{
  GIVEN( "An array of strings" )
  {
    std::array<std::string, 4> array STRING_VALUES;
    const std::array<std::string, 4> results STRING_RESULTS;

    THEN( "Sorted array matches expected result" )
    {
      csc280::mergeSort( std::begin( array ), std::end( array ) );
      REQUIRE( array == results );
    }

    AND_THEN( "Sorted array matches expected result when ordered in descending order" )
    {
      csc280::mergeSort( std::rbegin( array ), std::rend( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::crbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a less than lambda" )
    {
      csc280::mergeSort( std::begin( array ), std::end( array ),
        [] ( const std::string& lhs, const std::string& rhs ) { return lhs < rhs; } );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a greater than lambda" )
    {
      csc280::mergeSort( std::begin( array ), std::end( array ),
        [] ( const std::string& lhs, const std::string& rhs ) { return lhs > rhs; } );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::crbegin( results ) ) );
    }
  }
}

SCENARIO( "Merge sort can sort custom objects" )
{
  GIVEN( "A vector of Point objects" )
  {
    std::vector<csc280::Point> vector POINT_VALUES;
    const std::vector<csc280::Point> results POINT_RESULTS;

    THEN( "Sorted vector matches expected result" )
    {
      csc280::mergeSort( vector.begin(), vector.end() );
      REQUIRE( vector == results );
    }

    AND_THEN( "Sorted vector matches expected result when using a less than lambda" )
    {
      csc280::mergeSort( std::begin( vector ), std::end( vector ),
        [] ( const csc280::Point& lhs, const csc280::Point& rhs ) { return lhs < rhs; } );
      REQUIRE( std::equal( std::cbegin( vector ), std::cend( vector ),
        std::cbegin( results ) ) );
    }

    AND_THEN( "Sorted array matches expected result when using a greater than lambda" )
    {
      csc280::mergeSort( std::begin( vector ), std::end( vector ),
        [] ( const csc280::Point& lhs, const csc280::Point& rhs ) { return lhs > rhs; } );
      REQUIRE( std::equal( std::cbegin( vector ), std::cend( vector ),
        std::crbegin( results ) ) );
    }
  }

  GIVEN( "A vector of Point objects" )
  {
    std::vector<csc280::Point> vector POINT_VALUES;
    std::vector<csc280::Point> results POINT_VALUES;
    std::sort( results.begin(), results.end() );

    THEN( "Sorted vector matches std::sort" )
    {
      csc280::mergeSort( vector.begin(), vector.end() );
      REQUIRE( vector == results );
    }
  }
}

SCENARIO( "Merge sort implementation leaves pre-sorted data intact" )
{
  GIVEN( "A pre-sorted array of integers" )
  {
    int array[] = INT_RESULTS;
    const int results[] = INT_RESULTS;

    THEN( "Sorted array matches expected result" )
    {
      csc280::mergeSort( std::begin( array ), std::end( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }
  }
}