Методы сортировки данных в программировании. Методы сортировки массивов. Сравнительная характеристика методов сортировки

МЕТОДЫ СОРТИРОВКИ

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

Существует множество алгоритмов сортировки элементов. Наиболее простой из них - метод «пузырька». Алгоритм реализуется в виде двух вложенных циклов. Во внутреннем цикле просматриваются по порядку все элементы массива, попарно сравниваются рядом стоящие элементы, и если второй больше первого (при сортировке по убыванию) элементы меняются местами. Параметром внутреннего цикла является индекс(номер) элемента массива. Для полной сортировки такая перестановка должна быть выполнена n-1 раз, где n - количество элементов в массиве. Для этого организуется внешний цикл, параметром которого является шаг сортировки.

Пример. Отсортировать элементы одномерного массива целых чисел по возрастанию.

На рисунке 1 приведена последовательность перестановки элементов.

Рисунок 1. Сортировка методом «пузырька»

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

На рисунке 2 приведена блок-схема рассмотренного алгоритма.

Рисунок 2. Блок-схема алгоритма сортировки методом «пузырька»

Переменная m введена для возможности обмена значениями между двумя переменными, k отвечает за шаги сортировки.

Программа на языке С++ по данному алгоритму будет выглядеть следующим образом.

Рисунок 3. Программа сортировки элементов массива методом «пузырька»

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

Более эффективным является метод прямого выбора

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

Затем эта процедура повторяется, но поиск минимального (максимального) значения происходит уже со второй позиции и т.д. Схема этого алгоритм представлена на рисунке 4.

сортировка значение программный обеспечение

Рисунок 4. Сортировка методом прямого выбора

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

// сортируем элементы массива по возрастанию

int temp;//переменная для временного хранения при обмене значениями

int i;//переменная управления циклом (номер элемента массива)

int k;//переменная управления циклом (номер шага сортировки)

int nmin;//номер минимального значения

for (к=0; i < к 1; i++)

// ищем номер минимального элемента среди значений list [ i … n -1]

for (i = k+1; i< n; i++)

if (list[i] < list[ nmin ]) nmin = i;

//меняем местами list[ nmin ] и list[ k ]

temp = list[ nmin ];

list[ nmin ]= list[ k ];

list[ k ] = temp;

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

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

На днях в комментариях вконтакте у меня возник спор с одним из других студентов проекта. Суть спора заключалась в том, «кто кого» - метод sort() из класса java.util.Arrays или самописные реализации простых алгоритмов: bubble (пузырьковая), insertion (вставками), selection (выбором), shell (алгоритм Шелла). Для некоторых ответ на данный вопрос может быть очевиден, но раз спор возник, при том что у каждой из сторон были «уважаемые источники» в пользу своей точки зрения, было принято решение провести исследование, поразмяв в процессе серое вещество, реализуя различные алгоритмы. TL;DR: java.util.Arrays.sort() безоговорочно лидирует на массивах от 100 000 элементов, при меньшем размере с ним иногда может потягаться метод Шелла. Остальные рассмотренные алгоритмы сливают вчистую и могут быть полезны лишь при каких-то экзотических условиях. Теперь давайте рассмотрим, как же осуществляется сортировка массивов в наших убер-девайсах из кремния.

Selection sort. Сортировка выбором

Начнем с самого простого и очевидного способа. Суть его нам отлично демонстрирует Роберт Седжвик в своей видеолекции на coursera (привожу погано пережатую в gif мной анимацию оттуда): Пробегая по массиву с первого элемента, мы на каждом шаге ищем в правой части минимальный элемент, с которым и меняем местами текущий. В результате мы оставляем за собой окончательный вариант нашего массива в отсортированном виде. Вот код, реализующий этот алгоритм на Java: public void sort (int array) { int n = array. length; for (int i = 0 ; i < n; i ++ ) { int minIndex = min (array, i, n - 1 ) ; swap (array, i, minIndex) ; } } public static void swap (int array, int i, int j) { int temp = array[ i] ; array[ i] = array[ j] ; array[ j] = temp; } public static int min (int array, int begin, int end) { int minVal = array[ begin] ; int minIndex = begin; for (int i = begin + 1 ; i <= end; i++ ) { if (array[ i] < minVal) { minVal = array[ i] ; minIndex = i; } } return minIndex; } Анализ алгоритма показывает, что необходимо на каждом проходе прошерстить весть остаток массива, то есть нам понадобится ровно N + (N-1) + (N-2) + … + 1 = N^2/2 сравнений. Таким образом, сложность алгоритма составляет O(N^2). Что же это означает? А означает это, что, увеличив количество элементов в массиве (N) в 2 раза, мы увеличим время работы алгоритма не в 2, а в 2^2 = 4 раза. Увеличив N в 10 раз, время работы увеличим в 100 раз и так далее. На моем ноутбуке 2012 года с процессором Core i3 под Ubuntu 14.4 я получил следующее время работы:

Insertion sort. Сортировка вставками

Здесь идея несколько иная. Опять же, обратимся к анимации от Доктора Седжвика: То, что впереди, нами еще даже не просмотрено, а все что оставляем позади себя, всегда остается выстроенным по порядку. Суть в том, что каждый новый элемент исходного массива мы «возвращаем» к началу до тех пор, пока он не «упрется» в меньший элемент. Таким образом, у нас опять N проходов (для каждого элемента исходного массива), но в каждом проходе в большинстве случаев мы просматриваем не весь остаток, а только часть. То есть вариант 1 + (N-1) + (N-2) + … + N = N^2/2 мы получим, только если каждый следующий элемент нам придется возвращать к самому началу, то есть в случае отсортированного «наоборот» входного массива (не везет, так невезет). В случае же уже отсортированного массива (вот везуха ваще) будет полная халява – на каждом проходе всего одно сравнение и оставление элемента на месте, то есть отработает алгоритм за время, пропорциональное N. Сложность алгоритма же будет определяться худшим теоретическим случаем, то есть O(N^2). Среднестатистически же, время работы будет пропорционально N^2/4, то есть, вдвое быстрее предыдущего алгоритма. В моей реализации из-за неоптимального использования перестановки время работы получилось больше, чем у Selection. Планирую в ближайшее время исправить и обновить пост. Вот код и результат его работы на той же машине: public void sort (int array) { int length = array. length; for (int i = 1 ; i < length; i++ ) { for (int j = i; j >= 1 ; j-- ) { if (array[ j] < array[ j - 1 ] ) swap (array, j, j - 1 ) ; else break ; } } }

Shell sort. Сортировка Шелла

Умный мужик Дональд Шелл аж в 1959-м году заметил, что в алгоритме вставками дороже всего обходятся случаи, когда элемент возвращается очень далеко к началу массива: на каком-то проходе мы вернем элемент к началу на пару позиций, а на другом проходе почти через весь массив к началу – далеко и долго. Нельзя ли это сделать сразу, прыгая через несколько элементов? И такой способ он нашел. Заключается он в последовательном выполнении особых частичных сортировок, называемых в общем виде d-sort или, у Седжвика, h-sort (подозреваю, h означает hop - прыжок). 3-sort, например, будет сравнивать рассматриваемый элемент не с предыдущим, а пропустит два и сравнит с отстоящим на 3 позиции назад. Если поменяли, он его сравнит снова с элементом на 3 позиции назад и так далее. Суть в том, что полученный в результате массив будет «3-отсортирован», то есть неправильность положения элементов составит менее 3х позиций. Работать с таким алгоритму вставки будет легко и приятно. Кстати, «1-sort» является ничем иным, как просто алгоритмом вставки=) Последовательно применяя к массиву h-sort с уменьшающимся значением h, мы сможем отсортировать большой массив быстрее. Вот как это выглядит: Сложность здесь заключается в том, как выбрать правильную последовательность частичных сортировок. От этого, в итоге, зависит производительность алгоритма. Наиболее распространенной является последовательность, предложенная Дональдом Кнутом: h = h*3 + 1, то есть 1, 4, 13, 40, … и так до 1/3 размера массива. Такая последовательность обеспечивает достойную производительность, а также проста в реализации. Анализ алгоритма требует тонн матана и мной не осилен. Обширность анализа так же определяется множеством вариантов последовательностей h. Эмпирически же можно сказать, что скорость алгоритма весьма хороша – смотрите сами: Миллион элементов менее, чем за секунду! А вот код на Java с кнутовской последовательностью. public void sort (int array) { int h = 1 ; while (h* 3 < array. length) h = h * 3 + 1 ; while (h >= 1 ) { hSort (array, h) ; h = h/ 3 ; } } private void hSort (int array, int h) { int length = array. length; for (int i = h; i < length; i++ ) { for (int j = i; j >= h; j = j - h) { if (array[ j] < array[ j - h] ) swap (array, j, j - h) ; else break ; } } }

Bubble sort. Метод пузырька

Это классика! Этот алгоритм реализует почти каждый начинающий программист. Это настолько классика, что у Доктора Седжвика даже не нашлось анимации для него, потому мне пришлось потрудиться самому. Здесь на каждом проходе мы обходим массив с начала до конца, меняя местами соседние элементы, стоящие не по порядку. В результате самые крупные элементы «всплывают» (отсюда и название) в конец массива. Каждый новый проход мы начинаем, оптимистично надеясь, что массив уже отсортирован (sorted = true). В конце прохода, если мы видим, что ошиблись, начинаем новый проход. Сложность здесь заключается в том, что мы, опять же, обходим весь (почти) массив на каждом проходе. Сравнение происходит на каждом шаге, обмен - почти на каждом, что делает данный алгоритм одним из самых медленных (если рассматривать рационально реализованные, а не "сортировку встряхиванием" и прочие подобные). Интересно, что формально сложность и здесь будет равна O(N^2), только вот коэффициент гораздо выше, чем у вставок и выборов. Код алгоритма: public void sort (int array) { boolean isSorted; int nMinusOne = array. length - 1 ; for (int i = 0 ; i < nMinusOne; i++ ) { isSorted = true ; for (int j = 0 ; j < nMinusOne - i; j++ ) { if (array[ j] > array[ j + 1 ] ) { swap (array, j, j + 1 ) ; isSorted = false ; } } if (isSorted) return ; } } Время работы: Почувствуйте разницу: более получаса на миллионе элементов! Вывод: Никогда не исползуйте этот алгоритм!!!

Резюме первой части

Как итог предлагаю посмотреть общую таблицу для этих алгоритмов. Можете так же сравнить с результатами для встроенного метода java.util.Arrays.sort() . Похоже на какую-то магию - что же может быть быстрее Шелла? Об этом напишу в следующей части. Там мы рассмотрим широко применяемые алгоритмы быстрой сортировки, а также сортировки слиянием, узнаем о разнице в методах сортировки массивов из примитивов и ссылочных типов, а также познакомимся с очень важным в этом деле интерфейсом Comparable ;) Ниже можете изучить график, построенный в логарифмическом масштабе по данным таблицы. Чем более полого идет линия, тем лучше алгоритм =) Кто хочет скачать весь проект и прогнать тесты у себя, держите ссылку: Java До встречи в следующей части! =) Элементарные методы сортировки В качестве нашей первой экскурсии в область алгоритмов сортировки, мы изучим некоторые «элементарные» методы которые хорошо работают для небольших файлов или файлов специальной структуры. Существует несколько причин, по которым желательно изучение этих простых методов. Во-первых, они дают нам относительно безболезненный способ изучить терминологию и основные механизмы работы алгоритмов сортировки, что позволяет получить необходимую базу для изучения более сложных алгоритмов. Во-вторых, для многих задач сортировки бывает лучше использовать простые методы, чем более сложные алгоритмы. И, наконец, некоторые из простых методов можно расширить до более хороших методов или использовать их для улучшения более сложных.В некоторых программах сортировки лучше использовать простые алгоритмы. Программы сортировки часто используются только один раз (или несколько раз). Если количество элементов, которые нужно отсортировать не велико (скажем меньше чем 500 элементов), то может статься, что использование простого алгоритма будет более эффективно, чем разработка и отладка сложного алгоритма. Элементарные методы всегда пригодны для маленьких файлов (скажем меньших, чем 50 элементов); маловероятно, что сложный алгоритм было бы разумно использовать для таких файлов, если конечно не нужно сортировать большое количество таких файлов.Как правило, элементарные методы, которые мы будем обсуждать, производят около операций для сортировки N произвольно взятых элементов. Если N достаточно мало, то это может и не быть проблемой, и если элементы распределены не произвольным образом, то эти алгоритмы могут работать даже быстрее, чем сложные. Однако следует запомнить то, что эти алгоритмы не следует использовать для больших, произвольно упорядоченных файлов, с одним единственным исключением для алгоритма оболочечной сортировки, который часто используется во многих программах.Правила Игры

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

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

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

Количество используемой дополнительной памяти алгоритма сортировки - это еще один важный фактор, который мы будем принимать во внимание. Вообще говоря, методы сортировки делятся на три типа:

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

методы, которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;

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

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

Следующая программа, для сортировки трех записей, предназначена для иллюстрации основных соглашений, которые мы будем использовать. В частности, главная программа любопытна тем, что она работает только для N=3; смысл в том, что любая программа сортировки может быть сведена к процедуре sort3 этой программы.

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

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

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

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

Сортировка выбором Один из самых простых методов сортировки работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте. Потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементном и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором, поскольку он работает, циклически выбирая наименьший из оставшихся элементов, как показано на рисунке 1. При первом проходе символ пробела уходит на первое место, обмениваясь с буквой `П". На втором проходе элемент `В" обменивается с элементом `Р" и так далее.Следующая программа дает полную реализацию этого процесса. Для каждого i от 1 до N - 1 , она обменивает наименьший элемент из a [i ..N] с a[i ]:По мере продвижения указателя i слева направо через файл, элементы слева от указателя находятся уже в своей конечной позиции (и их больше уже не будут трогать), поэтому массив становится полностью отсортированным к тому моменту, когда указатель достигает правого края.Этот метод - один из простейших, и он работает очень хорошо для небольших файлов. Его «внутренний цикл» состоит из сравнения a[i ]min ] (плюс код необходимый для увеличения j и проверки на то, что он не превысил N ), что вряд ли можно еще упростить.Кроме того, хотя сортировка выбором является методом «грубой силы», он имеет очень важное применение: поскольку каждый элемент передвигается не более чем раз, то он очень хорош для больших записей с маленькими ключами.Сортировка вставкой Метод сортировки вставкой, почти столь же прост, что и сортировка выбором, но гораздо более гибкий. Этот метод часто используют при сортировке карт: берем один элемент и вставляем его в нужное место среди тех, что мы уже обработали (тем самым оставляя их отортированными).Рассматриваемый элемент вставляется в позицию посредством передвижения большего элемента на одну позицию вправо и затем размещением меньшего элемента в освободившуюся позицию, как показано на рисунке 2. Так `И" при третьем шаге меньше всех остальных отсортированных элементов, поэтому мы «топим» его в начало массива. `М» больше `И" но меньше всех остальных, поэтому мы помещаем его между `И" и `П", и так далее.Этот процесс реализован в следующей программе. Для каждого i от 2 до N , подмассив a сортируется посредством помещения a[i ] в подходящую позицию среди уже отсортированных элементов:Также как и при сортировке выбором, в процессе сортировки элементы слева от указателя i находятся уже в сортированном порядке, но они не обязательно находятся в своей последней позиции, поскольку их еще могут передвинуть направо чтобы вставить более маленькие элементы встреченные позже. Массив становится полностью сортированным когда указатель достигает правого края.Однако имеется еще одна важная деталь: программа insertion не всегда работает, поскольку while может проскочить за левый край массива, когда v - самый меньший элемент массива. Чтобы исправить ситуацию, мы помещаем «сторожевой» ключ в a, делая его, по крайней мере, не больше, чем самый маленький ключ массива. Сторожевые элементы повсеместно используются в ситуациях подобных этой для предотвращения дополнительной проверки (в данном случае j >0), что почти всегда помогает во внутренних циклах.Пузырьковая сортировка Элементарный метод сортировки, который часто дают на вводных занятиях - это пузырьковая сортировка : Стоящие рядом элементы массива обмениваются местами, до тех пор, пока встречаются неотсортированные пары. Реализация этого метода дана ниже.Чтобы поверить в то, что она на самом деле работает, может потребоваться некоторое время. Для этого заметьте, что когда во время первого прохода мы встречаем максимальный элемент, мы обмениваем его с каждым элементом справа от него пока он не окажется в крайней правой позиции. На втором проходе мы помещаем второй максимальный элемент в предпоследнюю позицию и так далее. Пузырьковая сортировка работает также как и сортировка выбором, хотя она и делает гораздо больше работы на то, чтобы переместить элемент в его конечную позицию.Характеристики простейших сортировок Свойство 1 Сортировка выбором использует около сравнений и N обменов. Свойство 2 Сортировка вставкой использует около сравнений и обменов в среднем, и в два раза больше в наихудшем случае. Свойство 3 Пузырьковая сортировка использует около сравнений и обменов в среднем и наихудшем случаях. Свойство 4 Сортировка вставкой линейна для «почти сортированных» файлов. Свойство 5 Сортировка выбором линейна для файлов с большими записями и маленькими ключами. Сортировка файлов с большими записями Очень часто бывает возможно (и желательно) сделать так, чтобы при сортировке файла состоящего из N элементов любом методом было бы сделано только N операций обмена полной записи посредством косвенной адресации к элементам массива (используя массив индексов или указателей), а саму реорганизацию делать после.Более конкретно: если массив a содержит большие записи, то мы предпочтем использовать массив указателей p для того, чтобы знать, где находится очередной элемент массива a, и для произведения псевдообмена. Ниже приведена программа сортировки вставкой с использованием массива указателей:Для предотвращения излишнего контроля в цикле, в программе опять используются «сторожевые» элементы.Изначально, индексы идут по порядку. Потом порядок индексов начинает меняться так, чтобы массив a, прочитанный по порядку чтения индексов был упорядочен.

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

Сортировка Шелла Сортировка вставкой работает медленно потому, что она обменивает только смежные элементы. Оболочечная сортировка является простейшим расширением сортировки вставкой, которая увеличивает скорость работы алгоритма за счет того, что позволяет обменивать элементы находящиеся далеко друг от друга.Основная идея алгоритма состоит в том, чтобы отсортировать все группы файла состоящие из элементов файла отстоящих друг от друга на расстояние h. Такие файлы называются h-сортированными. Когда мы h-сортируем файл по некоторому большому h, мы передвигаем его элементы на большие растояния. Это облегчает работу сортировки для меньших значений h. Процесс заканчивается когда h уменьшается до 1.

Приведенная программа использует последовательность… 1093, 364, 121, 40, 13, 4, 1. Могут существовать и другие последовательности - одни лучше, другие хуже.

Свойство 6 Оболочечная сортировка никогда не делает более чем N 1.5 сравнений для вышеуказанной последовательности h.

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

8 Сортировка вставкой

9 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом вставки Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. f f=1 f – условие выхода из цикла (если f=1, то выход) Val Val – промежуточное значение, используемое для перемещения элементов массив Постановка задачи

A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." class="link_thumb"> 10 10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма."> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма."> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма."> title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">

A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" class="link_thumb"> 11 11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает данное условие? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает данное условие?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает"> title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает">

A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" class="link_thumb"> 12 12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение j =2 ? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение j =2 ?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов"> title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">

A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" class="link_thumb"> 13 13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение i =2 ? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение i =2 ?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов"> title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">

A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" class="link_thumb"> 14 14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли происходит обмен входного j элемента с отсортированным элементом? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли происходит обмен входного j элемента с отсортированным элементом?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои"> title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои">

A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" class="link_thumb"> 15 15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли заменить цикл ПОКА и ЕСЛИ одним циклом ПОКА с условием i>=2 и A>A[i] ? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли заменить цикл ПОКА и ЕСЛИ одним циклом ПОКА с условием i>=2 и A>A[i] ?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за"> title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за">

A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" class="link_thumb"> 16 16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен этот оператор? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен этот оператор?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен"> title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен">

18 Суть сортировки: Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.

Сортировка выбором Отсортиро- ванная часть Отсортированная часть Массив отсортирован по возрастанию

20 Постановка задачи А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом выбора. Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. min min – минимальное число в массиве. Imin Imin – номер минимального числа в массиве

25 Суть сортировки: Последовательно просматривается массив и сравнивается каждая пара элементов между собой. При этом "неправильное" расположение элементов устраняется путем их перестановки. Процесс просмотра и сравнения элементов повторяется до просмотра всего массива.

26 Сортировка обменом

27 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом обмена Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. Val Val – промежуточное значение, используемое для перемещения элементов массива Постановка задачи

2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" class="link_thumb"> 28 28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседних элементов Обмен соседних элементов местами, в случае если левый больше правого Формируется отсортированная часть =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседних элементов Обмен соседних элементов местами, в случае если левый больше правого Формируется отсортированная часть"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни"> title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни">

2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" class="link_thumb"> 29 29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие такое? =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие такое?"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та"> title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та">

2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" class="link_thumb"> 30 30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j уменьшается? Можно ли увеличивать? Что нужно изменить? =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j уменьшается? Можно ли увеличивать? Что нужно изменить?"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j"> title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j">

35 12 Сортировка Шелла шаг. 4 группы из 2-х элементов шаг. 2 группы из 4-х элементов

36 Сортировка Шелла шаг. 1 группа из 8-ми элементов Массив отсортирован по возрастанию

37 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом Шелла Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. M M- оптимальный шаг P P– промежуточное значение, используемое для перемещения элементов массива Постановка задачи

45 Суть сортировки: Выбирается некоторое значение (x)- барьерный элемент, который определяется округлением до целого деления количества сортируемых элементов на 2; Просматриваем массив, двигаясь слева направо, пока не найдется элемент, больший x Затем просматриваем его справа налево, пока не найдется элемент, меньший x

46 Суть сортировки: Меняем найденные элементы местами. В случае, если не найден наибольший или наименьший элементы, местами меняется средний элемент с найденным наибольшим или наименьшим элементом; Дойдя до середины имеем 2 части массива; Процесс продолжается для каждой части, пока массив не будет отсортирован

7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" class="link_thumb"> 47 47 Быстрая сортировка Барьерный элемент Барьерный элемент Барьерный элемент >7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэтому меняем местами 7 и 12 4>3 Отсортиро- ванная часть 12>11 переносим в правую часть, т. к >11 не переносим, 811 переносим в правую часть, т. к. 16>11, 12>11,не переносим, 11 11=11 поэтому меняем местами 11 и 19 Отсортированная часть 19>12 переносим в правую часть, т. к. 16>12,не переносим, 12 12=12 поэтому меняем местами 12 и 19 19>16 Массив отсортирован по возрастанию Меньше равно 7 Больше 7 7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт"> 7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэтому меняем местами 7 и 12 4>3 Отсортиро- ванная часть 12>11 переносим в правую часть, т. к. 8 12 16>11 не переносим, 811 переносим в правую часть, т. к. 16>11, 12>11,не переносим, 11 11=11 поэтому меняем местами 11 и 19 Отсортированная часть 19>12 переносим в правую часть, т. к. 16>12,не переносим, 12 12=12 поэтому меняем местами 12 и 19 19>16 Массив отсортирован по возрастанию Меньше равно 7 Больше 7"> 7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт"> title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт">

48 А n Пусть нужно отсортировать массив А по возрастанию, в котором n элементов быстрым методом Вспомогательные переменные: t – t –конечный элемент массива m - m - начальный элемент массива x – x – элемент относительно которого перемещаются все остальные элементы. w – w – промежуточное значение, используемое для перемещения элементов массива Постановка задачи

58 Устойчивость – отсортированный массив не меняет порядок элементов с одинаковыми значениями. Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" Параметры оценки алгоритмов

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

60 Оценка алгоритма сортировки выбором Общее количество сравнений C =N-l + N = (N 2 -N)/2 Общее количество операций n + (n-1) + (n-2) + (n-3) = 1/2 * (n 2 +n) = Theta(n 2) Число обменов

63 Оценка алгоритма сортировки вставкой Для массива потребуется N-1 сравнение. Для массива потребуется (N 2 -N)/2 сравнение. Общее количество операций Theta(n 2)

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

70 Сравнение методов простой сортировки N N – количество элементов, M M – кол-во пересылок, C – кол-во сравнений МинимумМаксимум Простые включения M=2(n-1) C = n-1 M=2(n-1) С=(n 2 -n)/2 М=(n+3n-4)/2 М=(n 2 +3n-4)/2 Простой обмен C=(n 2 -n)/2M=3(n-1) С=(n 2 -n)/2 М=n/4+3(n-1) М=n 2 /4+3(n-1) Простой выбор C=(n 2 -n)/2 M = 0 С=(n 2 -n)/2 М=(n-n)*1,5 М=(n 2 -n)*1,5 ? Чему будет равно количество пересылок

72 Оценка алгоритма Шелла n 1.2 Время выполнения пропорционально n 1.2, т. к. при каждом проходе используется небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных

73 Оценка алгоритма быстрой сортировки N=2g X N N/2N/2 Если размер массива равен числу, являющемуся степенью двойки (N=2g), и при каждом разделении элемент X находится точно в середине массива, тогда при первом просмотре выполняется N сравнений и массив разделится на две части размерами N/2. Для каждой из этих частей N/2 сравнений и т. д. Следовательно C=N+2*(N/2)+4*(N/4)+...+N*(N/N). N Если N не является степенью двойки, то оценка будет иметь тот же порядок

74 Theta(n). Общее количество операций Theta(n). log n O(n log n) Количество шагов деления (глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n) O(n 2) Если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности, тогда быстродействие O(n 2)

77 Контрольные вопросы? Что такое «сортировка»? ? В чем заключается метод сортировки отбором? ? В чем заключается метод сортировки вставками? ? В чем заключается метод пузырьковой сортировки? ? В чем заключается метод быстрой сортировки? ? В чем заключается метод сортировки Шелла?

78 Контрольные вопросы? Какой алгоритм сортировки считается самым простым? ? Какой алгоритм сортировки считается самым эффективным? ? Сколько существует групп алгоритмов сортировки? ? По каким признакам характеризуются алгоритмы сортировки? ? Что нужно учитывать при выборе алгоритма сортировки?

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

Откуда взялось такое необычное название?

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

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

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

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

Еще короче алгоритм будущей программы можно записать так:

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

Псевдокод на основе описанного алгоритма

Самая простая реализация выполняется так:

Процедура Sortirovka_Puzirkom ;

Начало

цикл для j от nachalnii_index до konechii_index ;

цикл для i от nachalnii_index до konechii_index-1 ;

если massiv[i]>massiv

(меняем значения местами);

Конец

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

Потребовалась реализация получше. Например, учитывающая обмен значений в массиве местами:

Процедура Sortirovka_Puzirkom ;

Начало

sortirovka = истина;

цикл пока sortirovka = истина;

sortirovka = ложь;

цикл для i от nachalnii_index до konechii_index-1 ;

если massiv[i]>massiv (первый элемент больше второго), то:

(меняем элементы местами);

sortirovka = истина; (обозначили, что обмен был произведен).

Конец.

Недостатки метода

Основной минус - продолжительность процесса. Сколько же времени выполняется пузырьком?

Время выполнения рассчитывается из квадрата количества чисел в массиве - конечный результат ему пропорционален.

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

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

Достоинства

Сортировка пузырьком весьма проста для понимания. В учебных программах технических ВУЗов при изучении упорядочивания элементов массива ее проходят в первую очередь. Метод легко реализуется как на языке программирования Delphi (Д (Делфи), так и на C/C++ (Си/Си плюс плюс), невероятно простой алгоритм расположения значений в верном порядке и на Сортировка пузырьком идеально подходит для начинающих.

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