Сортировка одномерных массивов по убыванию и возрастанию в 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-го, это значит что количество проверяемых чисел станет меньше, что это значит. Вот когда у нас идет первый цикл, у нас проверяются все числа и мы находим самый последний элемент, он у нас хоть как самый большой и больше смысла проверять его просто нет. Когда пойдет уже второй цикл у нас это число просто не будет затрагиваться вот и всё, а какой смысл его затрагивать ведь оно и так самое больше? И так после каждого прохода цикла )))
Пффффф… надеюсь вы поняли, да и еще это была сортировка по возрастанию чтобы сделать сортировку по убыванию достаточно просто понять знак в условии:
Готовый код задачи на сортировку массива по возрастанию:
Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.
- количество шагов алгоритма, необходимых для упорядочения;
- количество сравнений элементов;
- количество перестановок, выполняемых при сортировке.
Мы рассмотрим только три простейшие схемы сортировки.
Метод «пузырька»
По-видимому, самым простым методом сортировки является так называемый метод » пузырька «. Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход «снизу», берется первый элемент и поочередно сравнивается с последующими. При этом:
В результате наибольший элемент оказывается в самом верху массива.
Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д.
Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее «всплывшие» элементы, т.к. они заведомо больше оставшихся. Другими словами, во время 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;
Оценивая эффективность применения , учтите что в демонстрации сортировки выбором отсутствует пошаговое выполнение этой процедуры.
Отсортировать массив по возрастанию
Решите эти задачи пожалуйста очень надо.
1. Организуйте массив, содержащий 20 различных целых чисел. После этого элементы массива упорядочиваются по убыванию и содержимое отсортированного массива выводится на экран.
2. Организуйте массив, содержащий 20 различных целых чисел. После этого 10 первых элементов массива упорядочиваются по возрастанию , а 10 последних элементов по убыванию. Содержимое таким образом отсортированного массива выводится на экран.
3. Организуйте массив, содержащий 15 различных целых чисел. После этого первых 5 элементов, вторых 5 элементов и последних 5 элементов сортируются по возрастанию. Содержимое таким образом отсортированного массива выводится на экран.
4. Организуйте массив, содержащий 10 различных целых чисел. Одержимое массива сортируется по возрастанию, и после этого определяется минимальный и максимальный элементы массива.
5. Организуйте массив, содержащий 20 различных символов. Отсортируйте его по возрастанию.
6. Организуйте массив, содержащий 20 целых чисел. Отсортируйте отдельно элементы с четными индексами по возрастанию, и элементы с нечетными индексами по убыванию.
7. Организуйте массив, содержащий 20 целых чисел. Отсортируйте его по возрастанию. После этого определите и выведите на экран сумму элементов с четными индексами и сумму элементов с нечетными индексами.
8. Создайте массив, содержащий 15 целых чисел. Отдельно первых 5 элементов массива вторых 5 элементов и последних 5 элементов отсортируйте по убыванию. Определите и выведите на экран сумму каждой пятерки отсортированного таким образом массива.
9. Создайте массив, содержащий 15 различных символов. Отсортируйте его по убыванию. После этого определите и выведите на экран «наименьший» и «наибольший» символы.
10. Создайте массив, содержащий 10 различных символов. Первую половину массива отсортируйте по возрастанию, а вторую по убыванию. Отсортированный массив выведите на экран.
11. Создайте массив А, содержащий 8 различных символов. Отсортируйте его по возрастанию. Организуйте и выведите на экран целочисленный массив В, заполнив его числами, полученными преобразованием символов массива А в целые числа.
12. Создайте целочисленный массив А, содержащий 10 различных чисел. Отсортируйте первую половину массива А по возрастанию, а вторую по убыванию. Организуйте и выведите на экран символьный массив В, заполнив его символами, полученными преобразованием чисел массива А в символы.
13. Создайте массив содержащий 20 различных целых чисел. Отсортируйте его по возрастанию. После этого замените все элементы массива на противоположные и выведите содержимое обработанного массива на экран.
14. Создайте массив содержащий 20 различных целых чисел. Отсортируйте первую половину массива по возрастанию, а вторую по убыванию. Все четные элементы массива увеличить в 3 раза, а нечетные в 2 раза. Содержимое таким образом отсортированного массива выводится на экран.
Урок 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 |
При упорядочивании массива по убыванию необходимо перемещать минимальный элемент. Для чего в алгоритме нахождения максимального элемента достаточно знак «>» поменять на знак « » заменить на «