C++: полное руководство по бинарной сортировке

При бинарной сортировке, или сортировке с бинарными вставками, корректная позиция каждого элемента определяется двоичным поиском. Поэтому на больших наборах данных такая сортировка эффективнее обычной сортировки вставками. Изучим ее реализацию и эффективное использование.

Базовая реализация

Вот простая реализация бинарной сортировки:

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

При выборе бинарной сортировки учитывайте, что она:

1. Хороша для почти отсортированных данных.
2. Эффективна для наборов данных малого и среднего размеров.
3. Ею поддерживается стабильность: относительный порядок эквивалентных элементов сохраняется.
4. На больших случайных наборах данных выполняется оптимальнее сортировки вставками, но хуже быстрой сортировки.

Не забывайте: хотя при бинарной сортировке меньше сравнений, чем при обычной сортировке вставками, в худшем случае ей по-прежнему требуется O(n²) перемещений. Для очень больших наборов данных воспользуйтесь std::sort или другими алгоритмами, такими как быстрая сортировка.

Читайте также:

• C++: полное руководство по «приведению вверх»
• Найти все на C++: практическое руководство
• C++: полное руководство по функциям Floor и Ceil

Читайте нас в Telegram, VK и Дзен

Перевод статьи ryan: Binary Sort in C++: Complete Guide