Сортировка одномерных массивов по убыванию и возрастанию в Pascal.
В чем заключается вопрос: Как организовать сортировку массивов по убыванию и возрастанию в Паскаль. Метод пузырька.
Сложность : средняя .
Довольно таки частый вопрос у начинающих программистов. Попробуем разобраться. Суть метода в том чтобы менять местами СОСЕДНИЕ числа пока наибольшее не окажется справа, но это для сортировки по возрастанию, пример:
Естественно есть готовый код, который мы сейчас и разберем:
Массив mass, n кол-во элементов массива, i и j для циклов, buf для того чтобы поменять числа местами. Как я и сказал суть в том чтобы поменять местами соседние элементы пока не от сортируется. Давайте пока забудем про приведенный выше код и напишем следующее:
Мы меняем соседние элементы местами, СОСЕДНИЕ. , цикл до n-1, потому что у последнего элемента массива соседнего элемента нету.
Что же делает этот цикл, он само собой поменяет местами соседние элементы при выполнении условия, что левый больше правого, т.е. например ( 3 , 2 ), 3 больше 2 значит поменяем местами.
После прохода этого цикла ХОТЬ КАК найдется наибольший элемент, т.е. он встанет в самый конец.
Сначала у нас j = 1, j + 1 = 2, т.е. сначала сравняться числа 5 и 2, они поменяются местами, потом j=2, j+1=3,
т.е. j = 2, там у нас уже 5, а в j = 3, у нас 3, условие выполняется значит опять местами.
И так пока цикл не кончиться, в итоге получиться что у нас в самом конце будет самый наибольший элемент. ВСЁЁЁЁЁ, у нас есть последний элемент.
Теперь когда мы запустим цикл еще раз у нас найдется предпоследний элемент, и так пока не от сортируется. Но сколько раз надо выполнить такой цикл спросите вы. Давайте попробуем выполнять его столько раз сколько у нас кол-во элементов массива, вроде логично звучит.
Всё работает правильно, можете проверить но все работает абсолютно ПРАВИЛЬНО. Теперь давайте сравним наш код с образцом:
Есть два отличия:
По поводу 1-го, не заморачивайте голову, можете оставить и просто n, но как видно что нам хватит на один проход меньше чтобы отсортировать массив, вот и всё.
По поводу 2-го, это значит что количество проверяемых чисел станет меньше, что это значит. Вот когда у нас идет первый цикл, у нас проверяются все числа и мы находим самый последний элемент, он у нас хоть как самый большой и больше смысла проверять его просто нет. Когда пойдет уже второй цикл у нас это число просто не будет затрагиваться вот и всё, а какой смысл его затрагивать ведь оно и так самое больше? И так после каждого прохода цикла )))
Пффффф… надеюсь вы поняли, да и еще это была сортировка по возрастанию чтобы сделать сортировку по убыванию достаточно просто понять знак в условии:
Готовый код задачи на сортировку массива по возрастанию:
Сортировка массива по возрастанию паскаль
Категории:
Свежие
комментарии:
Полина:
Мы такие задачи решаем в 6 классе. Как раз вчера по инф..
Олег:
Спасибо, все очень подробно написано..
Калужский Александр:
Можете мне заказать.
Сортировка пузырьком (Pascal)
Сегодня мы разберем сортировку методом «пузырька». Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка — это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.
Существуют различные алгоритмы сортировки. Некоторые, хорошо сортируют большое количество элементов, другие, более эффективны при очень маленьком количестве элементов. Наш метод пузырька характерен:
Плюсы:
- Простота реализации алгоритма
- Красивое название
Минусы:
- Один из самых медленных методов сортировки (Время выполнения квадратично зависит от длины массива n 2 )
- Почти не применяется в реальной жизни (используется в основном в учебных целях)
Пусть есть у нас некий массив: 3 1 4 2
Алгоритм: Берем элемент массива, сравниваем со следующим, если наш элемент, больше следующего элемента, то мы их меняем местами. После прохождения всего массива, мы можем быть уверены, что максимальный элемент будет «вытолкнут» — и стоять самым последним. Таким образом, один элемент у нас уже точно стоит на своём месте. Т.к. нам надо их все расположить на свои места, следовательно, мы должны повторить данную операцию, столько раз, сколько у нас элементов массива минус 1. Последний элемент встанет автоматически, если остальные стоят на своих местах.
Вернемся к нашему массиву : 3 1 4 2
Берем первый элемент «3» сравниваем со следующим «1». Т.к. «3» > «1», то меняем местами:
1 3 4 2
Теперь сравниваем «3» и «4», тройка не больше четвёрки, значит ничего не делаем. Далее, сравниваем «4» и «2». Четыре больше, чем два — значит меняем местами: 1 3 2 4 . Цикл закончился. Значит самый большой элемент уже должен стоять на своём месте!! Видим, что у нас так и произошло. Где бы «4» (наш самый большой элемент) не находился — он всё равно, после прохождения циклом всего массива, будет последним. Аналогия — как пузырёк воздуха всплывает в воде — так и наш элемент, всплывает в массиве. Поэтому и алгоритм, называется «Пузырьковая сортировка». Чтобы расположить следующий элемент, необходимо, начать цикл сначала, но последний элемент можно уже не рассматривать, потому что он стоит на своём месте.
Сравниваем «1» и «3» — ничего не меняем.
Сравниваем «3» и «2» — Три больше двух, значит меняем местами. Получается : 1 2 3 4 . Второй цикл закончили. Мы сделали уже два цикла — значит, с уверенностью можно сказать, что у нас, два последних элемента уже отсортированы. Осталось нам отсортировать третий элемент, а четвёртый, встанет в нужное место, автоматически. Ещё раз, сравниваем первый элемент и второй — видим, что у нас уже всё на своих местах, значит, массив, можно считать, отсортированный по возрастанию элементов.
Теперь осталось запрограммировать данный алгоритм на языке Pascal.
Вот результат: 
А вот видеоурок
Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.
- количество шагов алгоритма, необходимых для упорядочения;
- количество сравнений элементов;
- количество перестановок, выполняемых при сортировке.
Мы рассмотрим только три простейшие схемы сортировки.
Метод «пузырька»
По-видимому, самым простым методом сортировки является так называемый метод » пузырька «. Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход «снизу», берется первый элемент и поочередно сравнивается с последующими. При этом:
В результате наибольший элемент оказывается в самом верху массива.
Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д.
Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее «всплывшие» элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j -го прохода не проверяются элементы, стоящие на позициях выше j .
Теперь можно привести текст программы упорядочения массива M[1..N] :
| begin for j :=1 to N -1 do for i :=1 to N — j do if M[ i ] > M[ i +1] then swap (M[ i ],M[ i +1]) end; |
Стандартная процедура swap будет использоваться и в остальных алгоритмах сортировки для перестановки элементов (их тип мы уточнять не будем) местами:
procedure swap (var x,y: . );
var t: . ;
begin
t := x;
x := y;
y := t
end;
Заметим, что если массив M глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.
Применение метода «пузырька» можно проследить здесь.
Сортировка вставками
Второй метод называется метод вставок ., т.к. на j -ом этапе мы «вставляем» j -ый элемент M[j] в нужную позицию среди элементов M[1] , M[2] ,. . ., M[j-1] , которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
Сказанное можно записать следующим образом:
Чтобы сделать процесс перемещения элемента M[j] , более простым, полезно воспользоваться барьером: ввести «фиктивный» элемент M[0] , чье значение будет заведомо меньше значения любого из «реальных»элементов массива (как это можно сделать?). Мы обозначим это значение через оо.
Если барьер не использовать, то перед вставкой M[j] , в позицию i-1 надо проверить, не будет ли i=1 . Если нет, тогда сравнить M[j] ( который в этот момент будет находиться в позиции i ) с элементом M[i-1].
Описанный алгоритм имеет следующий вид:
| begin M[0] := -oo; for j :=2 to N do begin i := j ; while M[ i ] M[ i — 1] do begin swap (M[ i ],M[ i -1]); i := i -1 end end end; |
Процедура swap нам уже встречалась.
Сортировка посредством выбора
Идея сортировки с помощью выбора не сложнее двух предыдущих. На j -ом этапе выбирается элемент наименьший среди M[j] , M[j+1] ,. . ., M[N] (см. процедуру FindMin ) и меняется местами с элементом M[j] . В результате после j -го этапа все элементы M[j] , M[j+1] ,. . ., M[N] будут упорядочены.
Сказанное можно описать следующим образом:
нц для j от 1 до N-1
выбрать среди M[j] ,. . ., M[N] наименьший элемент и
поменять его местами с M[j]
кц
| begin for j :=1 to N -1 do begin FindMin ( j , i ); swap (M[ j ],M[ i ]) end end; |
В программе, как уже было сказано, используется процедура FindMin , вычисляющая индекс lowindex элемента, наименьшего среди элементов массива с индексами не меньше, чем startindex :
procedure FindMin (start index : integer; var lowindex : integer );
var lowelem: . ;
u: integer;
begin
lowindex := start index ;
lowelem := M[startindex];
for u:= start index +1 to N do
if M[u] lowelem then
begin
lowelem := M[u];
lowindex := u
end
end;
Оценивая эффективность применения , учтите что в демонстрации сортировки выбором отсутствует пошаговое выполнение этой процедуры.
Урок 28. Сортировка массива
Урок из серии: «Программирование на языке Паскаль»
Процесс обработки и поиска информации при решении многих задач проходит быстрее и эффективнее, если данные расположены в определенном порядке. Например, различные списки студентов, учащихся, сотрудников — в алфавитном порядке, числовые данные от большего значения к меньшему (или наоборот) и т.д.
Существует довольно много различных методов сортировки массивов, отличающихся друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки. Рассмотрим подробно некоторые из них.
Сортировка массива методом простого выбора
При сортировке массива методом выбора применяется базовый алгоритм поиска максимального (минимального) элемента и его номера.
Алгоритм сортировки массива методом выбора:
- Для исходного массива выбрать максимальный элемент.
- Поменять его местами с последним элементом (после этого самый большой элемент будет стоять на своем месте).
- Повторить п.п. 1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в нем максимальный элемент и поменять его местамис предпоследним (n-1)- м элементом массива, затем с оставшиеся (n-2)-мя элементами и так далее, пока не останется один элемент, уже стоящий на своем месте.
Для упорядочения массива потребуется (n-1) просмотров массива. В процессе сортировки будет увеличиваться отсортированная часть массива, а неотсортированная, соответственно, уменьшаться.
При сортировке данных выполняется обмен содержимого переменных. Для обмена необходимо создавать временную переменную, в которой будет храниться содержимое одной из переменных. В противном случае ее содержимое окажется утерянным.
Задача 1. Массив из 10 элементов отсортировать по возрастанию методом простого перебора.
Напишем процедуру. Входным параметром для неё будет массив. Он же будет и выходным параметром. Поэтому описываем его как параметр-переменная (с ключевым словом var).
В процедуре внешний цикл по i — определяет длину рассматриваемой части массива. Она будет изменяться от n до 2.
Внутренний цикл по j используется для поиска максимального элемента и его номера. В качестве начального значения максимума разумно взять значение последнего элемента рассматриваемой части массива.
Программный код процедуры:
Программный код основной программы:
Процесс упорядочения элементов в массиве по возрастанию методом отбора:
| Номер элемента | 1 | 2 | 3 | 4 | 5 |
| Исходный массив | 8 | 7 | 5 | 4 | 2 |
| Первый просмотр | 2 | 7 | 5 | 4 | 8 |
| Второй просмотр | 2 | 4 | 5 | 7 | 8 |
| Третий просмотр | 2 | 4 | 5 | 7 | 8 |
| Четвертый просмотр | 2 | 4 | 5 | 7 | 8 |
При упорядочивании массива по убыванию необходимо перемещать минимальный элемент. Для чего в алгоритме нахождения максимального элемента достаточно знак «>» поменять на знак « » заменить на «