CLRS-Cpp-Implementations-Chapter-5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include "chapter-2/merge_sort/merge_sort.h"
namespace CLRS
{
  template <typename T>
  bool operator<=(std::pair<T, unsigned> p1, std::pair<T, unsigned> p2)
  {
    return p1.second <= p2.second;
  }

  template <typename T, std::size_t n>
  void permute_by_sorting(T (&array)[n])
  {
    std::default_random_engine e(std::time(0));
    std::uniform_int_distribution<unsigned> u(0, (n-1)*(n-1)*(n-1));
    std::pair<T, unsigned> parray[n];
    for(std::size_t i = 0; i != n; ++i)
      parray[i] = std::pair<T, unsigned>(array[i], u(e));
    CLRS::merge_sort(parray, 0, n - 1);
    for(std::size_t i = 0; i != n; ++i)
      array[i] = parray[i].first;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include "permute_by_sorting.h"
namespace CLRS
{
  template <typename T, std::size_t n>
  void sort_randomized_hire_assistant(T (&a)[n], T *choose)
  {
    CLRS::permute_by_sorting(a);
    *choose = 0;
    for(std::size_t i = 0; i != n; ++i)
      {
	if(a[i] > *choose)
	  *choose = a[i];
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include "randomize_in_place.h"
namespace CLRS
{
  template <typename T, std::size_t n>
  void swap_randomized_hire_assistant(T (&a)[n], T *choose)
  {
    randomize_in_place(a);
    *choose = 0;
    for(std::size_t i = 0; i != n; ++i)
      {
	if(a[i] > *choose)
	  *choose = a[i];
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

namespace CLRS
{
  template <typename T, std::size_t n>
  void randomize_in_place(T (&a)[n])
  {
    std::default_random_engine e(std::time(0));
    for(std::size_t i = 0; i != n; ++i)
      {
	std::uniform_int_distribution<unsigned> u(i, n - 1);
	T temp = a[i];
	std::size_t j = u(e);
	a[i] = a[j];
	a[i] = temp;
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

namespace CLRS
{
  template <typename T, std::size_t n>
  void hire_assistant(const T (&a)[n], T *choose)
  {
    *choose = 0;
    for(std::size_t i = 0; i != n; ++i)
      {
	if(a[i] > *choose)
	  *choose = a[i];
      }
  }
}