Сортировка массива с методом прямого включения. Сортировка методом прямого включения. Эффективность алгоритма прямого включения
Необходимые определения и классификация сортировок.
Сортировка. Необходимые определения и классификация сортировок. Сортировки прямого включения и выбора. Их эффективность
Сортировка – это расположение данных в памяти в регулярном виде по их ключам. Так что при обработке данных важно знать информационное поле данных и размещение их в машине. Поэтому различают внутреннюю (сортировка в оперативной памяти) и внешнюю сортировки (сортировка во внешней памяти). Регулярность расположения элементов – это возрастание (убывание) значения ключа от начала к концу в массиве.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того чтобы их уменьшить, используют метод сортировки таблицы адресов . Этот метод применяют в таблице адресов ключей . Производят перестановку указателей, т.е. Сам массив не перемещается. При сортировке могут встретиться и одинаковые ключи. В этом случае одинаковые ключи желательно расположить после сортировки в том же порядке, что и в исходном файле. Этот принцип используется для устойчивой сортировки .
Эффективность сортировки можно рассматривать с нескольких критериев:
1) время, затрачиваемое на сортировку;
2) объем оперативной памяти, требуемой для сортировки;
3) время, затраченное программистом на написание программы.
Время, затраченное на сортировку, пропорционально количеству сравнений при выполнении сортировки и количеству перемещений элементов.
Считается, что порядок числа сравнения при сортировке может находиться в пределах от о(nlogn) до о(n 2) , где о(n) - идеальный и недостижимый случай.
Методы сортировки можно классифицировать примерно так:
1) строгие (прямые) методы (их эффективность примерно одинакова):
· прямого включения ;
· прямого выбора ;
· прямого обмена ;
2) улучшенные методы .
В жизни принцип данной сортировки присутствует при раскладывании пасьянсов, уборки квартиры, когда необходимо расположить кучу смешанных вещей в должном порядке и т.д. Очень естественный способ сортировки был применён и к упорядочиванию данных.
Элементы мысленно делятся на уже готовую последовательность a 1 ,...,a i-1 и исходную последовательность. В готовой последовательности элементы располагаются в заданном порядке (по убыванию или по возрастанию). А в исходной последовательности располагаются элементы, которые и нужно отсортировать. При каждом шаге элементы исходной последовательности уменьшаются на единицу, а готовая увеличивается на единицу. Это происходит из-за того, что из исходной последовательности извлекается i- й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место среди элементов готовой последовательности.
Рассмотрим пример сортировки методом прямого включения на последовательности элементов: 10, 3, 11, 8, 2, 15, 44, 9 (табл. 11.1). Необходимо её отсортировать по возрастанию.
Сначала готовая последовательность не имеет элементов. На первом шаге первый элемент исходной последовательности – это 10, становится первым элементом готовой последовательности. Далее второй шаг: элемент 3 из исходной последовательности помещается в готовую. Это происходит так. Если элемент больше 10, то он остаётся на своём месте, а если меньше, то 10 сдвигается на единицу вправо и на её место ставится элемент. Так как 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, то 11 остаётся на месте. Исходная последовательность теперь равна: 8, 2, 15, 44, 9. Последующие шаги производятся аналогичным образом.
Таблица 11.1
Принцип работы сортировки прямым включением
Число шагов в данной сортировке (табл. 11.1) равно числу элементов в сортируемой последовательности, т.е. 8 шагов = 8 элементов.
Существуют два способа реализации данного метода – это без барьера (рис. 11.1) и с барьером (рис. 11.2).
Метод: Метод косвенного измерения влажности веществ, основанный на зависимости диэлектрической проницаемости этих веществ от их влажности. Источник: РМГ 75 2004: Государственная система обеспечения еди …
КРОВЬ - КРОВЬ, жидкость, заполняющая артерии, вены и капиляры организма и состоящая из прозрачной бледножелтоват. цвета плаз мы и взвешенных в ней форменных элементов: красных кровяных телец, или эритроцитов, белых, или лейкоцитов, и кровяных бляшек, или … Большая медицинская энциклопедия
Недвижимость - (Real estate) Определение недвижимости, виды недвижимости, аренда и продажа недвижимости Информация о понятии недвижимость, виды недвижимости, аренда и продажа недвижимости, налогообложение и страхование Содержание - это вид имущества,… … Энциклопедия инвестора
У этого термина существуют и другие значения, см. C. См. также: Си (язык программирования) C++ Семантика: мультипарадигмальный: объектно ориентированное, обобщённое, процедурное, метапрограммирование Тип исполнения: компилируемый Появился в … Википедия
ОЦЕНКА СТОИМОСТИ НЕМАТЕРИАЛЬНЫХ АКТИВОВ - (англ. intangible assets appraisal) – определение стоимости объема прав предприятия на определенную группу объектов, не имеющих материально вещественного содержания и приносящих предприятию доход в течение периода, оговоренного национальным… … Финансово-кредитный энциклопедический словарь
ШКОЛА общеобразовательная - уч. воспитат. учреждение, базовый элемент образоват. системы. В этом качестве Ш. предмет исследования разл. дисциплин: пед., ист., демографич., социология, и др. Только в педагогике проблематика Ш. занимает вполне самостоят. место. Изученность… … Российская педагогическая энциклопедия
время - 3.3.4 время tE (time tE): время нагрева начальным пусковым переменным током IА обмотки ротора или статора от температуры, достигаемой в номинальном режиме работы, до допустимой температуры при максимальной температуре окружающей среды. Источник … Словарь-справочник терминов нормативно-технической документации
ГОСТ Р МЭК 60204-1-2007: Безопасность машин. Электрооборудование машин и механизмов. Часть 1. Общие требования - Терминология ГОСТ Р МЭК 60204 1 2007: Безопасность машин. Электрооборудование машин и механизмов. Часть 1. Общие требования оригинал документа: TN систем питания Испытания по методу 1 в соответствии с 18.2.2 могут быть проведены для каждой цепи… … Словарь-справочник терминов нормативно-технической документации
автоматический - 3.3.1 автоматический пробоотборник (automatic sampler): Устройство, используемое для извлечения представительной пробы жидкости, протекающей по трубопроводу. Примечание Автоматический пробоотборник обычно состоит из зонда (щупа), экстрактора… … Словарь-справочник терминов нормативно-технической документации
напряжение - 3.10 напряжение: Отношение растягивающего усилия к площади поперечного сечения звена при его номинальных размерах.
Сортировка методом прямого включения работает со списком неупорядоченных положительных целых чисел (обычно называемых ключами), сортируя их в порядке возрастания. Это делается примерно так же, как большинство игроков упорядочивают сданные им карты, поднимая каждый раз по одной карте. Покажем работу общей процедуры на примере следующего неотсортированного списка из восьми целых чисел:
27 412 71 81 59 14 273 87.
Отсортированный список создается заново; вначале он пуст. На каждой итерации первое число неотсортированного списка удаляется из него и помещается на соответствующее ему место в отсортированном списке. Для этого отсортированный список просматривается, начиная с наименьшего числа, до тех пор, пока не находят соответствующее место для нового числа, т.е. пока все отсортированные числа с меньшими значениями не окажутся впереди него, а все числа с большими значениями --- после него. Следующая последовательность списков показывает,как это делается:
Итерация 0
Отсортированный 27
Итерация 1 Неотсортированный 412 71 81 59 14 273 87
Отсортированный 27 412
Итерация 2 Неотсортированный 71 81 59 14 273 87
Отсортированный 27 71 412
Итерация 3 Неотсортированный 81 59 14 273 87
Отсортированный 27 71 81 412
Итерация 4 Неотсортированный 59 14 273 87
Отсортированный 27 59 71 81 412
Итерация 5 Неотсортированный 14 273 87
Отсортированный 14 27 59 71 81 412
Итерация 6 Неотсортированный 273 87
Отсортированный 14 27 59 71 81 273 412
Итерация 7 Неотсортированный 87
Отсортированный 14 27 59 71 81 87 273 412
В следующем алгоритме заводится только один список, и переорганизация чисел производится в старом списке.
Algorithm SIS (Сортировка Прямым включением). Отсортировать на старом месте последовательность целых чисел I(1), I(2), . . . ,I (N) в порядке возрастания.
Шаг 1. [ Основная итерация ]
For J← 2 to Ndo through шаг 4 od ;and STOP.
Шаг 2. [ Выбор следующего целого ] Set K← I(J); and L←J−1.
Шаг 3.
[ Сравнение с отсортированного целыми ] While
K AND L≥1 do set
I (L+1)←
I(L); and
L←L−1 od.
Шаг 4.
[ Включение ] Set
I(L+1)←K. QUICKSORT
:Алгоритм сортировки со средним временем работы О(N ln N)
Основная причина медленной работы алгоритма SIS заключается в том, что, все сравнения и обмены между ключами в последовательности а 1 , а 2 , . . . ,а N
происходят для пар из соседних элементов. При таком способе требуется относительно большое 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Строк 38 08 16 06 79 76 57 24 56 02 58 48 04 70 45 47Действие
1 38 47 уменьшение j 5 04 38 обмен 6 08 38 увеличение i 10 38 79 обмен 14 02 38 обмен 15 76 38 увеличение i,> 16 38 76 обмен 17 38 56 уменьшение j 19 24 38 обмен 20 57 38 увеличение i,> 21 38 57 обмен,уменьшение 22 04 08 16 06 02 24 38
57 56 76 58 48 79 70 45 47 (1 2 3 4 5 6) 7 (8 9 10 11 12 13 14 15 16) время, чтобы поставить ключ, находящийся не на месте, в нужную позицию в сортируемой последовательности. Естественно попытаться ускорить этот процесс, сравнивая пары элементов, находящихся далеко друг от друга в последовательности. К.Хоор изобрел и весьма эффективно применил эту идею (алгоритм QUICKSORT), сократив среднее время работы алгоритма SIS от порядка О(N 2) до порядка О(N ln N). Поясним этот алгоритм следующим примером. Предположим, что мы хотим отсортировать последовательность чисел из первой строки на рис. 15. Начнем с предположения, что первый
ключ в этой последовательности(38) служит хорошей аппроксимацией ключа, который в конечном счете появится в середине отсортированной последовательности. Используем это значение в качестве ведущего элемента, относительно которого ключи могут меняться местами, и продолжим следующим образом. Устанавливаем два указателя I и J , из которых I начинает отсчет слева (I=1) ,а J- слева в последовательности (J=N). Сравнивая а I
и а J
. Если а I ≤a J
, устанавливаем J←J−1 и проводим следующее сравнение. Продолжаем уменьшать
J до тех пор, пока не достигнем а I >а J .
Тогда поменяем местами а I ↔a J
(Рис.15 , строка 5 , обмен ключей 38 и 04), устанавливаем I←I+1 и продолжаем увеличивать
I до тех пор, пока не получим а I >а J .
После следующего обмена (строка 10, 79↔38) снова уменьшаем J. Чередуя уменьшение J и увеличение I , продолжаем этот процесс с обоих концов последовательности к «середине» до тех пор, пока не получим I=J. Теперь имеют место два факта. Во-первых,ключ(38),который сначала находился в первой позиции, к этому времени занимает надлежащее место в сортируемой последовательности. Во- первых,все ключи слева от этого элемента будут меньшими, а все ключи справа- большими. Ту же процедуру можно применить к левой и правой подпоследовательностям для окончательной сортировки всей последовательности. Последняя строка (с номером 22) рис.15 показывает, что когда будет получено I=J, то I=7. После этого процедура снова применяется к подпоследовательностям (1,6) и (8,16). Рекурсивный характер алгоритма наводит на мысль, что следует значения индексов крайних элементов большей из двух неотсортированных подпоследовательностей (8,16) поместить на стек и затем перейти к сортировке меньшей подпоследовательности (1,6). В строке 4 на рис.15 число 04 перешло в позицию 2 и сортировке подлежат подпоследовательности (1,1) и (3,6). Так как (1,1) уже отсортирована (число 02), сортируем (3,6), что в свою очередь ведет к строке 6 , в которой подлежат сортировке (3,4) и (6,6). В строке 7 подпоследовательность (1,6) отсортирована. Теперь извлекаем (8,16) из стека и начинаем сортировку этой подпоследовательности. В строке 13 находятся подпоследовательности (8,11) и (13,16), которые надо отсортировать. Помещаем (13,16) на стек, сортируем (8,11) и т.д. В строке 20 последовательность целиком отсортирована. Прежде чем описать алгоритм QUICKSORT формально, нужно точно показать,как он работает. Мы пользуемся стеком [ LEFT (K), RIGHT (K) ] для запоминания индексов крайних левого и правого элементов еще не не отсортированных подпоследовательностей. Так как короткие подпоследовательности быстрее сортируются при помощи обычного алгоритма, алгоритм QUICKSORT имеет входной параметр М, который определяет, насколько короткой должна бать подпоследовательность, чтобы ее сортировать обычным способом.Для этой цели пользуемся сортировкой простыми включениями (SIS). Поиск
Теперь обратимся к исследованию некоторых основных проблем, относящихся к поиску информации на стуктурах данных. Как и в предыдущем разделе, посвященному сортировки, будем предполагать, что вся информация хранится в записях, которые можно идентифицировать значениями ключей, т.е. записи R i соответствует значение ключа,обозначаемое K i . Предположим,что в файле расположены случайным образом N записей в виде линейного массива. Очевидным методом поиска заданной записи будет последовательный просмотр ключей. Если найден нужный ключ, поиск оканчивается успешно; в противном случае будут просмотрены все ключи, а поиск окажется безуспешным.Если все возможные порядки расположения ключей равновероятны, то такой алгоритм требует O(N) основных операций как в худшем, так и в среднем случаях. Время поиска можно заметно уменьшить, если предварительно упорядочить файл по ключам. Эта предварительная работа имеет смысл, если файл достаточно велик и к нему обращаются часто. Предположим, что мы обратились к середине файла и обнаружили там ключ K i . Сравним К и К i . Если К=К i , то нужная запись найдена. Если К<К i ,то ключ К должен находиться в части файла, предшествующей К i (если запись с ключом К вообще существует) . Аналогично, если К i <К, то дальнейший поиск следует вести в части файла, следующей за К i . Если повторять эту процедуру проверки ключа К i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К i будет исключать из рассмотрения приблизительно половину непросмотренной части. Блок-схема этой процедуры, известной под названием двоичный поиск
, приведена на рис.16 Algorithm
BSEARCH (Binary search- двоичный поиск) поиска записи с ключом К в файле с N≥2 записями, ключи которых упорядочены по возрастанию К 1 <К 2 …<К N . Шаг 0.
[Инициализация] Set
FIRST←1 ; LAST← N. (FIRST и LAST- указатели первого и последнего ключей в еще не просмотренной части файла.) Шаг 1.
[Основной цикл ] While
LAST≥FIRST do through
шаг 4 od.
Шаг 2.
[Получение центрального ключа] Set
I←|_(FIRST + LAST)/2_| .(К i - ключ, расположенный в середине или слева от середины еще не просмотренной части файла.) Шаг 3.
[Проверка на успешное завершение ] If
К=К I then
PRINT «Успешное окончание, ключ равен К I »;and
STOP fi.
Шаг 4.
[ Сравнение] If
K<
K I then set
LAST←I-1 else set
FIRST←I+1 fi.
Шаг 5.
[ Безуспешный поиск] PRINT «безуспешно»; and
STOP. Алгоритм BSEARCH используется для отыскания К=42 на рис.17. Метод двоичного поиска можно также применить для того, чтобы представить упорядоченный файл в виде двоичного дерева. Значение ключа, найденное при первом выполнении шага 2 (К(8)=53), является корнем дерева. Интервалы ключей слева (1,7) и справа (9,16) от этого значения помещаются на стек. Верхний интервал снимается со стека и с помощью шага 2 в нем отыскивается средний элемент (или элемент слева от середины). Этот ключ (К(4)=33) становится следующим после корня элементом влево, если его значение меньше значения корня, и следующим вправо в противном случае. Подынтервалы этого интервала справа и слева от вновь добавленного ключа [(1,3) , (5,7)] помещаются теперь на стек.Эта процедура повторяется до тех пор, пока стек не окажется пустым. На рис.18 показано двоичное дерево, которое было бы построено для 16 упорядоченных ключей с рис.17. Двоичный поиск можно теперь интерпретировать как прохождение этого дерева от корня до искомой записи. Если достигнута конечная вершина, а заданный ключ не найден, искомая запись в данном файле отсутствует. Заметим, что число вершин на единственном пути от корня к заданному ключу К равно числу сравнений, выполняемых алгоритмом BSEARCH при попытке отыскания К. Сортировка - это расположение данных в памяти в регулярном виде по выбранному параметру. Регулярность рассматривают как возрастание (убывание) значения параметра от начала к концу массива данных.
При обработке данных важно знать информационное поле данных и размещение их в машине.
Различают внутреннюю и внешнюю сортировку:
Внутренняя сортировка - сортировка в оперативной памяти;
Внешняя сортировка - сортировка во внешней памяти.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей
, то есть делают перестановку указателей, а сам массив не перемещается. Это - метод сортировки таблицы адресов.
При сортировке могут встретиться одинаковые ключи. В этом случае желательно после сортировки расположить одинаковые ключи в том же порядке, что и в исходном файле.
Это - устойчивая сортировка
.
Мы будем рассматривать только сортировки, не использующие дополнительную оперативную память. Такие сортировки называются «на том же месте»
.
Эффективность сортировки можно рассматривать по нескольким критериям:
Время, затрачиваемое на сортировку;
Объем оперативной памяти, требуемой для сортировки;
Время, затраченное программистом на написание программы.
Выделяем первый критерий. Эквивалентом затраченного на сортировку времени можно считать количество сравнений
и количество перемещений
при выполнении сортировки.
Порядок числа сравнений и перемещений при сортировке лежит в пределах
От О (n log n) до О (n 2);
О (n) - идеальный и недостижимый случай.
Различают следующие методы сортировки:
Строгие (прямые) методы;
Улучшенные методы.
Строгие методы:
Метод прямого включения;
Метод прямого выбора;
Метод прямого обмена.
Эффективность строгих методов примерно одинакова.
Элементы мысленно делятся на уже готовую последовательность a 1 ,...,a i-1 и исходную последовательность.
При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.
Суть алгоритма такова:
for i = 2 to n
X = a(i)
Находим место среди а(1)…а(i) для включения х
next i
Есть два алгоритма сортировки методом прямого включения. Первый - без барьера
Алгоритм сортировки методом прямого включения без барьера
for i = 2 to n
X = a(i)
For j = i - 1 downto 1
If x < a(j)
Then a(j + 1) = a(j)
Else go to L
Endif
Next j
L: a(j + 1) = x
next i
return
Недостатком приведенного алгоритма является нарушение технологии структурного программирования, при которой нежелательно применять безусловные переходы. Если же внутренний цикл организовать как цикл while , то необходима постановка «барьера», без которого при отрицательных значениях ключей происходит потеря значимости и «зависание» компьютера.
Алгоритм сортировки методом прямого включения с барьером
for i = 2 to n
X = a(i)
A(0) = x {a(0) - барьер}
J = i - 1
While x < a(j) do
A(j +1) = a(j)
J = j - 1
Endwhile
A(j +1) = x
next i
return
Число сравнений ключей Ci при i- м просеивании самое большее равно i-1, самое меньшее - 1; если предположить, что все перестановки из N ключей равновероятны, то среднее число сравнений = i/2. Число же пересылок Mi=Ci+3 (включая барьер). Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки - когда они первоначально расположены в обратном порядке. В некотором смысле сортировка с помощью включения демонстрирует истинно естественное поведение. Ясно, что приведенный алгоритм описывает процесс устойчивой сортировки: порядок элементов с равными ключами при нем остается неизменным.
Количество сравнений в худшем случае, когда массив отсортирован противоположным образом, С max = n(n - 1)/2, т. е. - О (n 2). Количество перестановок M max = C max + 3(n-1), т.е. - О (n 2). Если же массив уже отсортирован, то число сравнений и перестановок минимально: C min = n-1; M min = =3(n-1).
В данном разделе описан метод, где обмен местами двух элементов представляет собой характернейшую особенность процесса. Изложенный ниже алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы.
Мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (см. иллюстрацию на рисунке ниже).
C min = n - 1, порядок О(n),
а перемещения вообще отсутствуют
Сравнительный анализ прямых методов сортировок показывает, что обменная "сортировка" в классическом виде представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены приведенные выше усовершенствования, то для достаточно упорядоченных массивов пузырьковая сортировка даже имеет преимущество.
Такой метод широко известен под именем "пузырьковая сортировка". Алгоритм метода прямого обмена
for j = n to i step -1 if a(j) < a(j - 1) then В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не просматривать элементы, а значит проводить сравнения, затрачивая на это время, можно ввести флажок fl
, который остается в значении false
, если при очередном проходе не будет произведено ни одного обмена. На нижеприведенном алгоритме добавления отмечены жирным шрифтом. fl = true
if fl = false then return
fl = false
for j = n to i step -1 if a(j) < a(j - 1) then fl = true
Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление во внутреннем цикле. Число сравнений C max = n(n-1)/2 , порядок О(n 2).
Число перемещений М max =3C max =3n(n-1)/2, порядок О(n 2).
Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже «готовую» последовательность A 1 , A 2 ,…, A i -1 , и «оставшуюся» (не сортированную) часть: A i , A i +1 ,…, A N . Суть метода заключается в том, что при каждом i-ом шаге (начиная с i = 2), из неотсортированной части извлекается i-ый элемент и помещается в «готовую» часть, при этом он вставляется на нужное место. Текстовый алгоритм метода: 1. Начало. 2. Выполнить цикл, пока i имеет значения от 2 до N, а) i-ый элемент (A(i)) поместить в ячейку A(0); б) присвоить j = -1, то есть j равно номеру элемента, находящегося слева от испытуемого (i-го) и таким образом стоящего в «готовой» последовательности; в) если А(0) ≥ А(j), то элемент А(0) поместить в ячейку А(j+1), иначе элемент А(j) поместить в ячейку А(j+1), уменьшить значение j на единицу и вновь выполнить пункт в). На рис. 1 представлена блок-схема сортировки методом прямого включения. Метод работает следующим образом: на i-ом шаге (начиная с i = 2) i-ый элемент помещается в свободную ячейку (например, А(0)). Этот элемент сравнивается со стоящим в «готовой» части слева от него элементом. Если элемент А(0) меньше, то происходит сдвиг вправо сравниваемого (j-го элемента) на одну позицию, после чего для сравнения берется следующий элемент. Если же элемент А(0) при сравнении оказывается не меньше, то он помещается на место, стоящее сразу за сравниваемым элементом. Рис. 1. Блок-схема сортировки методом прямого включения На рис. 2 приведен пример выполнения сортировки методом прямого включения. Рис. 2. Пример сортировки методом прямого включения Сортировка прямым включением больше подходит для случая, когда сортируемые данные поступают последовательно (одно за другим). Сортировка методом прямого выбора
Суть метода заключается в следующем. Выбирается наименьший элемент в «оставшейся» (неотсортированной) части и меняется местами с первым элементом (в этой же неотсортированной части). После этого длина неотсортированной части уменьшается на один элемент (на первый), и весь процесс продолжается уже с (n – 1) элементами, затем с (n – 2) элементами и т.д., до тех пор, пока не останется один, самый большой элемент. Этот метод в некотором смысле противоположен методу прямого включения. В методе прямого включения на каждом шаге рассматривается только один очередной элемент и все элементы уже «готовой» части последовательности, среди которых отыскивается точка включения этого очередного элемента. А в методе прямого выбора для поиска одного (минимального) элемента просматривают все элементы неотсортированной части, и этот минимальный элемент помещается как очередной элемент в уже «готовую» часть. Текстовый алгоритм метода: 1. Начало. 2. Выполнить цикл, пока i имеет значения от 1 до N – 1, а) поместим текущий (i-ый) элемент в какую-нибудь ячейку памяти (Х) и запомним порядковый номер (i) текущего элемента (в переменной К); б) выполнить цикл, пока j имеет значения от i + 1 (то есть от следующего за i элемента) до N, шаг = +1: тело цикла: если Х > А(j), то помещаем в ячейку Х элемент А(j) и запоминаем его номер в ячейке К; в) присвоить А(К) = А(i) и А(i) = Х. На рис. 3 приведен пример выполнения сортировки методом прямого выбора. Рис. 3. Пример сортировки методом прямого выбора
Да
Сортировка методом прямого включения
Эффективность алгоритма прямого включения
Сортировка с помощью прямого обмена (пузырьковая сортировка)
Эффективность алгоритма сортировки прямым обменом
шаг = 1: Исходная последовательность
А (0)
I = 2
I = 3
I = 4
I = 5
I = 6
I = 7
I = 8
Результат
шаг = 1: Исходная последовательность
44
06
I = 1
55
12
I = 2
55
18
I = 3
42
55
I = 4
94
44
I = 5
55
94
I = 6
94
67
I = 7
