Уровень алгоритма

Участник:Yaselivoxin/Алгоритм

Материал из Алговики
Перейти к навигации Перейти к поиску


Алгоритм быстрой сортировки Quicksort
Последовательный алгоритм
Последовательная сложность [math]\displaystyle{ O(n^2) }[/math]
Объём входных данных [math]\displaystyle{ n }[/math]
Объём выходных данных [math]\displaystyle{ n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]\displaystyle{ O(log n) }[/math]
Ширина ярусно-параллельной формы [math]\displaystyle{ O(n) }[/math]


Основные авторы описания: Я.А.Селивохин.

Алгоритм быстрой сортировки QuickSort

Свойства и структура алгоритмов

Общее описание алгоритма

Алгоритм быстрой сортировки (Quicksort) — это один из наиболее известных и часто применяемых алгоритмов сортировки с использованием стратегии "разделяй и властвуй". Алгоритм работает следующим образом: выбирается опорный элемент массива (pivot), и все элементы массива разделяются на две части: те, что меньше опорного, и те, что больше или равны ему. Затем рекурсивно сортируются эти две части. Сортировка продолжается, пока каждый подмассив не будет отсортирован, что приводит к полному упорядочиванию элементов массива.

Этот алгоритм работает на основе сравнений элементов и выполняет операцию сортировки "на месте", то есть без использования дополнительных массивов для хранения промежуточных результатов. Время работы алгоритма зависит от выбора опорного элемента и в лучшем случае составляет 𝑂(nlogn).

Математическое описание алгоритма

Входные данные: Массив А = [a1, a2, ... , an] длинной n, где каждый элемент массива ai сравнивается с другими элементами массива с помощью операции "<=" ("меньше или равно").

Выходные данные: Отсортированный массив А, такой что для всех i и j выполняется условие:

a1 ≤ a2 ≤ ... ≤ an.

Код алгоритма на С: 

int partition(int* A, int lo, int hi) {
    int pivot = A[hi]; // Опорный элемент
    int i = lo - 1; // Индекс для меньших элементов
    for (int j = lo; j < hi; ++j) {
        if (A[j] <= pivot) {
            ++i;
            // Меняем местами элементы
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
    // Ставим опорный элемент на правильную позицию
    int temp = A[i + 1];
    A[i + 1] = A[hi];
    A[hi] = temp;

    return i + 1; // Возвращаем индекс опорного элемента
}

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма быстрой сортировки заключается в разделении массива на два подмассива относительно опорного элемента, после чего рекурсивно сортируются эти подмассивы. Основная операция, выполняющаяся за O(n) в каждом вызове рекурсии, — это разбиение массива на две части (пункт 1.2). Таким образом, вычислительное ядро — это функция partition.

Макроструктура алгоритма

Алгоритм состоит из двух основных макроопераций:

  1. Выбор опорного элемента (pivot).
  2. Разделение массива на две части, элементы которых меньше и больше опорного.
  3. Рекурсивная сортировка двух частей.

Эти макрооперации легко переносятся в другие контексты, например, при многопоточности или в параллельных вычислениях.

Схема реализации последовательного алгоритма

Пример реализации быстрой сортировки на языке псевдокода:

  • Разделение массива относительно опорного элемента.
  • Рекурсивная сортировка двух подмассивов.

Пример кода на C: 

void quicksort(int* A, int lo, int hi) {
    if (lo < hi) {
        int p = partition(A, lo, hi); // Разбиение массива
        quicksort(A, lo, p - 1); // Сортируем левую часть
        quicksort(A, p + 1, hi); // Сортируем правую часть
    }
}

Последовательная сложность алгоритма

Временная сложность:

  • Лучший случай: O(nlogn), когда выбор опорного элемента сбалансирован, и массив делится примерно пополам.
  • Средний случай: O(nlogn), для случайного массива.
  • Худший случай: O(n2), если опорный элемент всегда оказывается наименьшим или наибольшим элементом.

Пространственная сложность: O(logn), поскольку рекурсия в худшем случает требует глубины стека O(n), а в среднем случае - O(logn).

Информационный граф

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

Рис.1. Информационная структура алгоритма быстрой сортировки

Вводимые замены:

  • ОЭ - опорный элемент
  • ЛЧ - левая часть
  • ПЧ - правая часть

Ресурс параллелизма алгоритма

Алгоритм быстрой сортировки обладает хорошим потенциалом для параллельной реализации. Основной параллелизм можно достичь за счет выполнения рекурсивных вызовов для левых и правых подмассивов параллельно. Для этого можно использовать многозадачность, например, с помощью библиотек OpenMP или стандартной библиотеки C++. Например, с использованием 

std::async

Входные и выходные данные алгоритма

Входные данные: Массив чисел (или других объектов, для которых определено сравнение), например: A = [5,3,8,4,2]

Выходные данные: Отсортированный массив: A = [2,3,4,5,8]

Свойства алгоритма

  • Сложность: В худшем случае O(n2), в среднем O(nlogn).
  • Устойчивость: Алгоритм неустойчив — элементы с одинаковыми значениями могут менять свой порядок.
  • Память: Работает на месте, не требуя дополнительной памяти.
  • Параллельность: Хорошо поддаётся параллельной реализации с использованием многозадачности для рекурсивных вызовов.

Программная реализация алгоритма

Особенности реализации последовательного алгоритма

Алгоритм QuickSort может быть реализован как в последовательной, так и в параллельной версиях. В основе алгоритма лежит стратегия, где массив делится на два подмассива относительно опорного элемента (pivot), и затем рекурсивно сортируются эти подмассивы.

В простейшей последовательной версии алгоритма QuickSort, как правило, используется следующая логика:

  1. Выбирается опорный элемент (например, средний элемент массива).
  2. Массив разделяется на два подмассива: элементы, меньшие опорного, и элементы, большие опорного.
  3. Рекурсивно сортируются эти два подмассива, пока каждый из них не станет отсортированным.

Пример последовательной реализации (без параллельности): 

   void quicksort(int *arr, int left, int right) {
       int i = left, j = right;
       int pivot = arr[(left + right) / 2];
       int temp;
       while (i <= j) {
           while (arr[i] < pivot) i++;
           while (arr[j] > pivot) j--;
            if (i <= j) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++; 
                j--;
           }
       }
       if (left < j) quicksort(arr, left, j);  // Рекурсивно сортируем левую часть
       if (i < right) quicksort(arr, i, right);  // Рекурсивно сортируем правую часть
   }


Параллельная реализация алгоритма

Для увеличения производительности на многозадачных системах, таких как суперкомпьютеры, можно параллелить рекурсивные вызовы алгоритма QuickSort. Параллельная версия алгоритма QuickSort будет разделять массивы и обрабатывать их в несколько потоков на высоких уровнях рекурсии, используя директивы OpenMP.

В приведенном ниже коде используется условие, что параллельные задачи создаются только для рекурсивных вызовов, где размер подмассива больше заданного порога THRESHOLD. Это позволяет избежать излишних накладных расходов на параллельную обработку маленьких подмассивов. 


   #include <stdio.h>
   #include <stdlib.h>
   #include <omp.h>
   #define THRESHOLD 10000  // Минимальный размер подмассива для параллелизации
   void quicksort(int *arr, int left, int right, int depth) {
       int i = left, j = right;
       int pivot = arr[(left + right) / 2];
       int temp;
       while (i <= j) {
           while (arr[i] < pivot) i++;
           while (arr[j] > pivot) j--;
           if (i <= j) {
               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
               i++; 
               j--;
           }
       }
       // Последовательная сортировка мелких подмассивов
       if (right - left < THRESHOLD) {
           if (left < j) quicksort(arr, left, j, depth + 1);
           if (i < right) quicksort(arr, i, right, depth + 1);
       }
       else {
           // Параллельные ветви создаются только на верхних уровнях
           #pragma omp task shared(arr) if (depth < 4)
           quicksort(arr, left, j, depth + 1);
           #pragma omp task shared(arr) if (depth < 4)
           quicksort(arr, i, right, depth + 1);
       }
       }
       int main() {
       int n = 1000000000;  // Размер массива
       int *arr = malloc(n * sizeof(int));
       if (!arr) {
          printf("Memory allocation failed!\n");
          return 1;
       }
       // Заполнение массива случайными числами
       for (int i = 0; i < n; i++)
           arr[i] = rand();
       double start = omp_get_wtime();  // Начало замера времени
       // Запуск параллельного выполнения с использованием OpenMP
       #pragma omp parallel
       {
           #pragma omp single
           quicksort(arr, 0, n - 1, 0);
       }
       double end = omp_get_wtime();  // Конец замера времени
       printf("Elapsed time: %.4f seconds\n", end - start);  // Вывод времени выполнения
       free(arr);  // Освобождение памяти
       return 0;
       }

Описание параллельных аспектов реализации

В данном коде используются директивы OpenMP:

  • #pragma omp parallel: инициирует параллельное выполнение с использованием нескольких потоков.
  • #pragma omp task: создаёт параллельные задачи для сортировки левой и правой части массива на каждом уровне рекурсии. Задачи создаются только для рекурсии на уровнях, где глубина рекурсии меньше 4 (это значение можно подбирать и настраивать).
  • #pragma omp single: гарантирует, что только один поток будет выполнять начальный вызов quicksort, в то время как остальные потоки выполнят задачи параллельно.

Результаты и оценка производительности

Литература

  1. Cormen, T. H. , Leiserson, C. E. , Rivest, R. L. , Stein, C. (2009). Introduction to Algorithms. MIT Press.
  2. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
  3. Hoare, C. A. R. (1961). Quicksort. Computer Journal, 5(1), 10-15.
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Участник:Yaselivoxin/Алгоритм&oldid=30018