Быстрая сортировка

Алгоритмы сортировки и поиска / Быстрая сортировка

 

Быстрая сортировка представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой.

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

Тем самым массив разбивается на две части:

  • не отсортированные элементы слева от разрешающего элемента;
  • не отсортированные элементы справа от разрешающего элемента.

Чтобы отсортировать эти два меньших подмассива, алгоритм рекурсивно вызывает сам себя.

Если требуется сортировать больше одного элемента, то нужно

  • выбрать в массиве разрешающий элемент;
  • переупорядочить массив, помещая элемент на его окончательное место;
  • отсортировать рекурсивно элементы слева от разрешающего;
  • отсортировать рекурсивно элементы справа от разрешающего.

Ключевым элементом быстрой сортировки является алгоритм переупорядочения.

Рассмотрим сортировку на примере массива:

10, 4, 2, 14, 67, 2, 11, 33, 1, 15.

Для реализации алгоритма переупорядочения используем указатель left на крайний левый элемент массива. Указатель движется вправо, пока элементы, на которые он показывает, остаются меньше разрешающего. Указатель right поставим на крайний правый элемент массива, и он движется влево, пока элементы, на которые он показывает, остаются больше разрешающего.

Пусть крайний левый элемент — разрешающий pivot. Установим указатель left на следующий за ним элемент; right — на последний. Алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы.
Быстрая сортировка
Движение указателей останавливается, как только встречаются элементы, порядок расположения которых относительно разрешающего элемента неправильный.

Указатель left перемещается до тех пор, пока не покажет элемент больше 10; right движется, пока не покажет элемент меньше 10.

Быстрая сортировка
Эти элементы меняются местами и движение указателей возобновляется.

Быстрая сортировка
Процесс продолжается до тех пор, пока right не окажется слева от left.

Быстрая сортировка
Тем самым будет определено правильное место разрешающего элемента.

Осуществляется перестановка разрешающего элемента с элементом, на который указывает right.
Переустановка разрешающего элемента

Разрешающий элемент находится в нужном месте: элементы слева от него имеют меньшие значения; справа — большие. Алгоритм рекурсивно вызывается для сортировки подмассивов слева от разрешающего и справа от него.

Реализация алгоритма быстрой сортировки на Си

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
#include <stdlib.h>
#define SIZE 20
// Функция быстрой сортировки
void quickSort(int *numbers, int left, int right)
{
  int pivot; // разрешающий элемент
  int l_hold = left; //левая граница
  int r_hold = right; // правая граница
  pivot = numbers[left];
  while (left < right) // пока границы не сомкнутся
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--; // сдвигаем правую границу пока элемент [right] больше [pivot]
    if (left != right) // если границы не сомкнулись
    {
      numbers[left] = numbers[right]; // перемещаем элемент [right] на место разрешающего
      left++; // сдвигаем левую границу вправо
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++; // сдвигаем левую границу пока элемент [left] меньше [pivot]
    if (left != right) // если границы не сомкнулись
    {
      numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
      right--; // сдвигаем правую границу влево
    }
  }
  numbers[left] = pivot; // ставим разрешающий элемент на место
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива
    quickSort(numbers, left, pivot - 1);
  if (right > pivot)
    quickSort(numbers, pivot + 1, right);
}
int main()
{
  int a[SIZE];
  // Заполнение массива случайными числами
  for (int i = 0; i<SIZE; i++)
    a[i] = rand() % 201 - 100;
  // Вывод элементов массива до сортировки
  for (int i = 0; i<SIZE; i++)
    printf("%4d ", a[i]);
  printf("\n");
  quickSort(a, 0, SIZE-1); // вызов функции сортировки
            // Вывод элементов массива после сортировки
  for (int i = 0; i<SIZE; i++)
    printf("%4d ", a[i]);
  printf("\n");
  getchar();
  return 0;
}

Результат выполнения
Результат быстрой сортировки

Еще по теме:


Назад: Алгоритмы сортировки и поиска

Комментариев к записи: 49


  • В строке 28 вы меняете элемент numbers[left] = на pivot, при этом не сохраняя значение которое было в numbers[left], получается, что вы копировали элемент, который находился в начале входного массива, на место numbers[left], а сам numbers[left] попросту исчез

    • Елена Вставская
      Элемент из numbers[left] уже помещен на нужное место в предыдущем цикле.

  • Добрый день. А подскажите можно так же само например буквы (или разные символы) чтоб отсортировало по порядку? К примеру вводим: W4AH5ВD1 должно отсортировать:ABDHW145

    • Елена Вставская
      Каждый символ имеет свой числовой код. Поэтому метод сортировки не изменится

  •  Александр
    Алгоритм корявый и и не универсальный, потому что pivot используется как индекс массива и значение элементов массива, а они не обязаны быть одинаковых типов. Как только поменять тип элементов массива все сломается.

    • Елена Вставская
      Можно просто до 29 строчки взять другую переменную для работы с элементами массива

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include<bits/stdc++.h>

    auto qsort(std::vector<int> A)
    {
        if(A.empty())
            return A;
        std::vector<int> p, mn, mx;
        p.push_back(A[A.size()-1]);
        A.pop_back();
        for(int i=0; i<A.size(); i++)
            if(A[i]<p[0])
                mn.push_back(A[i]);
            else
                mx.push_back(A[i]);
        std::vector<int>A1,A2;
        A1=qsort(mn);
        A2=qsort(mx);
        A1.insert(A1.end(),p.begin(),p.end());
        A1.insert(A1.end(),A2.begin(),A2.end());
        return A1;
    }

    int main()
    {
        std::vector<int> Am;
        int am;
        std::cin>>am;
        for(int i = 0; i < am; i++)
            Am.push_back(rand() % 20000);
        Am=qsort(Am);
        for(int i=0; i<am; i++)
            std::cout<<Am[i]<<" ";
    }

    • Делал только по описанию принципа работы алгоритма как упражнение, так что работает и уже хорошо

  • Классический рекурсивный алгоритм быстрой сортировки, переработанный под функцию main из учебного примера.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #include <stdio.h>
    #include <stdlib.h>
    #define SIZE 20

    void qsort (int* arr, int left, int right)
    {
        int i = left, j = right;
        int temp, pivot = arr[ (left+right)/2 ];

        while (i <= j)
        {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;

            if (i <= j)
            {
                if (arr[i] > arr[j])
                {
                    temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
                }

                i++; j--;
            }

        };

        if (left < j) qsort (arr, left, j);
        if (i < right) qsort (arr, i, right);
    }

    //-------------------------------------------------------------------

    int main()
    {
        int Arr[SIZE];

        // Заполнение массива случайными числами
        for (int i = 0; i<SIZE; i++) Arr[i] = rand()%100;

        // Вывод элементов массива до сортировки
        for (int i = 0; i<SIZE; i++) printf("%3d ", Arr[i]); printf("\n");

        qsort(Arr, 0, SIZE-1); // вызов функции сортировки

        // Вывод элементов массива после сортировки
        for (int i = 0; i<SIZE; i++) printf("%3d ", Arr[i]); printf("\n");

        getchar(); return 0;
    }


  • Мне кажется код не совсем корректен. Например, на строке 17. В начале цикла вы установили pivot как нулевой элемент массива, а затем вы нулевой элемент меняете с правым, который сравнили с pivot. А надо брать тот элемент, который получился в результате сравнения слева left++ с pivot. А дальше какие-то костыли. Странно, что сортирует

    • я считаю что необязательно делать проверку на то то српава елементы будут больше это тупо так как вы и так в начале цикла будете знать что справа будут елементы больше надо просто сделать счетчик сдвига и проблем с массивом не будет

  • Евгений
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    void sort(int* nums, int begin, int end)
    {
        int l = begin, r = end;
        int v = nums[l+(r-l)/2];
        while(l <= r)
        {
            while(nums[l] < v) l++;
            while(nums[r] > v) r--;
            if(l <= r)
            {
                int tmp = nums[l];
                nums[l] = nums[r];
                nums[r] = tmp;
                l++, r--;
            }
        }
        if(begin < r)
            sort(nums, begin, r);
        if(l < end)
            sort(nums, l, end);
    }


    • Самый лучший вариант алгоритма. Vlavla, строка 9 нужна. Когда вышестоящие циклы заканчивают свою работу, получается r > l, а это знак, что ничего перемещать не надо. Автору сей статьи не мешало бы заменить своё псевдотворчество на этот нормальный код. Как минимум потому - что код автора не согласуется с алгоритмом, который автор же и написала в начале своего опуса.


    • Елена Вставская
      Потому что pivot уже стоит на месте, и нужно вызвать сортировку строго для элементов, которые слева и которые справа от pivot

  • Здравствуйте! Реализовал Ваш алгортим сортировки, в надежде что он действительно быстрый. Оказалось что нет. На массиве в 15 000 000 эл., сортирует 223 секунды. В интернете нашел другой алгоритм, который данное количество элементов, сортирует за 30 секунд.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    int partition2(std::vector<int>& vector, int lo, int hi)
    {
      int i = lo;
      int j = hi + 1;

      while (true)
      {
        while (vector[++i] < vector[lo])
        {
          if (i == hi) break;
        }

        while (vector[--j] > vector[lo])
        {
          if (j == lo)
          {
            break;
          }
        }

        if (i >= j)
        {
          break;
        }

        std::swap(vector[i], vector[j]);
      }

      std::swap(vector[lo], vector[j]);

      return j;
    }

    void quickSort2(std::vector<int>& vector, int lo, int hi)
    {
      if (hi <= lo) return;

      int j = partition2(vector, lo, hi);

      quickSort2(vector, lo, j - 1);
      quickSort2(vector, j + 1, hi);
    }

    • Ну конечно быстрее, ведь использует распараллеливание с помощью SIMD

      • Вячеслав
        А такой код не хотите? )) массив из 15 млн. чисел за 22 секунды на компе 15-ти летней давности (с памятью еще DDR2)!
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42

        ! qsort_reals.f90 --
        !
        !  Example belonging to "Modern Fortran in Practice"
        !  by Arjen Markus
        !
        !  This work is licensed under the 
        !  Creative Commons Attribution 3.0 Unported License.
        !  To view a copy of this license, 
        !  visit http://creativecommons.org/licenses/by/3.0/
        !  or send a letter to:
        !  Creative Commons, 444 Castro Street, Suite 900, 
        !  Mountain View, California, 94041, USA.
        !
        !  Compact implementation of the QuickSort algorithm
        !
        !  Note:
        !  Because the function uses Fortran 90 features, 
        !  its interface should be made
        !  explicit when using it in an actual program. 
        !  This is easiest via a module.
        !
        module qsort_functions
        implicit none
        contains
        recursive function qsort_reals( data ) result( sorted )
            real, dimension(:), intent(in) :: data
            real, dimension(1:size(data))  :: sorted
         
            if ( size(data) > 1 ) then
                sorted = &
                (/ qsort_reals( pack( data(2:), data(2:) > data(1) ) ), &
                data(1),                                                &
                qsort_reals( pack( data(2:), data(2:) <= data(1) ) ) /)
            else
                sorted = data
            endif
            
        end function qsort_reals
        end module qsort_functions


        ps В любом случае Елене почтение за статью.

  • Строка 29 pivot = left; ... Строка 32 if(pivot < left)... - т.е. никогда не исполняется Pivot- значение элемента массива, left индекс. Если бы массив не был целочисленным, то присвоение и сравнения были бы не совсем корректными. Где-то ошибка.

    • Ошибся есть ещё строка 30, но по присвоениям и сравнениям по моему ошибка

  • Кажется данная реализация слишком многословно. Думаю, стоит быть более функциональным.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    const quick_sort = array => {
        
        if (array.length < 2) 
            return array;

        const pivot = array.filter(e => e === array[0]); 
        const greater = array.filter(e => e < array[0]);
        const less = array.filter(e => e > array[0]);

        return [...quick_sort(less), ...pivot, ...quick_sort(greater)];

    };




        • Елена Вставская
          Потому что нумерация элементов начинается с 0, а нам нужно указать индекс последнего элемента


    • Елена Вставская
      Сохраняем значения левой и правой границ, которые были переданы в функцию

  • Большое спасибо за доступные разъяснения! И особенно за построчные комментарии. Очень быстро разобралась после того как нашла Вашу статью


    • Елена Вставская
      Нужно определиться, по какому ключу ведётся сортировка (например, по первому элементу строк). При этом в операции обмена менять местами не только ключевые элементы, но и все элементы строк с ключевыми элементами. Для последней операции придется использовать цикл.


  • По сути это та же сортировка деревом, только дерево неявно строится в стеке за счёт рекурсии. Большая сложность, зависимость от размера стека, но экономия места скорости за счёт отсутствия динамического выделения памяти.


    • Елена Вставская
      Специально запустила программу еще раз для 20 и 30 элементов и заменила скриншот на сайте, чтоб показать, что код работает

  • Какой толк от условия (14 строка): if (left != right) // если границы не сомкнулись { numbers[left] = numbers[right]; // перемещаем элемент [right] на место разрешающего left++; // сдвигаем левую границу вправо } если у while условие (left < right)

    • Елена Вставская
      После проверки условия while в строке 10 right смещался. Поэтому необходима дополнительная проверка.


    • Елена Вставская
      Поменять условия сравнения numbers[...] и pivot в строках 12 и 19 на противоположные


  • Почему описание алгоритма отличается от примера программы, как земля от неба?

    • Елена Вставская
      Я не вижу таких колоссальных отличий, поэтому можно поподробнее, где Вы их нашли?

      • Дмитрий
        Здравствуйте Елена. Попытался поправить код и алгоритм к нему. Вотссылка:https://drive.google.com/file/d/1w90IrLURoTPZ8KYBM8vie8E1qWTe06U_/view?usp=sharing

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *