Remkomplekty.ru

IT Новости из мира ПК
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Сортировка массива выбором паскаль

Сортировка массива выбором паскаль

В повседневной жизни нам очень часто приходится раскладывать наши вещи, книги, кассеты диски и т. п. в удобном для нас порядке. Для чего? Чтобы облегчить их дальнейший поиск. В библиотеке мы раскладываем книги по авторам, в телефонной книге мы записываем фамилии по алфавиту, в словаре слова расставлены по алфавиту. С появлением компьютеров люди стали использовать «железных монстров» для хранения больших объемов информации. Очевидно, что появилась потребность обработки данных. Две самые необходимые для этого функции — это сортировка и поиск. На первой мы и остановимся.

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

Обычно алгоритмы сортировки разделяются на два типа — сортировка массивов и сортировка последовательностей. В этой статье речь пойдет о сортировке массивов как наиболее часто встречающейся задаче при создании программы обработки данных. Под «массивом» я подразумеваю одномерный массив. Думаю, для вас не составит труда после прочтения статьи написать алгоритм сортировки двухмерного или более массива. Моя цель — не написать вам готовую программу, а познакомить с идеей, методом. Для практичности за описанием алгоритма будет следовать исходный код программы-примера на языке Паскаль. Почему на Паскале? Да потому что это наиболее распространенный язык для учебных целей. И, на мой взгляд, Паскаль лучше всего подходит для демонстрации механизмов сортировки.

Для оценки эффективности алгоритма мы будем использовать два значения: количество сравнений ключей (K) и число пересылок элементов (S). Последнее значение представляет для нас большой интерес — пересылка данных в памяти является более длительным процессом, чем сравнение. Также при описании алгоритмов я буду использовать такие величины: n — количество элементов массива, А[1..n] — сортируемый массив, x — переменная того же типа, что и элементы массива. Будем считать, что у нас массив целых чисел (А: array[l..n] of integer; х: integer;).

По количеству необходимых сравнений алгоритмы сортировки разделяют на два класса: более простые требуют примерно n^2 сравнений, а наиболее эффективные — порядка n*log(n). Я начну с более простых и наглядных алгоритмов. Первый метод сортировки, о котором я хочу рассказать, называется «сортировка с помощью прямого включения». Идея такова: мы по порядку берем элементы массива и ставим на их «законное» место. Начиная со второго, мы перебираем все элементы массива и последовательно сравниваем с элементами, которые имеют индекс меньше данного. Если наш элемент меньше предыдущего, то меняем их местами и продолжаем сравнивать дальше, если больше, то оставляем его — он уже на своем месте. И так продолжаем до тех пор, пока не достигнем левой границы массива. Чтобы в данном случае процесс сравнивания не уходил за пределы левой границы массива, необходимо создать так называемый «барьер» — добавить в начало массива ячейку (например, А[0]), в которую будем заносить сортируемый в этом проходе элемент. Вот полный код алгоритма:

Здесь A[0] — вышеупомянутый барьер, A[1..n] — сортируемый массив.

Мой совет: для простейших алгоритмов сортировок попробуйте написать на бумажке какую-нибудь последовательность из 4-5 чисел. А потом «прогоните» ее на листочке через алгоритм сортировки. При этом пишите значения всех переменных и изменения массива на каждом шаге. Это не так уж трудно сделать для первых трех алгоритмов и займет не больше половины тетрадного листа. Таким образом гораздо легче понять алгоритм. Конечно, для усовершенствованных методов это представляет значительную сложность, но и в этом случае есть выход. Например, в Delphi можно запустить программу в пошаговом режиме и смотреть значения всех переменных программы — очень полезная вещь для того чтобы понять, как работает какая-то часть программы. Не пренебрегайте этим советом!

Средние числа сравнения ключей и пересылки элементов имеют следующие значения: K=(n^2+n-2)/4, S=(n^2+9n-10)/4 Минимальные и максимальные значения такие: Kmin=n-1, Smin=3*(n-1), Kmax=(n^2+n-4)/4, Smax=(n^2+3n-4)/2. У алгоритма есть один существенный недостаток. Предположим, у нас есть массив чисел: 3,7,4,6,8,2. В этом случае последний элемент массива (2) придется «тащить» через весь массив.

Попробуем алгоритм, где перемещения делаются на большие расстояния. Такой алгоритм называется «сортировка прямым выбором». Он основан на следующей идее: выбираем в массиве наименьший элемент и меняем его местами с первым, после этого повторяем данную операцию для оставшихся элементов до тех пор, пока не останется единственный элемент. Ниже следует сам алгоритм:

В данном случае никакого барьера (A[0]) не нужно, и мы рассматриваем массив в диапазоне [1..n].

Сравнение ключей: K=(n^2-n)/2. Для пересылки ключей вычислить среднее значение нелегко, потому привожу минимальное (ключи уже отсортированы) и максимальное (ключи стоят в обратном порядке) значения: Smin=3*(n-1), Smax=n^2/4+3*(n-l). Как видим, алгоритм прямого выбора в большинстве случаев эффективнее прямого включения. Исключение составляет лишь ситуация, когда массив уже упорядочен или почти упорядочен. Однако в этом случае выигрыш не столь велик, и в целом данный метод предпочтительнее, чем предыдущий.

И последний тип сортировки первого класса называется «сортировка прямым обменом». Основное отличие этого метода от двух вышеперечисленных — обмен является характерной особенностью этого алгоритма. Идея алгоритма: последовательно перебираются по два рядом стоящих элемента, сравниваются и, в случае необходимости, меняются местами. Повторяем данную операцию до тех пор, пока не упорядочим весь массив.

При таких проходах по массиву мы сдвигаем наименьший элемент к левому краю. Если мы представим массив как вертикальную цепочку, то элементы при сортировке будут как пузырьки «всплывать» на свой уровень. Поэтому более широко известное наименование данного метода — «пузырьковая сортировка». Вот как выглядит код этого алгоритма:

Здесь используется переменная f в качестве флага. Если f=true, значит, в последнем проходе были сделаны перестановки и нужны еще проходы, а если f=false, значит, перестановок в последнем проходе не было и массив уже отсортирован. В этом алгоритме есть также свой недостаток: если наименьшее число расположено в конце массива, то для того, чтобы переместить его в начало (на его «законное» место), потребуется n-1 проходов. А в это время наибольший элемент с начала массива переместится в конец за один проход. Согласитесь, довольно неприятный факт. Вывод напрашивается сам собой: необходимо проходить массив с разных сторон по очереди, т. е. первый раз с начала в конец, второй — с конца в начало, третий — опять с начала в конец и т. д. Такой улучшенный алгоритм называется «шейкерной сортировкой» (ShakerSort). А вот программу для данного варианта предлагаю написать самим. Если вы полностью разобрались с методом пузырьковой сортировки, то это не будет для вас сложной задачей.

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

Читать еще:  Val паскаль что это

Теперь мы вплотную подошли к обсуждению улучшенных методов сортировки. Разобраться в них гораздо сложнее. В 1959 году Д. Шелл предложил усовершенствованную сортировку прямого включения. Идея довольно простая. Сначала мы сортируем элементы, отстоящие друг от друга на расстоянии 4. Например, берем элемент A[1] и сравниваем его с элементом A[5] (A[1+4]), если А[1] больше А[5], то меняем их местами. Потом берем A[2] и сравниваем с A[6] и т. д. После этого прохода с «четвертной» сортировкой проходим по массиву опять, но уже сортируем элементы, отстоящие друг от друга на расстоянии 2. И на последнем проходе идет обычная одинарная сортировка. Последовательность расстояний можно менять, как и их количество. Поэтому для обобщения все t расстояний занесем в массив s[1..t]. Сортировка каждого расстояния делается как сортировка прямым включением. Для условия окончания сортировки придется установить барьер, и не один.

Последний алгоритм, который мы рассмо¬трим, является самым быстрым из всех ныне существующих. Автор Ч. Хоар так и назвал его — Quicksort. В Quicksort сначала делают перемещения на большие расстояния. Для этого наугад выбираем в массиве элемент х. Просматриваем массив слева, пока не встретим элемент A[i]>x, потом смотрим массив справа, пока не обнаружим элемент А[j]

12. Методы сортировки массивов

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

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

Мы рассмотрим только три простейшие схемы сортировки.

Метод «пузырька»

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

В результате наибольший элемент оказывается в самом верху массива.

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

Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее «всплывшие» элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j -го прохода не проверяются элементы, стоящие на позициях выше j .

Теперь можно привести текст программы упорядочения массива M[1..N] :

Стандартная процедура swap будет использоваться и в остальных алгоритмах сортировки для перестановки элементов (их тип мы уточнять не будем) местами:

procedure swap (var x,y: . );
var t: . ;
begin
t := x;
x := y;
y := t
end;

Заметим, что если массив M — глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.

Применение метода «пузырька» можно проследить здесь.

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

Второй метод называется метод вставок ., т.к. на j -ом этапе мы «вставляем» j -ый элемент M[j] в нужную позицию среди элементов M[1] , M[2] ,. . ., M[j-1] , которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
Сказанное можно записать следующим образом:

нц для j от 2 до N
переместить M[j] на позицию i = M[i-1], либо i=1
кц

Чтобы сделать процесс перемещения элемента M[j] , более простым, полезно воспользоваться барьером: ввести «фиктивный» элемент M[0] , чье значение будет заведомо меньше значения любого из «реальных»элементов массива (как это можно сделать?). Мы обозначим это значение через —оо.

Если барьер не использовать, то перед вставкой M[j] , в позицию i-1 надо проверить, не будет ли i=1 . Если нет, тогда сравнить M[j] ( который в этот момент будет находиться в позиции i ) с элементом M[i-1].

Описанный алгоритм имеет следующий вид:

Сортировка посредством выбора

Идея сортировки с помощью выбора не сложнее двух предыдущих. На j -ом этапе выбирается элемент наименьший среди M[j] , M[j+1] ,. . ., M[N] (см. процедуру FindMin ) и меняется местами с элементом M[j] . В результате после j -го этапа все элементы M[j] , M[j+1] ,. . ., M[N] будут упорядочены.

Сказанное можно описать следующим образом:

нц для j от 1 до N-1
выбрать среди M[j] ,. . ., M[N] наименьший элемент и
поменять его местами с
M[j]
кц

В программе, как уже было сказано, используется процедура FindMin , вычисляющая индекс lowindex элемента, наименьшего среди элементов массива с индексами не меньше, чем startindex :

procedure FindMin (start index : integer; var lowindex : integer );
var lowelem: . ;
u: integer;
begin
lowindex := start index ;
lowelem := M[startindex];
for u:= start index +1 to N do
if M[u]

Сортировка одномерных массивов по убыванию и возрастанию в Pascal.

В чем заключается вопрос: Как организовать сортировку массивов по убыванию и возрастанию в Паскаль. Метод пузырька.

Сложность : средняя .

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

Естественно есть готовый код, который мы сейчас и разберем:

Массив mass, n кол-во элементов массива, i и j для циклов, buf для того чтобы поменять числа местами. Как я и сказал суть в том чтобы поменять местами соседние элементы пока не от сортируется. Давайте пока забудем про приведенный выше код и напишем следующее:

Мы меняем соседние элементы местами, СОСЕДНИЕ. , цикл до n-1, потому что у последнего элемента массива соседнего элемента нету.

Что же делает этот цикл, он само собой поменяет местами соседние элементы при выполнении условия, что левый больше правого, т.е. например ( 3 , 2 ), 3 больше 2 значит поменяем местами.

После прохода этого цикла ХОТЬ КАК найдется наибольший элемент, т.е. он встанет в самый конец.

Сначала у нас j = 1, j + 1 = 2, т.е. сначала сравняться числа 5 и 2, они поменяются местами, потом j=2, j+1=3,
т.е. j = 2, там у нас уже 5, а в j = 3, у нас 3, условие выполняется значит опять местами.

И так пока цикл не кончиться, в итоге получиться что у нас в самом конце будет самый наибольший элемент. ВСЁЁЁЁЁ, у нас есть последний элемент.

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

Всё работает правильно, можете проверить но все работает абсолютно ПРАВИЛЬНО. Теперь давайте сравним наш код с образцом:

Есть два отличия:

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

Читать еще:  Метод прямого выбора паскаль

По поводу 2-го, это значит что количество проверяемых чисел станет меньше, что это значит. Вот когда у нас идет первый цикл, у нас проверяются все числа и мы находим самый последний элемент, он у нас хоть как самый большой и больше смысла проверять его просто нет. Когда пойдет уже второй цикл у нас это число просто не будет затрагиваться вот и всё, а какой смысл его затрагивать ведь оно и так самое больше? И так после каждого прохода цикла )))

Пффффф… надеюсь вы поняли, да и еще это была сортировка по возрастанию чтобы сделать сортировку по убыванию достаточно просто понять знак в условии:

Готовый код задачи на сортировку массива по возрастанию:

Сортировка одномерного массива методом выбора

Презентация к уроку

Загрузить презентацию (344,7 кБ)

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

Тип урока: комбинированный – изучение нового материала, выполнение практической работы.

Цели и задачи:

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

Время реализации урока: 40 мин

Предполагаемый результат урока:

Обучающиеся

  • знают/понимаюталгоритм сортировки массива методом выбора;
  • умеют составлять программу для сортировки массива методом выбора.

Оборудование: ПК, проектор.

Дидактическое обеспечение урока: Презентация, задание для практической работы.

Основные понятия:

  • алгоритм сортировки методом выбора;
  • программа на Паскале сортировки методом выбора.

Особенности изложения содержания урока:

Это один из заключительных уроков изучения темы “Одномерные массивы” в 9 классе. Учащиеся изучили алгоритмы заполнения одномерного массива, вывода массива на экран, поиска числа в массиве, вставки и удаления элементов, перестановки и изменения элементов массива; научились составлять программу на Паскале по данному алгоритму. На предыдущем уроке был изучен алгоритм сортировки одномерного массива методом “пузырька”.

Ход урока

1. Организационный момент

Приветствие и проверка готовности учащихся к уроку.

2. Мотивация учащихся

Учитель: На предыдущем занятии мы с вами изучили алгоритм сортировки методом “пузырька”.

В чем состоит идея сортировки этим методом?

Ученик: рассказывает идею метода “пузырька”.

Учитель: Воспитание творческих способностей в человеке основывается на развитии самостоятельного мышления. (П. Капица) (Слайд 2)

Сегодня на уроке попробуем самостоятельно придумать другой алгоритм сортировки. Называется он “метод выбора”.

3. Постановка проблемы, составление алгоритма. (Слайд 3)

Учитель: Как вы думаете, что можно выбирать в числовом массиве, чтобы его отсортировать по возрастанию?

Ученики: предлагают различные варианты.

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

Ученики совместно составляют алгоритм.

Далее учащиеся делают запись алгоритма в тетради. (Слайд 4)

Упорядочивание по возрастанию

Ищем минимальный элемент среди всех элементов массива. Находим его номер.

Меняем местами 1-й и этот минимальный.

Производим поиск минимального элемента среди элементов со 2-го по n.

Меняем местами 2-й и этот минимальный.

Повторяем процедуру поиска минимального среди оставшихся и обмена местами многократно (? раз)

Учитель: Сколько раз нужно повторять процедуру?

Ученик: n-1 раз.

Учитель: Рассмотрим пример сортировки числового массива методом выбора. (Слайды 5-9)

4. Запись алгоритма на языке программирования PascalABC.NET. (Слайды 10-11)

5. Учитель: Час работы научит больше, чем день объяснения. (Жан-Жак Руссо). Практическая работа. Задания для учащихся:

Выполнить сортировку по возрастанию методом выбора.

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

Выполнить сортировку первой половины массива по возрастанию, второй – по убыванию.

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

6. Домашнее задание:

  • Повторить изученные алгоритмы сортировки.
  • Подсчитать количество произведенных сравнений.
  • Подсчитать количество произведенных перестановок.
  • Изменить процедуру сортировки так, чтобы сортировка начиналась с последнего элемента массива (с конца, индекс К — уменьшался).
  • Отсортировать по алфавиту строковый массив, состоящий из 10 фамилий учащихся класса. Фамилии вводить по алфавиту.

7. Рефлексия деятельности на уроке

Учитель: Мы рассмотрели наиболее простые алгоритмы сортировки:

  • “пузырьковая” сортировка;
  • сортировка выбором.

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

Сортировка массива выбором паскаль

Простые и улучшенные методы упорядочения данных.

Содержание

Задача сортировки

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

Необходимость отсортировать какие–либо величины возникает в программировании очень часто. К примеру, входные данные подаются «вперемешку», а вашей программе удобнее обрабатывать упорядоченную последовательность. Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы — в десятки раз.

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

Методы упорядочения подразделяются на внутренние (обрабатывающие массивы) и внешние (занимающиеся только файлами) 1 .

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

Простые сортировки

К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N 2 действий, где С — некоторая константа.

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

Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений и по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих операций занимает различное время. Однако точные значения удаётся найти редко, поэтому для оценки алгоритмов ограничиваются лишь понятием «пропорционально», которое не учитывает конкретные значения констант, входящих в итоговую формулу. Общую же эффективность алгоритма обычно оценивают «в среднем»: как среднее арифметическое от сложности алгоритма «в лучшем случае» и «в худшем случае», то есть (Eff_best + Eff_worst) / 2.

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

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

Читать еще:  Переменные в си шарп

Алгоритм ПрВст

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

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

— записать новый элемент на освободившееся место.

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

Реализация алгоритма ПрВст

Метод прямых вставок с барьером (ПрВстБар)

Для того, чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var ) и будем записывать в неё поочерёдно каждый вставляемый элемент (сравните строки <*>и <**>в приведённых вариантах программы). В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как «барьер», не дающий индексу j выйти за нижнюю границу массива. Кроме того, компонента a[0] может заменить собою и дополнительную переменную х:

Эффективность алгоритма ПрВстБар

Понятно, что для этой сортировки наилучшим будет случай, когда на вход подаётся уже упорядоченная последовательность данных. Тогда алгоритм ПрВстБар совершит N-1 сравнение и 0 пересылок данных.

В худшем же случае — когда входная последовательность упорядочена «наоборот» — сравнений будет уже (N + 1) * N / 2, а пересылок (N — 1) * (N + 3). Таким образом, этот алгоритм имеет сложность

N 2 (читается «порядка эн квадрат») по обоим параметрам.

Пример сортировки

Предположим, что нужно отсортировать следующий набор чисел:

Выполняя алгоритм ПрВстБар, мы получим такие результаты (подчёркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):

0 шаг: 5343621
1 шаг: 5 343621 1 1+1 3 1+2 4
2 шаг: 35 43621 1 1+1 1+2
3 шаг: 345 3621 2 2+1 2+2
4 шаг: 3345 621 0 1 0
5 шаг: 33456 21 5 5+1 5+2
6 шаг: 233456 1 6 6+1 6+2
Результат: 1233456 15 20 25

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

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

Пусть, к примеру, нужно найти место для элемента 7 в таком массиве:

Найдём средний элемент этой последовательности (10) и сравним с ним семёрку. После этого всё, что больше 10 (да и саму десятку тоже), можно смело исключить из дальнейшего рассмотрения:

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

Итак, отсечём половину последовательности:

Таким образом, мы нашли в исходной последовательности место, «подходящее» для нового элемента. Если бы в той же самой последовательности нужно было найти позицию не для семёрки, а для девятки, то последовательность границ рассматриваемых промежутков была бы такой:

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

Будет ли такой алгоритм универсальным? Давайте проверим, что же произойдёт, если мы станем искать позицию не для семёрки или девятки, а для единицы:

Как видим, правая граница становится неопределённой — выходит за пределы массива. Будет ли этот факт иметь какие–либо неприятные последствия? Очевидно, нет, поскольку нас интересует не правая, а левая граница.

«А что будет, если мы захотим добавить 21?» — спросит особо въедливый читатель. Проверим это:

Кажется, будто всё плохо: левая граница вышла за пределы массива; непонятно, что нужно сдвигать.

Вспомним, однако, что в реальности на (N + 1)–й позиции как раз и находится вставляемый элемент (21). Таким образом, если левая граница вышла за рассматриваемый диапазон, получается, что ничего сдвигать не нужно. Вообще же, такие действия выглядят явно лишними, поэтому от них стоит застраховаться, введя одну дополнительную проверку в текст алгоритма.

Реализация алгоритма БинВст

Эффективность алгоритма БинВст

Теперь на каждом шаге выполняется не N, а log N проверок 5 , что уже значительно лучше (для примера, сравните 1000 и 10 = log 1024). Следовательно, всего будет совершено N*log N сравнений. Впрочем, улучшение это не слишком значительное, ведь по количеству пересылок наш алгоритм по–прежнему имеет сложность «порядка N 2 ».

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

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

Алгоритм ПрВыб

На каждом шаге (всего их будет ровно N — 1) будем производить такие действия:

  1. найдём минимум среди всех ещё не упорядоченных элементов;
  2. поменяем его местами с первым «по очереди» не отсортированным элементом. Мы надеемся, что читателям очевидно, почему к концу работы этого алгоритма последний (N–й) элемент массива автоматически окажется максимальным.

Реализация ПрВыб

Эффективность алгоритма ПрВыб

В лучшем случае (если исходная последовательность уже упорядочена), алгоритм ПрВыб произведёт (N — 1) * (N + 2) / 2 сравнений и 0 пересылок данных. В остальных же случаях количество сравнений останется прежним, а вот количество пересылок элементов массива будет равным 3 * (N — 1).

Таким образом, алгоритм ПрВыб имеет квадратичную сложность (

N 2 ) по сравнениям и линейную (

N) — по пересылкам.

Замечание. Если перед вами поставлена задача отсортировать строки двумерного массива (размерности NxN) по значениям его первого столбца, то сложность алгоритма ПрВыб, модифицированного для решения этой задачи, будет квадратичной (N 2 сравнений и N 2 пересылок), а алгоритма БинВст — кубической (N*log N сравнений и N 3 пересылок). Комментарии, как говорится, излишни.

Пример сортировки

Предположим, что нужно отсортировать тот же набор чисел, при помощи которого мы иллюстрировали метод сортировки простыми вставками:

Теперь мы будем придерживаться алгоритма ПрВыб (подчёркнута несортированная часть массива, а квадратиком выделен её минимальный элемент):

1 шаг: 5343621
2 шаг: 1 343625
3 шаг: 12 43635 <***>6
4 шаг: 123 3645 <ничего не делаем>
5 шаг: 1233 645
6 шаг: 12334 65
результат: 1233456

Сортировка простыми обменами

Рассмотренными сортировками, конечно же, не исчерпываются все возможные методы упорядочения массивов.

Существуют, например, алгоритмы, основанные на обмене двух соседних элементов: Пузырьковая и Шейкерная сортировки. Обе имеют сложность порядка N 2 , однако и по скорости работы на любых входных данных, и по простоте реализации они проигрывают другим простым сортировкам. Поэтому мы настойчиво советуем читателю не прельщаться красивыми названиями, за которыми не стоит никакой особенной выгоды.

Тем же, кто всё-таки желает ознакомиться с обменными сортировками, а также с подробными данными по сравнению различных сортировок, мы рекомендуем труды Д. Кнута 7 или Н. Вирта 8 .

Ссылка на основную публикацию
Adblock
detector