Implement the binary search algorithm that operates on data that is iterable.

• Create a new empty Visual Studio C++ project named search
  • Right-click the search solution on the left navigation pane and choose Properties
  • Expand the Linker node and select the System item
  • Select “Console (/SUBSYSTEM:CONSOLE)” from the SubSystem drop-down menu. This will allow us to view the results of running the application in the DOS Command window.
  • Expand the C/C++ node and select the Preprocessor item
  • Chose Edit on the Preprocessor Definitions item on the right pane.
  • Enter _SCL_SECURE_NO_WARNINGS in the top box of the dialog window. Microsoft provides checked versions of std::equal algorithm, which however are Microsoft extensions and not available on other platforms/compilers. This will disable the error that the compiler would otherwise generate.
• Download the Catch unit testing framework header file and add to the project Header Files section.
• Add a new header file named common to the project. We will declare a few macros that will help create an unordered dataset of integer and string values as well as their corresponding sorted values. We will use the sorted values to ensure that our implementation of the sort functions work as designed.

#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" }

• Add a new header file named Point to the project. We will declare a simple structure named Point, and add some useful functions to support our structure. We will use the Point structure to exercise searching and sorting objects. We will also declare two macros to create a random dataset of Point instances, as well as another which is what the sorted dataset should look like when the algorithms have finished working on the unordered dataset.

#pragma once

#include <iostream>
#include <ostream>

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

namespace csc240
{
  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 != right ) && ( !( left < right ) ) );
  }
}

• Create a new header file named search in which we will implement our binary search algorithm. Note that, in this example we will adopt the standard C++ pattern for a search algorithm function. We will use a template function that operates on a pair of iterators (generally the beginning and end iterators for a dataset) and a user specified value that is to be searched for. Since this is a template function, the full implementation needs to be in the header file.

#pragma once

namespace csc240
{
  template <typename Iterator, typename Type>
  Iterator binarySearch( Iterator first, Iterator last, const Type& value )
  {
    // The original last passed in.  Will return it to indicate that the
    // value specified was not found.
    auto notFound = last;

    // usually "last" points beyond the last element
    // now it points directly to that last element
    --last;

    while ( first < last )
    {
      auto mid = first + (last - first) / 2;
      if ( value == *mid ) return mid;

      if ( value > *mid ) first = ( mid < last ) ? ++mid : last;
      else last = ( mid > first ) ? --mid : first;
    }

    // We broke out of the loop when first is same as last.
    // Check the value to see if it matches the last item of passed in data set.
    if ( ( first == last ) && ( value == *first ) ) return first;

    return notFound;
  }
}

• Add a new C++ source file named search to the project. We will build a BDD style test suite that will exercise our binary search algorithm implementation with C-style array of integer values (observe the use of std::cbegin and std::cend functions to get constant iterators to the C-array), a std::array of std::string values, and a std::vector of csc240::Point instances. Note how the use of a template function allows us to have a single template of the search function while working with different types of dataset containers and data types. Also note the use of std::binary_search which is provided by the STL in the last test.

#define CATCH_CONFIG_MAIN
#include "catch.hpp"
#include "search.h"
#include "common.h"
#include "Point.h"

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

SCENARIO( "Binary search can find numbers" )
{
  GIVEN( "An array of integers" )
  {
    const int results[] = INT_RESULTS;
    auto begin = std::cbegin( results );
    auto end = std::cend( results );

    THEN( "Binary search finds valid values" )
    {
      auto position = csc240::binarySearch( begin, end, 1 );
      REQUIRE( position != end );
      REQUIRE( *position == 1 );

      position = csc240::binarySearch( begin, end, 5 );
      REQUIRE( position != end );
      REQUIRE( *position == 5 );

      for ( auto value : results )
      {
        position = csc240::binarySearch( begin, end, value );
        REQUIRE( position != end );
        REQUIRE( *position == value );
      }
    }

    THEN( "Binary search does not find invalid values" )
    {
      auto position = csc240::binarySearch( begin, end, -1 );
      REQUIRE( position == end );

      position = csc240::binarySearch( begin, end, 25 );
      REQUIRE( position == end );
    }
  }
}

SCENARIO( "Binary search can find text" )
{
  GIVEN( "An array of strings" )
  {
    const std::array<std::string, 4> results STRING_RESULTS;
    auto begin = results.cbegin();
    auto end = results.cend();

    THEN( "Binary search finds valid values" )
    {
      std::string s{ "Cancer" };
      auto position = csc240::binarySearch( begin, end, s );
      REQUIRE( position != end );
      REQUIRE( *position == s );

      s = "Bother";
      position = csc240::binarySearch( begin, end, s );
      REQUIRE( position != end );
      REQUIRE( *position == s );

      for ( auto &value : results )
      {
        position = csc240::binarySearch( begin, end, value );
        REQUIRE( position != end );
        REQUIRE( *position == value );
      }
    }

    THEN( "Binary search does not find invalid values" )
    {
      auto position = csc240::binarySearch( begin, end, "0" );
      REQUIRE( position == end );

      position = csc240::binarySearch( begin, end, "Blah" );
      REQUIRE( position == end );
    }
  }
}

SCENARIO( "Binary search can find custom objects" )
{
  GIVEN( "A vector of Point objects" )
  {
    const std::vector<csc240::Point> results POINT_RESULTS;
    auto begin = results.cbegin();
    auto end = results.cend();

    THEN( "Binary search finds valid values" )
    {
      csc240::Point p{ 1.0, 1.0 };
      auto position = csc240::binarySearch( begin, end, p );
      REQUIRE( position != end );
      REQUIRE( *position == p );

      p = csc240::Point{ 2.0, 2.0 };
      position = csc240::binarySearch( begin, end, p );
      REQUIRE( position != end );
      REQUIRE( *position == p );

      for ( auto &value : results )
      {
        position = csc240::binarySearch( begin, end, value );
        REQUIRE( position != end );
        REQUIRE( *position == value );
      }
    }

    THEN( "Binary search does not find invalid values" )
    {
      csc240::Point p{ 10.0, 0.0 };
      auto position = csc240::binarySearch( begin, end, p );
      REQUIRE( position == end );

      p = csc240::Point{ -10.0, 0.0 };
      position = csc240::binarySearch( begin, end, p );
      REQUIRE( position == end );
    }

    THEN( "Binary search is similar to standard function" )
    {
      for ( auto &value : results )
      {
        REQUIRE( std::binary_search( begin, end, value ) );
      }
    }
  }
}

• Build and run the project and observe the results. Try modifying the macro definitions with other sets of values and observe the results. Try using an unsorted dataset with the binary search algorithm.

We will now add a bubble sort implementation to the project created above and test our implementation.

• Add a new header file named bubble to the project. We will once again implement our function using the common C++ pattern of working off a pair of iterators to the underlying dataset. Note that callers must invoke the function with non-constant iterators, as the iterators need to support modification to the underlying dataset for it to be sorted. Note the use of the std::iter_swap function which will swap the iterator values for us. Our implementation will use the standard less than (<) operator to determine the sort order.

#pragma once
#include <algorithm>

namespace csc240
{
  template <typename Iterator>
  void bubbleSort( Iterator first, Iterator last )
  {
    if ( first == last ) return;

    // usually "last" points beyond the last element
    // now it points directly to that last element
    --last;

    if ( first == last ) return;

    bool swapped;
    do
    {
      swapped = false;

      Iterator current = first;
      while ( current != last )
      {
        Iterator next = current;
        ++next;

        if ( *next < *current )
        {
          std::iter_swap( current, next );
          swapped = true;
        }

        ++current;
      }

      // last element is already sorted now
      --last;
    } while ( swapped && ( first != last ) );
  }
}

• Add a new C++ source file named bubble to the project. We will build a BDD style test suite that will exercise our bubble sort algorithm implementation with C-style array of integer values (observe the use of std::begin and std::end functions to get iterators to the C-array), a std::array of std::string values, and a std::vector of csc240::Point instances. Note the use of std::equal to compare two C-arrays for equality. Note the use of std::sort in the final test. This is just to illustrate the standard library function that is generally used for sorting.

#include "catch.hpp"
#include "common.h"
#include "bubble.h"
#include "Point.h"

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

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

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

SCENARIO( "Bubble 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" )
    {
      csc240::bubbleSort( array.begin(), array.end() );
      REQUIRE( array == results );
    }
  }
}

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

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

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

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

SCENARIO( "Bubble 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" )
    {
      csc240::bubbleSort( std::begin( array ), std::end( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }
  }
}

• Build and run the project and observe the results. Try modifying the macro definitions with other sets of values and observe the results.

We will now add a selection sort implementation to the project created above and test our implementation.

• Add a new header file named selection to the project. We will implement our sort algorithm once again using a template function that operates on a pair of iterators to the dataset.

#pragma once
#include <algorithm>

namespace csc240
{
  template <typename Iterator>
  void selectionSort( Iterator first, Iterator last )
  {
    for ( Iterator current = first; current != last; ++current )
    {
      // find smallest element in the unsorted part and remember its iterator in "minimum"
      Iterator minimum = current;
      Iterator compare = current;
      ++compare;

      while ( compare != last )
      {
        if ( *compare < *minimum ) minimum = compare;
        ++compare;
      }
      // add minimum to the end of the already sorted part
      if ( current != minimum ) std::iter_swap( current, minimum );
    }
  }
}

• Add a new C++ source file named selection to the project. We will build a BDD style test suite that will exercise our selection sort algorithm implementation with C-style array of integer values, a std::array of std::string values, and a std::vector of csc240::Point instances.

#include "catch.hpp"
#include "selection.h"
#include "common.h"
#include "Point.h"

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

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

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

SCENARIO( "Selection 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" )
    {
      csc240::selectionSort( array.begin(), array.end() );
      REQUIRE( array == results );
    }
  }
}

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

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

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

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

SCENARIO( "Selection 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" )
    {
      csc240::selectionSort( std::begin( array ), std::end( array ) );
      REQUIRE( std::equal( std::cbegin( array ), std::cend( array ),
        std::cbegin( results ) ) );
    }
  }
}

• Build and run the project and observe the results. Try modifying the macro definitions with other sets of values and observe the results.