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

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

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

Один из самых быстрых известных универсальных алгоритмов сортировки. В среднем O(n log(n)) обменов при упорядочивании n элементов.

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

  1. Выбирается элемент каким-либо образом. Существуют разные способы выбора элемента, но алгоритм работает с любым выбранным элементом. Это может быть самый первый, либо самый последний элемент массива, либо элемент где-то посередине. Этот элемент называется опорным.
  2. Элементы в массиве перемещаются так, что элементы меньше опорного оказываются слева от него, а элементы больше опорного — справа.
  3. К подмассивам слева и справа от опорного применяются первые два шага, если в этих подмассивах больше одного элемента.

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

Реализуем этот алгоритм на Java.

Внимание! Не стоит реализовывать этот алгоритм в реальных проектах. Всегда используйте готовые алгоритмы сортировки коллекций и готовые алгоритмы из класса java.util.Arrays.

Код на Java:

Main.java — пример реализации алгоритма быстрой сортировки на Java import java.util.Arrays;/** * Пример обучающей программы с реализацией быстрой сортировки Quicksort * @see https://urvanov.ru */public class Main {     public static void main(String [] args) {        int [][] array1 = {                {9, 0, -2, 89, 1, 2, 3, -3, -99, 6},                {5, 3, 1, 2, 2, 1, 0},                {1, 1},                {3, 1, 1},                {2, 1, 1, 2, 1, 2},                {2, 5, 3, 1},                {-1, 3, 2, 4, 0, 1},                {-1, 0}                };        sortAndPrintln(array1);    }        public static void sortAndPrintln(int[][] array1) {        for (int n = 0; n < array1.length; n++) {            quicksort(array1[n], 0, array1[n].length - 1);            System.out.println(Arrays.toString(array1[n]));        }    }         /**     * Реализуем алгоритм быстрой сортировки     * @param array1 Массив, в котором нужно упорядочить элементы.     * @param startIndex Начальный индекс в массиве (включая).     * @param endIndex Конечный индекс в массиве (не включая)     */    public static void quicksort(int[] array1, int startIndex, int endIndex) {        int pivotValue = getPivot(array1, startIndex, endIndex);        int currentStartIndex = startIndex;        int currentEndIndex = endIndex;                while (currentStartIndex < currentEndIndex) {            while (array1[currentStartIndex] < pivotValue) {                currentStartIndex++;            }             while ((array1[currentEndIndex] > pivotValue) && (currentEndIndex > currentStartIndex)) {                currentEndIndex—;            }            if (currentStartIndex < currentEndIndex) {                swap(array1, currentStartIndex, currentEndIndex);                if (currentEndIndex - currentStartIndex > 1) {                    currentStartIndex++;                    currentEndIndex—;                } else {                    break;                }            }        }        if ((currentStartIndex > startIndex)                && (currentStartIndex — startIndex > 1))            quicksort(array1, startIndex, currentStartIndex);        if ((endIndex > currentEndIndex)                && (endIndex — currentEndIndex > 1))            quicksort(array1, currentEndIndex , endIndex);    }            /**     * Меняет местами элементы массива с индексами index1 и index2.     * @param array1 Массив.     * @param index1 Индекс элемента 1.     * @param index2 Индекс элемента 2.     */    private static void swap(int[] array1, int index1, int index2) {        int buffer = array1[index1];        array1[index1] = array1[index2];        array1[index2] = buffer;    }            /**     *      * @param array1     * @param lowIndex     * @param highIndex     * @return Значение опорного элемента. В этой реализации опорный элемент —     *  это последний элемент в массиве.     */    public static int getPivot(int[] array1, int startIndex, int endIndex) {        return array1[endIndex — 1];    }}

 * Пример обучающей программы с реализацией быстрой сортировки Quicksort * @see https://urvanov.ru    public static void main(String [] args) {                {9, 0, -2, 89, 1, 2, 3, -3, -99, 6},    public static void sortAndPrintln(int[][] array1) {        for (int n = 0; n startIndex)                && (currentStartIndex — startIndex > 1))            quicksort(array1, startIndex, currentStartIndex);        if ((endIndex > currentEndIndex)                && (endIndex — currentEndIndex > 1))            quicksort(array1, currentEndIndex , endIndex);     * Меняет местами элементы массива с индексами index1 и index2.     * @param index1 Индекс элемента 1.     * @param index2 Индекс элемента 2.    private static void swap(int[] array1, int index1, int index2) {        int buffer = array1[index1];        array1[index1] = array1[index2];     * @return Значение опорного элемента. В этой реализации опорный элемент —     *  это последний элемент в массиве.    public static int getPivot(int[] array1, int startIndex, int endIndex) {        return array1[endIndex — 1];

Достоинства алгоритма:

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

Недостатки:

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

Вас также может заинтересовать сортировка слиянием и сортировка вставками.

Весь  код выложен в репозиторий на GitHub (ставьте звёздочки).

Ещё записи из этой рубрики:

  • Lombok @Getter и @Setter — больше не нужно писать геттеры и сеттеры
  • A collection with cascade=”all-delete-orphan” was no longer referenced by the owning entity instance
  • Unit-тесты с Joda-Time
  • Java 8 файлы (NIO.2)
  • Иерархия классов java.io.OutputStream
  • Java 8 локализация
  • Lombok. Упрощение Java кода.
  • Правила (Rules) в JUnit 4
  • Синглетон (одиночка) в Java
  • Java 8 ещё раз о перегрузке методов

Источник: https://urvanov.ru/2017/08/19/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B9-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-quicksort/

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

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

Быстрая сортировка си, итеративная быстрая сортировка, рекурсивная быстрая сортировка, bolts and nuts

Алгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за n·log(n) шагов. В худшем случае сложность опускается до порядка n2, хотя такая ситуация довольно редкая.

Быстрая сортировка обычно быстрее других «скоростных» сортировок со сложностью порядка n·log(n). Быстрая сортировка не устойчивая.

Обычно, она преподносится как рекурсивная, однако, может быть с помощью стека (возможно, и без него, не проверено) сведена к итеративной, при этом потребуется не более n·log(n) дополнительной памяти.

Начнём с задачи, которую обычно называют Bolts & Nuts (Болты и Гайки). Вы пошли в магазин и купили болтов и гаек, много, целых два ведра. В одном ведре болты, в другом гайки.

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

Вы можете сравнить только гайку с болтом и болт гайкой и проверить, подходят они друг другу или нет. Задача — найти для каждой гайки соответствующий ей болт.

Пусть у нас n пар болт-гайка. Самое простое решение — «в лоб» — берём гайку и находим для неё болт. Всего надо будет проверить n болтов. Поле этого берём вторую гайку,находим для неё болт, предстоит сделать уже n-1 проверку. И так далее. Всего надо будет сделать n + (n-1) + (n-2) + … + 1 = n2/2 шагов. Существует ли более простое решение?

Самое быстрое (из известных мне) решение не самое очевидное. Применим подход «разделяй и властвуй». Если множество, которое мы хотим обработать слишком большое, то разобьём его на более мелкие и применим рекурсивно наш алгоритм к каждому из них. В конце концов, когда данных будет немного, обработаем и обратно соберём их вместе.

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

Таким образом мы получим две кучи гаек — те, которые больше и те, которые меньше. С помощью найденной гайки разобьём все болты на те, которые меньше, и те, которые больше, чем первоначальный болт.

Получим две кучи болтов, мелкие и крупные.

Далее, из кучи мелких болтов выберем случайный болт и с его помощью разобьём кучу гаек (тех, которые мелкие) на две кучи. Во время разбиения найдём подходящую гайку, с помощью которой разобьём мелкие болты на две кучи и т.д. То же самое проделаем и с большей кучей. Рекурсивно будем применять этот алгоритм к каждой «подкуче». Таким образом, предстоит сделать порядка n·log(n) шагов.

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

Далее разобьём множество на три — элементы, которые больше опорного, равны ему и элементы, которые меньше.

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

Рекурсивное решение

Функция принимает в качестве аргументов массив и левую и правую границу массива. В самом начале левая граница это 0, а правая — длина массива минус один. Нам понадобятся следующие переменные

size_t i, j;

указывают на левый и правый элементы,

int tmp, pivot;

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

i = low;j = high;pivot = a[(low + (high-low)/2)];

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

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

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

Пока i будет меньше j (пока они не пересекутся) делаем следующее. Во первых, нужно пропустить все уже отсортированные элементы

do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j—; }

Далее, если границы ещё не пересеклись, то в случае, если порядок нарушен, то следует обменять местами переменные, после чего опять инкрементировать i и декрементировать j, чтобы не зациклиться.

if (i a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; j—; }} while (i 0) { j—;}

После этого цикла i и j пересекутся, i станет больше j и мы получим ещё два массива, для которых следует применить сортировку: массив от левой границы до i, и массив от j до правой границы, если, конечно, мы не вышли за пределы границ.

if (i < high) { qsortx(a, i, high);}if (j > low) { qsortx(a, low, j);}

Весь код

void qsortx(int *a, size_t low, size_t high) { size_t i, j; int tmp, pivot; i = low; j = high; pivot = a[(low + (high-low)/2)]; do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j—; } if (i a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; if (j > 0) { j—; } } } while (i low) { qsortx(a, low, j); }}

Функция называется qsortx, чтобы не спутать со стандартной функцией быстрой сортировки qsort.

Итеративное решение

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

void qsortxi(int *a, size_t size) { size_t i, j; int tmp, pivot; Stack *lows = createStack(); Stack *highs = createStack(); size_t low, high; push(lows, 0); push(highs, size — 1); while (lows->size > 0) { low = pop(lows); high = pop(highs); i = low; j = high; pivot = a[(low + (high-low)/2)]; do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j—; } if (i a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; if (j > 0) { j—; } } } while (i low) { push(lows, low); push(highs, j); } } freeStack(&lows); freeStack(&highs);}

Код стека

#define STACK_INIT_SIZE 100 typedef struct Stack { size_t size; size_t limit; int *data;} Stack; Stack* createStack() { Stack *tmp = (Stack*) malloc(sizeof(Stack)); tmp->limit = STACK_INIT_SIZE; tmp->size = 0; tmp->data = (int*) malloc(tmp->limit * sizeof(int)); return tmp;} void freeStack(Stack **s) { free((*s)->data); free(*s); *s = NULL;} void push(Stack *s, int item) { if (s->size >= s->limit) { s->limit *= 2; s->data = (int*) realloc(s->data, s->limit * sizeof(int)); } s->data[s->size++] = item;} int pop(Stack *s) { if (s->size == 0) { exit(7); } s->size—; return s->data[s->size];}

Функция в общем виде

void qsortxig(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) { size_t i, j; void *tmp, *pivot; Stack *lows = createStack(); Stack *highs = createStack(); size_t low, high; push(lows, 0); push(highs, size — 1); tmp = malloc(item); while (lows->size > 0) { low = pop(lows); high = pop(highs); i = low; j = high; pivot = (char*)a + (low + (high-low)/2)*item; do { while (cmp(((char*)a + i*item), pivot)) { i++; } while (cmp(pivot, (char*)a + j*item)) { j—; } if (i 0) { j—; } } } while (i low) { push(lows, low); push(highs, j); } } freeStack(&lows); freeStack(&highs); free(tmp);}

ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students

Q&A

Всё ещё не понятно? – пиши вопросы на ящик Сортировка вставками

Источник: https://learnc.info/algorithms/quicksort.html

ТОП-6 алгоритмов сортировки на Java для новичков

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

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

Задействование алгоритмов сортировки поможет нам упорядочить массивы Java. Для понимания: сортировка чисел от наименьшего к большему или наоборот, а также лексикографический порядок – это примеры алгоритмов сортировки, способные упорядочить Java строки и числа

Сортировка пузырьком

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

Алгоритм просматривает массив и сравнивает каждую пару соседних элементов. Когда он встречает пару элементов, расположенных не по порядку, происходит замена двух элементов местами.

Остается вопрос: как узнать, что все элементы упорядочены? В этом случае очередная итерация пройдет без замены соседних элементов.

Вот шаги для сортировки массива чисел от наименьшего к большему:

  • 4 2 1 5 3: два первых элемента расположены в массиве в неверном порядке. Меняем их.
  • 2 4 1 5 3: вторая пара элементов тоже «не в порядке». Меняем и их.
  • 2 1 4 5 3: а эти два элемента в верном порядке (4 < 5), поэтому оставляем как есть.
  • 2 1 4 5 3: очередная замена.
  • 2 1 4 3 5: результат после одной итерации.

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

Но причём тут пузырьки? Посмотрите снова на пример, и вы увидите, что алгоритм как бы смещается вправо. По этому поведению элементов в массиве и возникла аналогия с «пузырьками», всплывающими на «поверхность».

Реализация

Функция входит в цикл while, в котором проходит весь массив и меняет элементы местами при необходимости.

Массив в алгоритме считается отсортированным. При первой замене доказывается обратное и запускается еще одна итерация.

Цикл останавливается, когда все пары элементов в массиве пропускаются без замен:

public static void bubbleSort(int[] array) { boolean sorted = false; int temp; while(!sorted) { sorted = true; for (int i = 0; i < array.length - 1; i++) { if (array[i] > array[i+1]) { temp = array[i]; array[i] = array[i+1]; array[i+1] = temp; sorted = false; } } } }

Будьте осторожны с формулировкой условия замены!

Например, при условии a[i] >= a[i+1] алгоритм войдет в бесконечный цикл, потому что для равных элементов это условие остается true: отсюда следует бесконечная замена

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

Рассмотрим наихудший сценарий. Вот в чем вопрос: сколько итераций нужно для сортировки всего массива? Пример:

5 4 3 2 1

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

Расширьте это утверждение для массива из n элементов, и получите n итераций. В коде это означает, что цикл while будет запускаться максимум n раз.

Каждая n-ая итерация по всему массиву (цикл for в коде) означает, что временная сложность в наихудшем случае будет равна O(n 2).

Сортировка вставками

Этот алгоритм разделяет оригинальный массив на сортированный и несортированный подмассивы.

Длина сортированной части равна 1 в начале и соответствует первому (левому) элементу в массиве. После этого остается итерировать массив и расширять отсортированную часть массива одним элементом с каждой новой итерацией.

После расширения новый элемент помещается на свое место в отсортированном подмассиве. Это происходит путём сдвига всех элементов вправо, пока не встретится элемент, который не нужно двигать.

В приведенном ниже массиве жирная часть отсортирована в порядке возрастания. Посмотрите что произойдет в этом случае:

  • 3 5 7 8 4 2 1 9 6: выбираем 4 и помним, что это элемент, который нужно вставить. 8 > 4, поэтому сдвигаем.
  • 3 5 7 x 8 2 1 9 6: здесь x – нерешающее значение, так как элемент будет перезаписан (на 4, если это подходящее место, или на 7, если смещение). 7 > 4, поэтому сдвигаемся.
  • 3 5 x 7 8 2 1 9 6
  • 3 x 5 7 8 2 1 9 6
  • 3 4 5 7 8 2 1 9 6

Теперь вы видите, что отсортированная часть дополнилась элементом. Каждая следующая итерация делает то же самое, и к концу вы получите отсортированный массив!

Сортировка выбором

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

  • 3 5 1 2 4
  • 1 5 3 2 4
  • 1 2 3 5 4
  • 1 2 3 5 4
  • 1 2 3 4 5
  • 1 2 3 4 5

Сортировка слиянием

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

Массив делится на два подмассива, а затем происходит:

  1. Сортировка левой половины массива (рекурсивно)
  2. Сортировка правой половины массива (рекурсивно)
  3. Слияние

На схеме показана работа рекурсивных вызовов. Для массивов, отмеченных стрелкой вниз, вызывается функция. Во время слияния возвращаются массивы со стрелкой вверх. Всё просто: мы следуем за стрелкой вниз к нижней части дерева, а затем возвращаемся и объединяем.

В примере массив 3 5 4 2 1 делится на 3 5 4 и 2 1 и так далее. При достижении «дна» начинается объединение и сортировка.

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

На этом участнике нашего топа мы закончим разбирать примеры алгоритмов сортировки.

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

Так соблюдается правильная позиция самого «стержня». Затем алгоритм рекурсивно повторяет сортировку для правой и левой частей.

Метод Хоара — Быстрая сортировка(Quick-sort) — Всё для чайников

Алгоритм быстрой сортировки
Подробности Категория: Сортировка и поиск

Быстрая сортировка (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

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

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

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

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

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

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

 Реализация алгоритма на различных языках программирования:

C

Работает для произвольного массива из n целых чисел.

int n, a[n]; //n — количество элементов void qs(int* s_arr, int first, int last) { int i = first, j = last, x = s_arr[(first + last) / 2]; do { while (s_arr[i] < x) i++; while (s_arr[j] > x) j—; if(i s_arr[j]) swap(&s_arr[i], &s_arr[j]); i++; j—; } } while (i item.CompareTo(list.First()) item.CompareTo(list.First()) > 0).shortQuickSort()); } }

C++

Быстрая сортировка на основе библиотеки STL.

#include #include #include template< typename BidirectionalIterator, typename Compare > void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) { if( first != last ) { BidirectionalIterator left = first; BidirectionalIterator right = last; BidirectionalIterator pivot = left++; while( left != right ) { if( cmp( *left, *pivot ) ) { ++left; } else { while( (left != —right) && cmp( *pivot, *right ) ) ; std::iter_swap( left, right ); } } —left; std::iter_swap( first, left ); quick_sort( first, left, cmp ); quick_sort( right, last, cmp ); } } // для вещественных int partition (double *a, int p, int r) { double x = *(a+r); int i = p — 1; int j; double tmp; for (j = p; j < r; j++) { if (*(a+j) inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) { quick_sort( first, last, std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >() );

Java

import java.util.Comparator; import java.util.Random; public class Quicksort { public static final Random RND = new Random(); private void swap(Object[] array, int i, int j) { Object tmp = array[i]; array[i] = array[j]; array[j] = tmp; } private int partition(Object[] array, int begin, int end, Comparator cmp) { int index = begin + RND.

nextInt(end — begin + 1); Object pivot = array[index]; swap(array, index, end); for (int i = index = begin; i < end; ++ i) { if (cmp.compare(array[i], pivot) begin) { int index = partition(array, begin, end, cmp); qsort(array, begin, index - 1, cmp); qsort(array, index + 1, end, cmp); } } public void sort(Object[] array, Comparator cmp) { qsort(array, 0, array.

length — 1, cmp); }

Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)

import java.util.Random; public class QuickSort { public static void main(String[] args) { int N=10; int A[]; A = new int[N+1]; // заполнение массива for (int i=0;i (append (q-sort (filter (> A) [A|B])) [A] (q-sort (filter (< A) [A|B]))))

VB.NET

Судя по тестам, сортировка пузырьком 5000 занимает в 8 с половиной раз больше времени, чем qSort'ом

Sub Swap(ByRef Val1, ByRef Val2) Dim Proc Proc = Val1 Val1 = Val2 Val2 = Proc End Sub Function partition(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer, ByRef pivot As Integer) Dim i Dim piv Dim store piv = a(pivot) Swap(a(right — 1), a(pivot)) store = left For i = left To right — 2 If a(i) 1 Then pivot = getpivot(a, left, right) pivot = partition(a, left, right, pivot) quicksort(a, left, pivot) quicksort(a, pivot + 1, right) End If End Sub Sub qSort(ByVal a() As Integer) Dim i Dim ii For i = 0 To a.Length() — 1 ii = New System.Random().Next(0, a.Length() — 1) If i ii Then Swap(a(i), a(ii)) End If Next quicksort(a, 0, a.Length()) End Sub

Вызов функции:

qSort(имя сортируемого массива)

PHP

function quicksort (&$array, $l=0, $r=0) { if($r === 0) $r = count($array)-1; $i = $l; $j = $r; $x = $array[($l + $r) / 2]; do { while ($array[$i] < $x) $i++; while ($array[$j] > $x) $j—; if ($i $array[$j]) list($array[$i], $array[$j]) = array($array[$j], $array[$i]); $i++; $j—; } } while ($i $l) quicksort ($array, $l, $j); }

Встроенный язык 1С 8.*

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

Функция СравнитьЗначения(Знач1, Знач2) Если Знач1>Знач2 Тогда Возврат 1; КонецЕсли; Если Знач1

Источник: https://forkettle.ru/vidioteka/programmirovanie-i-set/108-algoritmy-i-struktury-dannykh/sortirovka-i-poisk-dlya-chajnikov/1010-metod-khoara-bystraya-sortirovka-quick-sort

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