Объяснение быстрой сортировки в Java

Соглашение о сокращении вдвое

Когда количество элементов в списке четное, уменьшение списка вдвое означает, что буквальная первая половина списка является первой половиной, а буквальная вторая половина списка - второй половиной. Средний (средний) элемент всего списка - это последний элемент первого списка. Это означает, что средний индекс имеет длину / 2 - 1, так как подсчет индекса начинается с нуля. Длина - это количество элементов в списке. Например, если количество элементов равно 8, то в первой половине списка 4 элемента, а во второй половине списка также 4 элемента. Это нормально. Поскольку подсчет индекса начинается с 0, средний индекс равен 3 = 8/2 - 1.

А как насчет случая, когда количество элементов в списке или подсписке нечетное? Вначале длина все еще делится на 2. По соглашению количество элементов в первой половине этого деления составляет length / 2 + 1/2. Подсчет индекса начинается с нуля. Средний индекс равен длине / 2 - 1/2. По соглашению это считается средним сроком. Например, если количество элементов в списке 5, то средний индекс равен 2 = 5/2 - 1/2. И есть три элемента в первой половине списка и два элемента во второй половине. Средний элемент всего списка - это третий элемент с индексом 2, который является средним индексом, поскольку подсчет индекса начинается с 0.

Такое деление является примером целочисленной арифметики.

Медиана трех значений

Вопрос: какова медиана последовательности:

C B A

Решение:
Расположите список в порядке возрастания:

А Б В

Средний член B - это медиана. Это величина, которая находится между двумя другими величинами.

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

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

Термин arr означает массив. Этот сегмент кода ищет медианное значение, а также выполняет некоторую сортировку. Этот сегмент кода выглядит просто, но может сбивать с толку. Итак, обратите внимание на следующее объяснение:

Сортировка в этом руководстве приведет к созданию списка, в котором первое значение - наименьшее значение, а последнее значение - наибольшее значение. В алфавите A меньше Z.

Здесь опорная точка - это итоговая медиана. Низкий - это самый низкий индекс списка или подсписка (не обязательно для самого низкого значения); high - это самый высокий индекс списка или подсписка (не обязательно для самого высокого значения), а middle - это обычный средний индекс (не обязательно для среднего значения всего списка).

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

В коде сначала получается обычный средний индекс. В этом начале список не отсортирован. Сравнение и некоторая перестановка трех значений в порядке возрастания должны происходить одновременно. Первый оператор if сравнивает значение самого низкого индекса и среднего индекса. Если значение среднего индекса меньше, чем значение самого низкого индекса, то два значения меняются местами. При этом начинается сортировка и изменяется расположение значений в списке или подсписке. Второй оператор if сравнивает значение самого высокого индекса и самого низкого индекса. Если значение наивысшего индекса меньше, чем значение самого низкого индекса, два значения меняются местами. При этом происходит некоторая сортировка и изменение расположения значений в списке или подсписке. Третий оператор if сравнивает значение среднего индекса и самого высокого индекса. Если самый высокий индекс меньше среднего, два значения меняются местами. Здесь также может произойти некоторая сортировка или перестановка. Это третье условие if не похоже на два предыдущих.

В конце этих трех перестановок среднее значение трех рассматриваемых значений будет A [высокое], исходное содержание которого могло быть изменено в сегменте кода. Например, рассмотрим несортированную последовательность:

C B A

Мы уже знаем, что медиана равна B. Однако это должно быть доказано. Здесь цель состоит в том, чтобы получить медианное значение этих трех значений, используя указанный выше сегмент кода. Первый оператор if сравнивает B и C. Если B меньше C, то позиции B и C должны быть поменяны местами. B меньше C, поэтому новое расположение выглядит следующим образом:

Б В А

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

А В Б

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

А В Б

B - это медиана, которая равна A [high], и это точка поворота. Итак, стержень рождается в крайнем конце списка или подсписка.

Функция обмена

Еще одна функция, необходимая для быстрой сортировки, - это функция подкачки. Функция обмена меняет значения двух переменных. Псевдокод для функции подкачки:

Здесь x и y относятся к фактическим значениям, а не к копиям.

Сортировка в этой статье приведет к созданию списка, в котором первое значение - наименьшее значение, а последнее - наибольшее значение.

Содержание статьи

• Алгоритм быстрой сортировки
• Псевдокод раздела
• Иллюстрация быстрой сортировки
• Кодирование на Java
• Заключение

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

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

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

Шаги для алгоритма быстрой сортировки следующие:

1. Убедитесь, что в несортированном списке есть как минимум 2 числа, которые нужно отсортировать.
2. Получите приблизительное центральное значение для списка, называемое опорной точкой. Медиана, как описано выше, является одним из способов получения точки поворота. У разных способов есть свои преимущества и недостатки. - Увидим позже.
3. Разбейте список на разделы. Это означает, что нужно разместить опорную точку в списке. Таким образом, все элементы слева меньше значения поворота, а все элементы справа больше или равны значению поворота. Есть разные способы разбиения. Каждый метод перегородки имеет свои преимущества и недостатки. Разделение - это разделение в парадигме «разделяй и властвуй».
4. Повторяйте шаги 1, 2 и 3 рекурсивно для новых пар подписок, которые появляются, пока не будет отсортирован весь список. Это победа в парадигме «разделяй и властвуй».

Псевдокод быстрой сортировки:

Псевдокод раздела

Псевдокод раздела, используемый в этом руководстве:

На иллюстрации быстрой сортировки ниже используется этот код:

Иллюстрация быстрой сортировки

Рассмотрим следующий несортированный список (массив) буквенных символов:

В Е Р Т Й У И О П

При осмотре отсортированный список выглядит следующим образом:

E I O P Q R T U W Y

Отсортированный список теперь будет проверяться с использованием указанного выше алгоритма и сегментов псевдокода из несортированного списка:

В Е Р Т Й У И О П

Первая точка поворота определяется из arr [0] = Q, arr [4] = T и arr [9] = P, обозначается как Q и ​​помещается в крайний правый угол списка. Итак, список с любой сортировкой сводной функции становится:

П В Е Р Т Й У И О К

Текущая точка поворота - Q. Процедура поворота произвела небольшую сортировку и поместила P на первую позицию. Результирующий список должен быть переупорядочен (разбит на разделы) таким образом, чтобы все элементы слева были меньше по значению, тогда точка поворота и все элементы справа от нее были равны или больше, чем точка поворота. Компьютер не может выполнить разметку путем проверки. Итак, это происходит с использованием индексов и вышеуказанного алгоритма разделения.

Нижний и верхний индексы теперь равны 0 и 9. Итак, компьютер начнет сканирование с индекса 0 до тех пор, пока не достигнет индекса, значение которого равно или больше, чем точка поворота, и временно остановится на нем. Он также будет сканировать с верхнего (правого) конца, индекс 9, снижаясь, пока не достигнет индекса, значение которого меньше или равно оси поворота, и временно остановится на нем. Это означает две позиции стопа. Если i, переменная инкрементного индекса, начиная с минимума, еще не равна или больше переменной с уменьшающимся индексом j, начиная с высокого, то эти два значения меняются местами. В текущей ситуации сканирование с обоих концов остановилось на W и O. Таким образом, список становится:

П О Е Р Т Ы У И В К

Поворот по-прежнему Q. Сканирование в противоположных направлениях продолжается и соответственно останавливается. Если i еще не равно или больше j, то два значения, при которых сканирование с обоих концов остановлено, меняются местами. На этот раз сканирование с обоих концов остановилось на R и I. Итак, расположение списка выглядит следующим образом:

P O E I T Y U R W Q

Поворот по-прежнему Q. Сканирование в противоположных направлениях продолжается и соответственно останавливается. Если i еще не равно или больше j, то два значения, на которых сканирование остановлено, меняются местами. На этот раз сканирование с обоих концов остановилось на T для i и I для j. i и j встретились или пересеклись. Значит, подмены быть не может. Список остается прежним:

P O E I T Y U R W Q

На этом этапе точка поворота Q должна быть помещена в окончательное положение при сортировке. Для этого нужно заменить arr [i] на arr [high], поменять местами T и Q. Список становится следующим:

P O E I Q Y U R W T

На этом разбиение всего списка завершено. Свою роль сыграл стержень = Q. Теперь есть три подсписка:

P O E I Q Y U R W T

Разделение есть разделение и завоевание (сортировка) в парадигме. Q находится в правильной позиции сортировки. Каждый элемент слева от Q меньше Q, а каждый элемент справа от Q больше Q. Однако левый список по-прежнему не отсортирован; и правильный список все еще не отсортирован. Вся функция быстрой сортировки должна вызываться рекурсивно, чтобы отсортировать левый подсписок и правый подсписок. Этот отзыв Quick Sort должен продолжаться; новые подсписки будут развиваться до тех пор, пока весь исходный список не будет полностью отсортирован. При каждом вызове функции быстрой сортировки сначала обрабатывается левый подсписок, а затем соответствующий правый подсписок. Для каждого подсписка необходимо получить новую сводку.

Для подсписка:

P O E I

Определяется точка поворота (медиана) для P, O и I. Для этого подсписка, относящегося к полному списку, новое arr [low] - это arr [0], а новое arr [high] - это последнее arr [i-1] = arr [ 4-1] = arr [3], где i - окончательный индекс сводной таблицы из предыдущего раздела. После вызова функции pivot () новое значение поворота pivot = O. Не путайте функцию поворота и значение поворота. Функция поворота может выполнять небольшую сортировку и размещать точку поворота в крайнем правом углу подсписка. Этот подсписок становится,

И П Е О

В этой схеме поворот всегда заканчивается в правом конце подсписка или списка после вызова его функции. Сканирование с обоих концов начинается с arr [0] и arr [3], пока i и j не встретятся или не пересекутся. Сравнение выполняется с pivot = O. Первые остановки находятся в точках P и E. Они меняются местами, и новый подсписок становится:

I E P O

Сканирование с обоих концов продолжается, и новые остановки находятся в точке P для i и в точке E для j. Теперь я и j встретились или пересеклись. Таким образом, подсписок остается таким же, как:

I E P O

Разделение подсписка или списка заканчивается, когда точка поворота находится в окончательном положении. Итак, новые значения для arr [i] и arr [high] меняются местами. То есть поменяны местами P и O. Новый подсписок становится:

I E O P

O теперь находится на последней позиции для всего списка. Его роль стержня закончилась. Подсписок в настоящее время разделен на еще три списка:

I E O P

На этом этапе необходимо вызвать быструю сортировку первого правого подсписка. Однако называться не будет. Вместо этого он будет отмечен и зарезервирован для последующего вызова. Поскольку операторы функции разделения выполнялись, начиная с верхней части функции, сейчас должна быть вызвана быстрая сортировка для левого подсписка (после вызова pivot ()). Будет вызван список:

I E

Он начнется с поиска медианы I и E. Здесь arr [low] = I, arr [mid] = I и arr [high] = E. Таким образом, медиана, pivot, должна определяться алгоритмом поворота как , I. Однако указанный выше псевдокод поворота будет определять точку поворота как E. Эта ошибка возникает здесь, потому что указанный выше псевдокод предназначен для трех элементов, а не для двух. В приведенной ниже реализации в код внесены некоторые изменения. Подсписок становится,

E I

Сводная диаграмма всегда заканчивается в правом конце подсписка или списка после вызова функции. Сканирование с обоих концов начинается с arr [0] и arr [1], исключая, пока i и j не встретятся или не пересекутся. Сравнение выполняется с pivot = I. Первые и единственные остановки находятся в I и E: в I для i и в E для j. Теперь я и j встретились или пересеклись. Итак, подсписок остается таким же, как:

E I

Разделение подсписка или списка заканчивается, когда точка поворота находится в окончательном положении. Итак, новые значения для arr [i] и arr [high] меняются местами. Здесь бывает, что arr [i] = I и arr [high] = I. Таким образом, одно и то же значение заменяется само собой. Новый подсписок становится:

E I

I теперь находится на последней позиции для всего списка. Его роль стержня закончилась. Подсписок теперь разделен на еще два списка:

E I

Итак, до сих пор опорными точками были Q, O и I. Поворотные точки заканчивались на своих конечных позициях. Подсписок из одного элемента, такой как P выше, также заканчивается на своей конечной позиции.

На этом этапе первый левый подсписок полностью отсортирован. И процедура сортировки сейчас по адресу:

E I O P Q Y U R W T

Первый правый подсписок:

Y U R W T

еще нужно рассортировать.

Завоевание первого правого подсписка
Помните, что вызов быстрой сортировки для первого правого подсписка был отмечен и зарезервирован, а не выполнен. На этом этапе он будет выполнен. Итак, новый arr [low] = arr [5] = arr [QPivotIndex + 1], а новый arr [high] остается arr [9]. Аналогичный набор действий, который произошел с первым левым подсписком, будет происходить здесь. И этот первый правый подсписок отсортирован по:

R T U W Y

А исходный несортированный список был отсортирован по:

E I O P Q R T U W Y

Кодирование на Java

Ввод алгоритма в Java означает просто поместить все вышеупомянутые сегменты псевдокода в методы Java в одном классе. Не забывайте, что в классе должен быть метод main (), который будет вызывать функцию quicksort () с несортированным массивом.

Метод pivot ()

Метод Java pivot (), который возвращает значение pivot, должен быть:

Метод swap ()

Метод swap () должен быть:

Метод quicksort ()

Метод quicksort () должен быть:

Метод partition ()

Метод partition () должен быть:

Метод main ()

Метод main () может быть:

Все вышеперечисленные методы можно объединить в один класс.

Заключение

Быстрая сортировка - это алгоритм сортировки, использующий парадигму «разделяй и властвуй». Он начинается с разделения несортированного списка на два или три подсписка. В этом руководстве Quick Sort разделил список на три подсписка: левый подсписок, средний список из одного элемента и правый подсписок. Победа в быстрой сортировке - это разделение списка или подсписка при его сортировке с использованием значения поворота. В этом руководстве объясняется одна реализация быстрой сортировки на компьютерном языке Java.

Об авторе

Chrysanthus Forcha

Первооткрыватель математики «Интеграция из первых принципов» и связанных с ней серий. Имеет степень магистра технического образования по специальности 'Электроника и компьютерное программное обеспечение'. Бакалавр электроники. У меня также есть знания и опыт на уровне магистра в области вычислительной техники и телекоммуникаций. Из 20 000 писателей я был 37-м лучшим писателем на сайте devarticles.com. Я работаю в этих сферах более 10 лет.

СВЯЗАННЫЕ СОВЕТЫ ДЛЯ LINUX

• Сравнение строк в Java
• Как использовать HashMap в Java
• Объяснение быстрой сортировки в Java
• Обход двоичного дерева в Java
• Объяснение сортировки слиянием в Java
• Как использовать сканер в Java
• Запись в файл Java