8.2 Сортировка одномерного массива
Сортировкой называют набор операций, упорядочивающий элементы массива в соответствии с заданным отношением порядка. Например, в упорядоченном массиве A по возрастанию выполняются неравенства вида:
Вопрос о возрастании или убывании упорядоченного массива для нас не принципиален. Как правило, программы, сортирующие массив по возрастанию, легко изменяются для сортировки по убыванию.
Существует множество алгоритмов сортировки (пузырьковая сортировка, сортировка по дереву, быстрая сортировка, сортировка слиянием, сортировка Шелла и т. д.), они имеют большую практическую значимость, являются фундаментальными в некоторых областях информатики.
Здесь приводится самый распространенный и очень понятный алгоритм пузырьковой сортировки по возрастанию.
Название «Пузырьковая сортировка» происходит от образной интерпретации, по которой алгоритм заставляет «легкие» элементы мало-помалу всплывать на «поверхность».
Суть алгоритма такова. Начиная с первого, сравниваются два соседних элемента массива A[i] и A[i+l], если A[i] > A[i+1], то элементы меняются местами. В первый раз мы проходим массив начиная с индекса 1, до индекса n — 1, во второй — с 1 до n — 2 и т. д. Любой массив будет отсортирован за n-1 проходов. Таким образом, порядок сложности данного алгоритма (максимальное количество операций проверок и перестановок элементов массива) пропорционален n 2 /2, хотя массив может быть отсортирован уже после первого прохода.
a: array [1.. n] of Real;
Writeln (‘ введите ‘, n, ‘ элементов массива: ‘ ) ;
for i := 1 to n do Read (A [i] ) ; Readln;
Writeln (‘ Массив до сортировки:’ ) ;
for i:= 1 to n do Write(А[i] : 6 : 2, ‘ ‘);
if A[i] > A[i + 1] then
Writeln (‘ Массив после сортировки:’ ) ;
for i:= 1 to n do Write (A [i] : 6 : 2, ‘ ‘) ;
8.3 Массивы с большей размерностью
Возможна следующая организация массива: каждый элемент массива является другой массив. Описание массива в этом случае может выглядеть так:
. : array [. ] of array .
Подобная запись достаточно громоздка (несколько раз записывается служебное слово array и т. д. ), но синтаксис языка Паскаля позволяет описывать многомерные массивы проще.
<список идентификаторов через запятую> :
Array [ <список диапазонов, через запятую> ] of
М: array[1.. 3] of array [1.. 3] of Real;
Подобное описание эквивалентно следующему:
М: array [1.. 3, 1.. 3] of Real;
В первом случае доступ к элементу осуществляется так:
Т: array[1 .. 2, 1 .. 3, 1 .. 4] of Integer;
U: array[1 .. 10, ‘A’ .. ‘Z’] of char;
Работа с n-мерными массивами заставляет программиста организовать n вложенных циклов. Подробнее остановимся на двумерных массивах. Двумерные массивы используются, в основном, для определения матриц (таблиц) с индексами, изменяющимися по строкам и по столбцам (первый индекс – номер строки, второй — номер столбца).
А[1, 1] , А[1, 2] , . . . , A[l, M]
А[2, 1] , А[2, 2] , . . . , А[2, M]
А[N, 1] , A[N,2] , . . . , А[N,M]
Здесь приведён пример двух мерного массива с N строками и M столбцами.
С элементами двумерных массивов можно работать, указывая два индекса (номер строки и номер столбца) через запятую в квадратных скобках.
M[k, i] := SQR(M[i, j] + M[j, i] ) ;
Ввод элементов двумерного массива по строкам с клавиатуры:
for i := 1 to n do
for j:= 1 to m do Read (M[i, j]);
или с сообщениями:
for i:= 1 to n do
for j:= l to m do
Write(‘введите М[‘, i, ‘, ‘ , j, ‘] ‘);
Вывод элементов двумерного массива в виде матрицы:
Часто при работе с двумерными массивами (матрицами) приходится оперировать с элементами, обладающими некоторыми признаками, в частности, связанными с положением элементов относительно диагоналей матрицы. Например, элемент находится на главной диагонали рисунок 8.1a, на побочной диагонали рисунок 8.1б, ниже главной диагонали, ниже побочной и т. д. (рисунки 8.1в÷ж).
Положение этих элементов может быть описано следующими математическими соотношениями для матрицы n∙n:
— выше главной и выше побочной диагонали –
Задача. Матрица n*n вводится с клавиатуры, заменить все отрицательные элементы выше главной диагонали их квадратами. Вывести новую матрицу на экран.
Как упорядочить массив по возрастанию паскаль
Массив называется отсортированным по возрастанию, если для любых его элементов выполняется
условие a[i]<a[i+1]. Массив называется отсортированным по убыванию, если для любых его элементов выполняется условие a[i]>a[i+1].
Существует множество методов сортировки. Одни из них являются более эффективными, другие
проще для понимания. Достаточно простой для понимания является сортировка методом пузырька, который
также называют методом простого обмена. В чем же он заключается, и почему у него такое странное
название: «метод пузырька»?
Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В
сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно
«всплывают» в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).
Алгоритм и особенности сортировки:
Лекция 22 . Одномерные массивы. Сортировка одномерного массива.
автор: Садовский Ефим Моисеевич
1. Повторение.
Одномерные массивы. Описание. Ввод и вывод. Поиск максимального и минимального элемента массива.
2. Одномерный массив. Сортировка одномерного массива.
Отсортировать одномерный массив – это упорядочить его элементы по возрастанию или убыванию.
Сортировать массив можно различными способами. Давайте рассмотрим один из них, наверное, наиболее простой для понимания.
Например, надо отсортировать целочисленный массив по убыванию.
Пусть исходный массив, например: 5, 3, 1, 7, 9 , 4, 5, 8, 7, 5
Сначала найдем максимальный элемент и его порядковый номер.
Максимальный элемент – 9 (на 5 месте).
Ставим его на первое место, но, чтобы не потерять первый элемент, переставляем его на место максимального. То есть меняем максимальный с первым местами.
Получим массив: 9, 3, 1, 7, 5, 4, 5, 8 , 7, 5
Определяем максимальный элементов из элементов от второго до последнего. Этот максимальный меняем местами со вторым элементом массива.
Получим: 9, 8, 1, 7 , 5, 4, 5, 3, 7, 5
Ищем максимальный из оставшихся, меняем его местами с третьим и т.д.
Выполнив N-1 замену (так как при N-1-й замене последний элемент станет на свое место автоматически, то есть массив будет отсортирован.)
Для сортировки массива сначала оформим задачу поиска максимального элемента массива и перестановки его с первым элементом.
Такие действия надо выполнить, как мы говорили раньше, N-1 раз.
Добавляем внешний цикл For (по переменной t).
Вспоминаем, что на первом шаге цикла мы сначала за максимальный берем первый элемент, на втором – второй, на третьем – третий и т. д. Аналогично на первом шаге мы максимальный меняем местами с первым, на втором – со вторым и т.д.
Поэтому просто заменяем цифру 1 на переменную t , а число 2 в строке For на t+1 .
Получим:
Программа сортировки готова.
Для сортировки массива по возрастанию достаточно поменять в условии знак > на знак <.
3. Задачи.
1. Заполнить одномерный массив из 20 элементов случайными числами от 1 до 50. Отсортировать массив по возрастанию.
2. Одномерный массив заполнен целыми числами. Отсортируйте его по убыванию. Затем выведите на экран максимальный и минимальный элементы.
3. Заполнить одномерный массив из n элементов случайными числами от 1 до 30. Отсортировать массив по возрастанию. Вывести на экран число, расположенное в середине, если количество элементов нечетное или фразу «Числа в центре нет», если четное.
Сортировка массива методом "пузырька"
Сейчас мы поговорим о сортировки массива так называемым методом "пузырька". По другому этот метод называется методом перестановок или методом обмена. Почему метод известен как метод "пузырька", да просто потому, что при его реализации более "легкие" элементы как бы всплывают вверх. Соответственно, более тяжелые "идут ко дну", один человек, обладающий видимо хорошим чувством юмора, заметил, что по всей видимости, пессимисты называют метод пузырька методом "утопленника".
Итак, представим, что у нас есть целочисленный массив из 10 элементов и нам его необходимо отсортировать по возрастанию.
Вот код программы на Паскале:
Пояснения. Как видно из текста программы на Паскале, при сортировке массива методом пузырька, сравниваются два соседних элемента массива. В том случае, если элемент массива с номером i оказывается больше элемента массива с номером i+1 , происходит обмен значениями при помощи вспомогательной переменной buf (переменной я дал название со смысловой нагрузкой, от слова "буфер").
Возможные ошибки. Как показывают мои личные наблюдения, начинающие программисты постоянно наступают на одни и те же грабли. Вместо строки "for j:=i+1 to n do" они зачастую пишут "for j:=2 to n do", что хоть и приводит к обмену значениями некоторых переменных, но не дает необходимого результата.