Сортировка хоара c код

Сортировка хоара c код

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

Я буду далеко не первым и не последним, кто скажет, что «быстрая» она только в названии и сейчас существует куча аналогов, и вообще для каждого типа данных нужна своя сортировка. Да, это все правда, но эта правда не отменяет простого факта, что собственноручная реализация быстрой сортировки оттачивает навыки программирования в общем, и она всегда будет в университетских курсах, я в этом уверен. Из этих же соображений был выбран язык программирования для реализации, ибо тут же можно попрактиковаться в использовании указателей в C/C++.

Предлагаю перейти к делу и для начала кратко рассмотреть суть алгоритма.

Как работает быстрая сортировка

Схему алгоритма можно описать таким образом:

  1. Выбрать опорный элемент в массиве — часто встречается вариант с центральным элементом.
  2. Разделить массив на две части следующим образом: все элементы из левой части, которые больше или равны опорному, перекидываем в правую, аналогично, все элементы из правой, которые меньше или равны опорному кидаем в левую часть.
  3. В результате предыдущего шага в левой части массива останутся элементы, которые меньше или равны центральному, а в правой — больше либо равны.
    Наглядно это можно показать таким образом:
    |———————|—————————|———————|
    | mas[i] = mid |
    |———————-|—————————|———————|
  4. Рекурсивно повторяем действие для левой и правой части массива.

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

Иллюстрацию одного шага алгоритма я позаимствовал отсюда , больно уж она наглядная.

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

На вход функция принимает сам массив(указатель на начало) и его размер.

Читайте также:  Зашифровать текст в бинарный код

Заключение

Это задание одновременно помогает понять, как работает рекурсия и учит прослеживать изменение данных во время исполнения алгоритма. Рекомендуется «дойти» и написать это самостоятельно, но все же вот моя реализация, мне и самому она может пригодиться. На этом у меня все, спасибо за внимание!

Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.

Итак, быстрая сортировка, или, по названию функции в Си, Qsort — это алгоритм сортировки, сложность которого в среднем составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.

  1. Выбираем опорный элемент
  2. Разбиваем массив на 3 части
    • Создаём переменные l и r — индексы соответственно начала и конца рассматриваемого подмассива
    • Увеличиваем l, пока l-й элемент меньше опорного
    • Уменьшаем r, пока r-й элемент больше опорного
    • Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
    • Если l вдруг становится больше r, то прерываем цикл
    • Повторяем рекурсивно, пока не дойдём до массива из 1 элемента

    Что ж, выглядит не так уж сложно. Реализуем на Си? Нет проблем!

    Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента — один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью.

    Читайте также:  Бук не видит wifi

    Писáл сам, изредка поглядывая на Википедию. Пользуясь случаем, передаю спасибо замечательным преподавателям и студентам ПетрГУ, научившим меня множеству полезных вещей, в том числе и этому алгоритму!

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

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

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

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

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

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

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

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

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

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

    Читайте также:  Как перезагрузить модем ростелеком

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

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

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

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

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


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


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


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

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

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

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

    Результат выполнения

    Ссылка на основную публикацию
    Совместимость ssd с ноутбуками
    Вопрос совместимости Многие пользователи интересуются совместимостью материнской платы и SSD, который они купили или хотят купить. Опыт показывает, что не...
    Скрыть не интересуюсь уже купил спам мешает
    "Яндекс" запустил опцию "Скрыть объявление" на сайтах входящих в Рекламную сеть Яндекса. Опция позволяет отключить показ рекламных объявлений, которые в...
    Слабо работает интернет что делать
    Как настроить роутер, как настроить модем, как настроить оптический терминал. Настройка роутера по http://192.168.1.1 или http://192.168.0.1 Что делать если медленно...
    Совместимость ремешков apple watch
    Здесь приводятся общие инструкции, которые помогут Вам снять, поменять и застегнуть ремешок. В случае смены ремешка убедитесь, что размеры используемого...
    Adblock detector