Урок №18. Сортировка массива.
Под сортировкой (упорядочением) массива понимают перераспределение его элементов в некотором определённом порядке.
Порядок, при котором в массиве первый элемент имеет самое маленькое значение, а значение каждого следующего элемента не меньше значения предыдущего элемента, называют неубывающим.
Порядок, при котором в массиве первый элемент имеет самое большое значение, а значение каждого следующего элемента не больше значения предыдущего элемента, называют невозрастающим.
Цель сортировки — облегчить последующий поиск элементов: искать нужный элемент в упорядоченном массиве легче.
Разработано множество алгоритмов сортировки. Рассмотрим один из них — сортировку выбором.
Сортировка выбором (например, по невозрастанию) осуществляется следующим образом:
- в массиве выбирается максимальный элемент;
- максимальный и первый элементы меняются местами, после чего первый элемент считается отсортированным;
- в неотсортированной части массива снова выбирается максимальный элемент; он и первый неотсортированный элемент массива меняются местами;
- действия, описанные в п. 3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет минимальным).
Рассмотрим процесс сортировки выбором на примере массива
В этом массиве из 8 элементов операцию выбора максимального элемента мы проводили 7 раз. В массиве из К элементов такая операция будет проводиться N — 1 раз. Объясните почему.
Приведём фрагмент программы, реализующий описанный алгоритм:
for i in range(N-1):
imax = i
for j in range(i+1,N):
if A[j] > A[imax]:
imax= j
A[i], A[imax] = A[imax], A[i]
Здесь мы использовали один цикл внутри другого. Такая конструкция называется вложенным циклом.
Запишите полный текст программы и выполните её на компьютере для рассмотренного в примере массива А.
Разработайте подпрограмму max для поиска максимального из двух элементов массива. Модифицируйте программу сортировки выбором, использовав в ней эту подпрограмму.