CLRS-Cpp-Implementations-Chapter-8

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

namespace CLRS
{
  /*
   * Suppose elements of array uniformly and individually
   * scattered in half open interval [0, 1)
   * TODO: this time uses standard library list and iterator,
   * this program would be refactored after list implementation.
   */
  template <typename T, std::size_t n>
  void bucket_sort(T (&a)[n])
  {
    std::list<T> b[n];
    for(std::size_t i = 0; i != n; ++i)
      b[static_cast<std::size_t>(n*a[i])].push_back(a[i]);

    for(std::size_t j = 0; j != n; ++j)
      /* be careful that the commom algorithm sort
       * could not be applied on containers which
       * do not support random access
       */
      b[j].sort();

    std::size_t i = 0;
    for(std::size_t j = 0; j != n; ++j)
      {
	auto it = b[j].cbegin();
	while(it != b[j].cend())
	  {
	    a[i] = *it;
	    ++it;
	    ++i;
	  }
      }
  }
}

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

namespace CLRS
{
  // specified for array with unsigned elements
  template <typename T, std::size_t n>
  void counting_sort(T (&a)[n], T (&b)[n], std::size_t k)
  {
    T c[k + 1];
    for(std::size_t i = 0; i <= k; ++i)
      c[i] = 0;
    for(std::size_t j = 0; j != n; ++j)
      ++c[a[j]];
    for(std::size_t i = 1; i <= k; ++i)
      c[i] = c[i] + c[i - 1];
    for(long long j = n - 1; j >= 0; --j)
      {
	// be careful that the index starts from 0
	// and the minimum element should be placed in index 0.
	b[c[a[j]] - 1] = a[j];
	--c[a[j]];
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

namespace CLRS
{
  template <typename T>
  T radix_digit(T a, std::size_t d)
  {
    T return_value;
    for(T i = 1; i <= d; ++i)
      {
	return_value = a % 10;
	a /= 10;
      }
    return return_value;
  }

  template <typename T, std::size_t n>
  void radix_counting_sort(T (&a)[n], T (&b)[n], std::size_t d)
  {
    T c[10];
    for(std::size_t i = 0; i <= 9; ++i)
      c[i] = 0;
    for(std::size_t j = 0; j != n; ++j)
      ++c[radix_digit(a[j], d)];
    for(std::size_t i = 1; i <= 9; ++i)
      c[i] = c[i] + c[i - 1];
    for(long long j = n - 1; j >= 0; --j)
      {
	b[c[radix_digit(a[j], d)] - 1] = a[j];
	--c[radix_digit(a[j], d)];
      }
  }

  template <typename T, std::size_t n>
  void radix_sort(T (&a)[n], T d)
  {
    T b[n];
    for(std::size_t j = 1; j <= d; ++j)
      {
	radix_counting_sort(a, b, j);
	for(std::size_t i = 0; i != n; ++i)
	  a[i] = b[i];
      }
  }
}