При бинарной сортировке, или сортировке с бинарными вставками, корректная позиция каждого элемента определяется двоичным поиском. Поэтому на больших наборах данных такая сортировка эффективнее обычной сортировки вставками. Изучим ее реализацию и эффективное использование.
Базовая реализация
Вот простая реализация бинарной сортировки:
#include <vector>
template<typename T>
int binary_search(std::vector<T>& arr, int target, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
template<typename T>
void binary_sort(std::vector<T>& arr) {
for (int i = 1; i < arr.size(); ++i) {
T key = arr[i];
int j = i - 1;
// Место для вставки находится двоичным поиском
int loc = binary_search(arr, key, 0, j);
// Чтобы освободить место, элементы перемещаются
while (j >= loc) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
Реальный пример: система учета учащихся
Вот практическое применение бинарной сортировки:
struct Student {
std::string name;
int id;
float gpa;
bool operator<(const Student& other) const {
return id < other.id;
}
bool operator==(const Student& other) const {
return id == other.id;
}
};
class StudentDatabase {
private:
std::vector<Student> students;
public:
void add_student(const Student& student) {
students.push_back(student);
binary_sort(students);
}
Student* find_student(int id) {
Student target{.id = id};
int loc = binary_search(students, target, 0, students.size() - 1);
if (loc < students.size() && students[loc].id == id) {
return &students[loc];
}
return nullptr;
}
void print_sorted_students() const {
for (const auto& student : students) {
std::cout << "ID: " << student.id
<< ", Name: " << student.name
<< ", GPA: " << student.gpa << '\n';
}
}
};
// Пример использования
void manage_students() {
StudentDatabase db;
db.add_student({"Alice", 103, 3.8f});
db.add_student({"Bob", 101, 3.5f});
db.add_student({"Charlie", 102, 3.9f});
db.print_sorted_students();
}
Оптимизированная бинарная сортировка для пользовательских объектов
Вот оптимизированная версия, здесь меньше перемещений в памяти:
template<typename T, typename Compare = std::less<T>>
class BinarySorter {
private:
static int find_position(const std::vector<T>& arr, const T& target,
int start, int end, Compare comp = Compare()) {
while (start <= end) {
int mid = start + (end - start) / 2;
if (comp(arr[mid], target)) {
start = mid + 1;
} else if (comp(target, arr[mid])) {
end = mid - 1;
} else {
return mid;
}
}
return start;
}
public:
static void sort(std::vector<T>& arr, Compare comp = Compare()) {
if (arr.size() <= 1) return;
for (int i = 1; i < arr.size(); ++i) {
T current = std::move(arr[i]);
int pos = find_position(arr, current, 0, i - 1, comp);
// Производительность повышается операциями перемещения
for (int j = i; j > pos; --j) {
arr[j] = std::move(arr[j - 1]);
}
arr[pos] = std::move(current);
}
}
};
// Пример с пользовательским компаратором
struct TimeStamp {
int hour, minute, second;
bool operator<(const TimeStamp& other) const {
if (hour != other.hour) return hour < other.hour;
if (minute != other.minute) return minute < other.minute;
return second < other.second;
}
};
void sort_timestamps() {
std::vector<TimeStamp> times = {
{14, 30, 0},
{9, 15, 30},
{14, 15, 45}
};
BinarySorter<TimeStamp>::sort(times);
for (const auto& time : times) {
std::cout << time.hour << ":"
<< time.minute << ":"
<< time.second << '\n';
}
}
Реальное применение: обработка записей журнала
Вот как эффективно бинарная сортировка справляется с записями журнала:
class LogEntry {
public:
std::chrono::system_clock::time_point timestamp;
std::string message;
int priority;
bool operator<(const LogEntry& other) const {
return timestamp < other.timestamp;
}
};
class LogProcessor {
private:
std::vector<LogEntry> log_entries;
static constexpr size_t BATCH_SIZE = 1000;
public:
void add_entry(const LogEntry& entry) {
log_entries.push_back(entry);
// Чтобы избежать постоянных пересортировок, выполняется пакетная сортировка
if (log_entries.size() % BATCH_SIZE == 0) {
process_batch();
}
}
void process_batch() {
binary_sort(log_entries);
// Обрабатываются сортированные записи
auto now = std::chrono::system_clock::now();
auto one_hour_ago = now - std::chrono::hours(1);
// Удаляются записи старше одного часа
auto it = std::find_if(log_entries.begin(), log_entries.end(),
[&](const LogEntry& entry) {
return entry.timestamp >= one_hour_ago;
});
log_entries.erase(log_entries.begin(), it);
}
void print_recent_logs(int count = 10) const {
int n = std::min(count, static_cast<int>(log_entries.size()));
for (int i = log_entries.size() - n; i < log_entries.size(); ++i) {
auto time_t = std::chrono::system_clock::to_time_t(
log_entries[i].timestamp);
std::cout << std::ctime(&time_t) << " - "
<< log_entries[i].message << '\n';
}
}
};
Сравнение производительности
Вот тест производительности для сравнения бинарной сортировки с другими алгоритмами сортировки:
class SortBenchmark {
private:
template<typename Func>
static double measure_time(Func&& f) {
auto start = std::chrono::high_resolution_clock::now();
f();
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration<double>(end - start).count();
}
public:
static void run_benchmark(int size) {
std::vector<int> data(size);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(1, 10000);
// Генерируются случайные данные
for (int& x : data) {
x = dis(gen);
}
// Тестируется бинарная сортировка
auto binary_time = measure_time([&] {
auto binary_data = data;
binary_sort(binary_data);
});
// Тестируется «std::sort»
auto std_time = measure_time([&] {
auto std_data = data;
std::sort(std_data.begin(), std_data.end());
});
std::cout << "Array size: " << size << '\n'
<< "Binary sort time: " << binary_time << "s\n"
<< "std::sort time: " << std_time << "s\n";
}
};
// Выполняются тесты производительности
void compare_sorts() {
for (int size : {100, 1000, 10000}) {
SortBenchmark::run_benchmark(size);
std::cout << "-------------------\n";
}
}
При выборе бинарной сортировки учитывайте, что она:
- Хороша для почти отсортированных данных.
- Эффективна для наборов данных малого и среднего размеров.
- Ею поддерживается стабильность: относительный порядок эквивалентных элементов сохраняется.
- На больших случайных наборах данных выполняется оптимальнее сортировки вставками, но хуже быстрой сортировки.
Не забывайте: хотя при бинарной сортировке меньше сравнений, чем при обычной сортировке вставками, в худшем случае ей по-прежнему требуется O(n²) перемещений. Для очень больших наборов данных воспользуйтесь std::sort или другими алгоритмами, такими как быстрая сортировка.
Читайте также:
- C++: полное руководство по «приведению вверх»
- Найти все на C++: практическое руководство
- C++: полное руководство по функциям Floor и Ceil
Читайте нас в Telegram, VK и Дзен
Перевод статьи ryan: Binary Sort in C++: Complete Guide
