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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Pascal | Лекция №7

Методы упорядочивания данных

СОДЕРЖАНИЕ:

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

Она заключается в следующем: задан список целых чисел (простейший случай) B = . Требуется переставить элементы списка B так, чтобы получить упорядоченный список B’ = , в котором для любого 1

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

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

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

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

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

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

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

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

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

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

B = — исходный список;

B1 = — первый просмотр;

B2 = — второй просмотр;

B? = B3 = — третий просмотр.

В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса 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 = имеем:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Важно знать.

На практике алгоритм Шелла целесообразнее применять, если n 3 элементов. Теоретически показано, что трудоемкость оптимального алгоритма сортировки должна быть

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

Контрольные вопросы

Источник

Урок 28. Сортировка массива

Урок из серии: «Программирование на языке Паскаль»

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

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

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

При сортировке массива методом выбора применяется базовый алгоритм поиска максимального (минимального) элемента и его номера.

Алгоритм сортировки массива методом выбора:

Для упорядочения массива потребуется (n-1) просмотров массива. В процессе сортировки будет увеличиваться отсортированная часть массива, а неотсортированная, соответственно, уменьшаться.

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

Задача 1. Массив из 10 элементов отсортировать по возрастанию методом простого перебора.

Напишем процедуру. Входным параметром для неё будет массив. Он же будет и выходным параметром. Поэтому описываем его как параметр-переменная (с ключевым словом var).

В процедуре внешний цикл по i — определяет длину рассматриваемой части массива. Она будет изменяться от n до 2.

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

Программный код процедуры:

Программный код основной программы:

Процесс упорядочения элементов в массиве по возрастанию методом отбора:

Источник

Как отсортировать массив в паскале

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник