Как упорядочить массив по возрастанию паскаль

Сортировка методом пузырька

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

Решение

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

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

Сортировка одномерных массивов по убыванию и возрастанию в 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, условие выполняется значит опять местами.

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

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

Pascal | Лекция №7

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

Она заключается в следующем: задан список целых чисел (простейший случай) B = < B₁, B₂, …, B_n>. Требуется переставить элементы списка B так, чтобы получить упорядоченный список B’ = < B’₁, B’₂, …, B’_n>, в котором для любого 1 <= i <= n элемент B_i <= B_i+1. Другими словами — упорядочить список по возрастанию.

Для решения данной задачи существуют различные методы. Практически каждый алгоритм сортировки можно разбить на три части:

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

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

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

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

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

Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:

• сортировка обменом;
• сортировка выбором;
• сортировка вставкой.

Сортировка «методом пузырька»

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

B’ получается из B систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.

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

Идея метода: производится последовательное упорядочивание смежных элементов массива: B₁ и B2, B₂ и B3, …, B_n-1 и B_n. В итоге максимальное значение переместится в B_n. Затем ту же процедуру повторяют до B_n-1 и т.д., вплоть до цепочки из двух элементов B₁ и B2.

B = < 20, -5, 10, 8, 7> — исходный список;

B1 = < -5, 10, 8, 7, 20> — первый просмотр;

B2 = < -5, 8, 7, 10, 20> — второй просмотр;

B? = B3 = < -5, 7, 8, 10, 20> — третий просмотр.

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

Ниже приведенная процедура сортирует исходный массив методом пузырьковой сортировки, начиная с элемента с номером m и заканчивая элементом с номером n.

/* Сортировка пузырьковым методом */

Пузырьковая сортировка выполняется при количестве действий Q=(n-m)*(n-m) и не требует дополнительной памяти.

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

Требуется упорядочить массив B, состоящий из N элементов. Пусть B₁, B₂, …, B_i-1 уже отсортированная часть массива B, а B_i, B_i+1, …, B_n не отсортированная. Идея метода:

• выбираем очередной элемент B_i (начинаем с i=1);
• в упорядоченной части массива находим k-ое место, такое чтобы при вставке на это место элемента B_i порядок не нарушился;
• все элементы начиная с B_k–го до B_i-1 сдвигаем на одну позицию вправо и вставляем элемент B_i на k-ое место;
• повторяем пункты 1-3 до тех пор пока i <N.

Например, для начального списка B = < 20, -5, 10, 8, 7> имеем:

При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.

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

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

При сортировке посредством выбора требуется Q=(n-m)*(n-m) действий и не требуется дополнительной памяти.

Пример программы с процедурами сортировки простого выбора (SortVybor) и простой вставки (SortVstav):

Быстрая сортировка (сортировка Хоара)

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

Рассмотрим этот метод подробнее. Быстрая сортировка состоит в том, что список B=<K₁, K₂, …, K_n> реорганизуется в список <K₁>, , где — подсписок B с элементами не большими K₁, а — подсписок B с элементами большими K₁. В списке <K₁>, элемент <K₁> расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам и снова применяется упорядочивание быстрой сортировкой.

Время работы по сортировке списка методом быстрой сортировки зависит от упорядоченности списка. Оно будет минимальным, если на каждом шаге разбиения получаются подписки B’ и B» приблизительно равной длины, и тогда требуется около N*log2(N) шагов. Если список близок к упорядоченному, то требуется около (N*N)/2 шагов. Быстрая сортировка требует дополнительной памяти порядка log2(N).

Пример программы, использующий сортировку Хоара:

Сортировка Шелла

Алгоритм предложен в 1959 году как усовершенствование метода простых вставок. Является самым простым среди улучшенных алгоритмов сортировки. Может работать и как улучшенный метод простого обмена (метод «пузырька»).

alt=»123″ width=»437″ height=»110″ />
Идея метода состоит в следующем: сначала переставлять элементы на большие расстояния, а затем расстояния сужать. Расстояние между сравниваемыми элементами задается с помощью вспомогательной величины h – шага перестановки элементов. На каждом этапе рассматриваются a_i и a_i+h.В «пузырьке» сравниваем соседние элементы. Но если в массиве элементы стоят далеко от своего истинного места, то придется совершить очень много перестановок.

При заданных h и начальном значении i все рассматриваемые на данном этапе элементы образуют цепочку. Если изменить i, то получим другие цепочки. На каждом этапе сортировки h – уменьшается.

При уменьшении шага h количество цепочек уменьшается, а длина их возрастает. На самом последнем этапе h=1 (обязательно!), и весь массив представляет собой цепочку. «Пузырек» — частный случай алгоритма Шелла при h=1. Пример сортировки методом Шелла:

Таким образом, мы видим, что внешне процесс существенно усложняется: вместо одной сортировки необходимо несколько (при каждом h — несколько цепочек и для каждой нужно провести сортировку). В чем же преимущество?

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

Теперь запишем весь алгоритм.

Важно знать.

На практике алгоритм Шелла целесообразнее применять, если n<=(1-5)·10 3 элементов. Теоретически показано, что трудоемкость оптимального алгоритма сортировки должна быть

Для небольших n нецелесообразно применять сложные алгоритмы. Но при больших n улучшенные алгоритмы имеют преимущества.