Изменения

Перейти к: навигация, поиск

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

411 байт добавлено, 23:18, 12 июня 2016
Алгоритм
==Алгоритм==
* из массива выбирается некоторый опорный элемент Массив <tex> A[l \ldots r]</tex> разбивается на два (возможно пустых) подмассива <tex> A[l \ldots q-1]</tex> и <tex>A[iq+1 \ldots r]</tex>.* запускается процедура разделения массива, которая перемещает все ключитаких, меньшие, либо равные что каждый элемент <tex> A[l \ldots q-1]</tex> меньше или равен <tex>A[iq]</tex>, влево от негокоторый в свою очередь, а все ключи, большие, либо равные не превышает любой элемент подмассива <tex>A[iq+1 \ldots r]</tex> {{. Индекс вычисляется в ходе процедуры разбиения.* Подмассивы <tex> A[l \ldots q---}} вправо1]</tex> и <tex> A[q+1 \ldots r]</tex> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.* Поскольку подмассивы сортируются на месте, для обоих подмассивових объединения не требуются никакие действия: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.весь массив <tex> A[l \ldots r]</tex> оказывается отсортированным.
==Псевдокод==
635
правок

Навигация