string-sort-algorithms-comparison/src/StringSortTester.h at main · SeM0nchik/string-sort-algorithms-comparison · GitHub

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
45
46
47
48
49
50
51
52
53
54
55
56
#ifndef STRINGSORTTESTER_H_
#define STRINGSORTTESTER_H_

#include <cstdint>
#include <string>
#include <utility>
#include <vector>

struct BenchmarkResult {
  int size;
  std::string algorithm;
  std::string array_type;
  double time_ms;
  uint64_t comparisons;
};

class StringSortTester {
 public:
  void ResetComparisons();
  uint64_t GetComparisons() const;

  void TestQuickSort(const std::vector<std::string>& base, int size,
                     const std::string& type);
  void TestMergeSort(const std::vector<std::string>& base, int size,
                     const std::string& type);
  void TestStringQuickSort(const std::vector<std::string>& base, int size,
                           const std::string& type);
  void TestStringMergeSort(const std::vector<std::string>& base, int size,
                           const std::string& type);
  void TestMsdRadixSort(const std::vector<std::string>& base, int size,
                        const std::string& type);
  void TestMsdRadixSortWithQuickSort(const std::vector<std::string>& base,
                                     int size, const std::string& type);

  void SaveToCsv(const std::string& filename) const;
  const std::vector<BenchmarkResult>& GetResults() const;

 private:
  bool CompareStrings(const std::string& a, const std::string& b);
  std::pair<bool, int> LcpCompare(const std::string& a, const std::string& b,
                                  int known);
  char GetAt(const std::string& s, int pos);

  void QuickSort(std::vector<std::string>& arr, int l, int r);
  void MergeSort(std::vector<std::string>& arr, int l, int r);
  void StringQuickSort(std::vector<std::string>& arr, int l, int r, int depth);
  void StringMergeSort(std::vector<std::string>& arr, int left, int right);
  void MsdRadixSort(std::vector<std::string>& arr, int l, int r, int pos);
  void MsdRadixSortWithQuickSort(std::vector<std::string>& arr, int l, int r,
                                 int pos);

  uint64_t comparisons_count_ = 0;
  std::vector<BenchmarkResult> results_;
};

#endif  // STRINGSORTTESTER_H_