В мире алгоритмов и методов сортировки есть один метод, который выделяется своей простотой и эффективностью: сегментная сортировка. Этот алгоритм сортировки особенно хорошо работает при работе с набором равномерно распределенных элементов. В этой статье мы углубимся в детали сегментной сортировки, объясним, как она работает, приведем примеры кода на C и исследуем ее временную и пространственную сложность.

Что такое сегментная сортировка?
Групповая сортировка — это алгоритм сортировки на основе распределения, который делит входные данные на конечное число сегментов. Каждый сегмент представляет собой диапазон значений и изначально пуст. Затем элементы входного массива распределяются по сегментам в зависимости от их значений. После этого каждая корзина сортируется индивидуально, либо с использованием другого алгоритма сортировки, либо с применением рекурсивной сортировки. Наконец, отсортированные элементы из всех сегментов объединяются для получения отсортированного вывода.

Пример кода на C:
Давайте посмотрим на простую реализацию сегментарной сортировки на C:

#include <stdio.h>
// Function to sort the array using Bucket Sort
void bucketSort(int array[], int n) {
    // Choose the number of buckets (here, we assume 10)
    const int numBuckets = 10;

    // Create the buckets
    int buckets[numBuckets][n];
    int bucketSize[numBuckets] = {0};

    // Distribute the elements into buckets
    for (int i = 0; i < n; i++) {
        int bucketIndex = array[i] / numBuckets;
        buckets[bucketIndex][bucketSize[bucketIndex]++] = array[i];
    }
// Sort the elements within each bucket
    for (int i = 0; i < numBuckets; i++) {
        // Applying another sorting algorithm (e.g., Insertion Sort)
        for (int j = 1; j < bucketSize[i]; j++) {
            int key = buckets[i][j];
            int k = j - 1;

            while (k >= 0 && buckets[i][k] > key) {
                buckets[i][k + 1] = buckets[i][k];
                k--;
            }

            buckets[i][k + 1] = key;
        }
    }
// Concatenate the sorted elements from all buckets
    int index = 0;
    for (int i = 0; i < numBuckets; i++) {
        for (int j = 0; j < bucketSize[i]; j++) {
            array[index++] = buckets[i][j];
        }
    }
}
// Example usage
int main() {
    int array[] = {29, 25, 10, 12, 22, 18, 30, 45, 37};
    int n = sizeof(array) / sizeof(array[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }

    bucketSort(array, n);

    printf("\nSorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }

    return 0;
}

В этом примере у нас есть массив целых чисел, который мы хотим отсортировать с помощью сегментной сортировки. Код сначала делит элементы на сегменты на основе их значений. Затем он применяет простой алгоритм сортировки (в данном случае сортировку вставками) для сортировки элементов в каждом сегменте. Наконец, отсортированные элементы из всех сегментов объединяются для получения окончательного отсортированного массива.

Временная и пространственная сложность.
Временная сложность сегментной сортировки зависит от алгоритма сортировки, используемого в каждом сегменте. В приведенном выше примере мы использовали сортировку вставками, средняя временная сложность которой составляет O(n^2). Однако если элементы внутри каждого сегмента распределены равномерно, средняя временная сложность сегментной сортировки составляет примерно O(n). Пространственная сложность сортировки сегментов равна O(n + k), где n — количество элементов, а k — количество сегментов.

Сортировка по сегментам – это простой и эффективный алгоритм сортировки, который хорошо работает, когда входные элементы распределены равномерно. Разделяя элементы на сегменты и сортируя их по отдельности, Bucket Sort обеспечивает в среднем линейную временную сложность. В этой статье мы предоставили пример кода на языке C и объяснили основные концепции сортировки по сегментам. Теперь вы можете с уверенностью использовать этот алгоритм для эффективной сортировки данных.