СтатьиСтатьи об алгоритмах программирования

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

Этот один из самых быстрых алгоритмов сортировки, получил свое название от стандартной библиотеки языка Си – quicksort. Он был разработан английским информатиком Чарльзом Хаором в 1960 году.

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

Механизм работы алгоритма заключается в следующем:

- выбор опорного элемента – это может быть произвольный элемент массива, от которого зависит дальнейшая эффективность алгоритма;

- сравнение элементов массива с опорным элементом, размещая в двух группах, выбирая значения больше опорного элемента или меньше;

- повторение предыдущих операций для каждой группы элементов;

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

const
N = 10; // размер массива

type
TMas = array[1..N] of Integer; // создание типа данных массив *

var
mas : TMas; // создание массива

procedure sort(var mas : TMas; low, high: integer);
var
i, j, k, h: integer;
begin
i := low;
j := high;
k := mas[(i + j) div 2]; // средний элемент в массиве берется в качестве опорного

repeat
// если в этих условиях заменить знаки сравнения на обратные, будет выполняться сортировка по убыванию
while mas[i] < k do i := i + 1;
while mas[j] > k do j := j - 1;

if i <= j then begin // замена элементов местами
h := mas[i];
mas[i] := mas[j];
mas[j] := h;
i := i + 1
j := j + 1
end;
until i > j;

// рекурсивный вызов процедуры сортировки для частей массива
if low < j then
sort(mas, low, j);
if i < high then
sort(mas, i, high);
end;

begin
sort(mas, Low(mas), High(mas)); // основной вызов процедуры сортировки
end;

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


Комментарии

Имя:
Текст комментария:
* В комментариях запрещено публиковать рекламные объявления. Сообщения, содержащие ссылки на сторонние ресурсы добавляется в скрытом режиме. Они будут открыты, если не нарушают установленных правил, после проверки.
Защита от спам-роботов (* Обязателельно укажите ответ на простой вопрос ниже.)
Сумма чисел двa плюc тpи? (цифра)