Одним из примеров задачи, выполненной с особым удовлетворением, была реализация эффективного алгоритма сортировки для большого массива данных на C++. Задача требовала оптимизации по времени и памяти. Я использовал алгоритм быстрой сортировки с улучшениями, такими как выбор медианы в качестве опорного элемента и переход на сортировку вставками для маленьких подмассивов. Это позволило значительно ускорить работу программы.

#include <iostream>
#include <vector>

void insertionSort(std::vector<int>& arr, int left, int right) {
    for (int i = left + 1; i <= right; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

int medianOfThree(std::vector<int>& arr, int left, int right) {
    int mid = left + (right - left) / 2;
    if (arr[right] < arr[left]) std::swap(arr[left], arr[right]);
    if (arr[mid] < arr[left]) std::swap(arr[mid], arr[left]);
    if (arr[right] < arr[mid]) std::swap(arr[right], arr[mid]);
    return mid;
}

void quickSort(std::vector<int>& arr, int left, int right) {
    if (right - left <= 10) {
        insertionSort(arr, left, right);
        return;
    }
    int pivotIndex = medianOfThree(arr, left, right);
    int pivot = arr[pivotIndex];
    std::swap(arr[pivotIndex], arr[right]);
    int i = left;
    for (int j = left; j < right; ++j) {
        if (arr[j] < pivot) {
            std::swap(arr[i], arr[j]);
            ++i;
        }
    }
    std::swap(arr[i], arr[right]);
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

int main() {
    std::vector<int> data = {10, 7, 8, 9, 1, 5};
    quickSort(data, 0, data.size() - 1);
    for (int num : data) {
        std::cout << num << " ";
    }
    return 0;
}

Результат — стабильная и быстрая сортировка, что повысило производительность проекта.

Есть ли у вас примеры задач, выполненных с особым удовлетворением?