Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Быстрая сортировка алгоритм и примеры онлайн кратко

Лекция



Привет, сегодня поговорим про быстрая сортировка, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое быстрая сортировка , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом « быстрая сортировка » (также «qsort» от англ. quick sort). Его разработал в 1960 году английский ученый Чарльз Хоар, занимавшийся тогда в МГУ машинным переводом. Алгоритм, по принципу функционирования, входит в класс обменных сортировок (сортировка перемешиванием, пузырьковая сортировка и др.), выделяясь при этом высокой скоростью работы.

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

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

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

Разбиение массива

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

В следующих четырех пунктах описан околопрограммный процесс разбиения массива (сортировка по возрастанию):

  1. вводятся переменные first и last для обозначения начального и конечного элементов последовательности, а также опорный элемент mid;
  2. по формуле (first+last)/2 вычисляется значение среднего элемента, и заноситься в переменную mid;
  3. значения элементов поочередно проверяются на их соответствие позиции, в которой они находятся, то есть элементы левой и правой частей сравниваются с опорным элементом, и если оказывается, что некоторые элементы Mas[i] (левее опорного) и Mas[j] (правее опорного) стоят не на своих позициях, то они меняются местами.
  4. шаг 3 продолжает выполняться до тех пор, пока все элементы не встанут на свои места относительно опорного элемента (это ни в коем случае не означает, что по окончанию обменов массив будет отсортирован).

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

Исходный массив:

Быстрая сортировка алгоритм и примеры онлайн

Данный массив (назовем его Mas) состоит из 8 элементов: Mas[1..8]. Начальным значением first будет 1, а last – 8. Пройденная часть закрашивается голубым цветом.

Быстрая сортировка алгоритм и примеры онлайн

В качестве опорного возьмем элемент со значением 5, и индексом 4. Его мы вычислили по формуле (first+last)/2, отбросив дробную часть. Теперь mid=5.

Быстрая сортировка алгоритм и примеры онлайн

Далее, первый элемент левой части сравнивается с mid: 3 меньше 5, поэтому он остается на своем месте, а first увеличивается на 1. Таким же образом проверяется элемент с индексом 2 и значением 7. Так как значение второго элемента превышает значение mid, он запоминается, а first остается равным 2. Наступает очередь аналогичной проверки правой части.

Правая часть проверяется с конца. Значения первых двух элементов (они имеют индексы 7 и 8) больше значения опорного элемента, но для третьего это не верно, т. к. 1<5. Элемент запоминается, проверка правой части на некоторое время приостанавливается. Сейчас last равен 6.

Быстрая сортировка алгоритм и примеры онлайн

На следующем шаге происходит перестановка. Как мы помним, first=2, а last=6, следовательно, элементами, требующими рокировки, являются Mas и Mas .

Тем же способом продолжим проверку оставшихся частей массива до тех пор, пока условие first

Быстрая сортировка алгоритм и примеры онлайн

На этом этап разбиения закончен: массив разделен на две части относительно опорного элемента. Осталось произвести рекурсивное упорядочивание его частей.

Открыть на весь экран

Рекурсивное доупорядочивание

Если в какой-то из получившихся в результате разбиения массива частей находиться больше одного элемента, то следует произвести рекурсивное упорядочивание этой части, то есть выполнить над ней операцию разбиения описанную выше. Для проверки условия «количество элементов > 1», нужно действовать примерно по следующей схеме:

Имеется массив Mas[L..R], где L и R – индексы крайних элементов этого массива. По окончанию разбиения, указатели first и last оказались примерно в середине последовательности, тем самым образую два отрезка: левый от L до last и правый от first до R. Проверить такие отрезки на заданное условие не составит труда.

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

Код программы на C++:

  1. #include "stdafx.h"
  2. #include
  3. #include
  4. using namespace std;
  5. const int n=7;
  6. int first, last;
  7. //функция сортировки
  8. void quicksort(int *mas, int first, int last)
  9. {
  10. int mid, count;
  11. int f=first, l=last;
  12. mid=mas[(f+l) / 2]; //вычисление опорного элемента
  13. do
  14. {
  15. while (mas[f]<mid) f++;
  16. while (mas[l]>mid) l--;
  17. if (f<=l) //перестановка элементов
  18. {
  19. count=mas[f];
  20. mas[f]=mas[l];
  21. mas[l]=count;
  22. f++;
  23. l--;
  24. }
  25. } while (f<l);
  26. if (first<l) quicksort(mas, first, l);
  27. if (f<last) quicksort(mas, f, last);
  28. }
  29. //главная функция
  30. void main()
  31. {
  32. setlocale(LC_ALL,"Rus");
  33. int *A=new int[n];
  34. srand(time(NULL));
  35. cout<<"Исходный массив: ";
  36. for (int i=0; i<n; i++)
  37. {
  38. A[i]=rand()%10;
  39. cout<<A[i]<<" ";
  40. }
  41. first=0; last=n-1;
  42. quicksort(A, first, last);
  43. cout<<endl<<"Результирующий массив: ";
  44. for (int i=0; i<n; i++) cout<<A[i]<<" ";
  45. delete []A;
  46. system("pause>>void");
  47. }

Код программы на Pascal:

  1. program qsort;
  2. uses crt;
  3. const n=7;
  4. var A: array[1..n] of integer;
  5. first, last, i: integer;
  6. {процедура сортировки}
  7. procedure quicksort(var mas: array[1..n] of integer; first, last: integer);
  8. var f, l, mid, count: integer;
  9. begin
  10. f:=first;
  11. l:=last;
  12. mid:=mas[(f+l) div 2]; {вычисление опорного элемента}
  13. repeat
  14. while mas[f]do inc(f);
  15. while mas[l]>mid do dec(l);
  16. if f<=l then {перестановка элементов}
  17. begin
  18. count:=mas[f];
  19. mas[f]:=mas[l];
  20. mas[l]:=count;
  21. inc(f);
  22. dec(l);
  23. end;
  24. until f>l;
  25. if firstthen quicksort(A, first, l);
  26. if fthen quicksort(A, f, last);
  27. end;
  28. {основной блок программы}
  29. begin
  30. clrscr;
  31. randomize;
  32. write('Исходный массив: ');
  33. for i:=1 to n do
  34. begin
  35. A[i]:=random(10);
  36. write(A[i]:2);
  37. end;
  38. first:=1; last:=n;
  39. quicksort(A, first, last);
  40. writeln; write('Результирующий массив: ');
  41. for i:=1 to n do
  42. write(A[i]:2);
  43. end.

Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. Об этом говорит сайт https://intellect.icu . В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.

Вау!! 😲 Ты еще не читал? Это зря!

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

создано: 2014-11-30
обновлено: 2021-07-20
132519



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов