Как отсортировать массив
В задачах ЕГЭ по информатике часто возникает потребность отсортировать массив, то есть переставить его элементы так, чтобы они расположились по возрастанию (или по убыванию).
Самый простой способ (на Питоне)
Если нужно упорядочить массив a, то самый простой способ сделать это - метод sort:
a.sort()
После этого массив a будет отсортирован по возрастанию.
Можно сортировать и по убыванию:
a.sort(reverse=True)
Метод работает очень быстро: массив из миллиоа элементов упорядочивается за доли секунды.
Всё дальнейшее - скорее для общего развития либо для случая, если вы используете какой-то другой язык программирования.
Некоторые другие способы сортировки.
Если массив сравнительно небольшой (скажем, 10 тысяч элементов), то эта задача решается буквально в пять строк на Питоне (a - массив, который надо отсортировать):
n=len(a)
for i in range(n-1):
for j in range(i+1,n):
if a[i] > a[j]:
a[i],a[j] = a[j],a[i]
Для массива из 10 тысяч элементов время сортировки составит несколько секунд.
Однако при возрастании размера массива время работы алгоритма увеличивается пропорционально квадрату этого размера. Поэтому массив в 100 тысяч элементов будет отсортирован где-то за десяток минут - это уже неприемлемо много.
Можно ли сортировать быстрее? Да, можно!
Сортируем быстро!
Есть по крайней мере два способа быстрой сортировки: быстрая сортировка Хоара (quicksort) и сортировка слиянием (mergesort).
Сортировка Хоара очень популярна, но, на мой взгляд, её алгоритм достаточно сложен, поэтому написать и отладить его на экзамене будет тяжеловато. Сортировка слиянием куда проще, и реализовать её существенно легче. По скорости же она сравнима с quicksort: массив из миллиона элементов сортируется за считанные секунды.
Основная идея сортировки слиянием - объединение двух отсортированных массивов в один. Процесс очень несложен. Пусть у нас есть два уже упорядоченных массива: a и b. Сравниваем их самые первые (т.е. минимальные) элементы. Если элемент массива a меньше, чем элемент массива b, то копируем его в выходной массив и продвигаемся по массиву a на один элемент. В противном случае проделываем то же самое с элементом массива b.
Когда один из массивов закончится, то переписываем в выходной массив оставшиеся элементы другого массива. Когда закончится и второй массив - то работа завершена.
Приведем код функции merge. Параметры a и b - упорядоченные массивы, которые надо слить в единый массив. Объединенный массив возвращается функцией как результат.
def merge(a,b):
r=[]
na = len(a)
nb = len(b)
ia=0
ib=0
while(True):
if ia < na and ib < nb :
if a[ia] < b[ib] :
r.append(a[ia])
ia += 1
else:
r.append(b[ib])
ib += 1
elif ia < na:
r.append(a[ia])
ia += 1
elif ib < nb:
r.append(b[ib])
ib += 1
else: break
return r
Собственно сортировка состоит в следующем: если наш массив пустой или состоит из одного элемента, то сортировать нечего. В противном случае разделяем массив на две половины, к каждой половине рекурсивно применяем процедуру сортировки и сливаем два подмассива в один массив. Это выглядит так:
def mergesort(a):
if len(a) <= 1: return a
else:
m = len(a)//2;
return merge( mergesort(a[0:m]), mergesort(a[m:]) )
Сортировка в три строки
В Питоне есть подключаемый модуль bisect. Функция insort, включенная в этот модуль, вставляет новый элемент в упорядоченный массив - в такое его место, что массив остается упорядоченным.
Это дает возможность получить из массива a отсортированный массив b следующим образом:
n = len(a)
b = []
for i in range(n): bisect.insort( b,a[i] )
Чтобы функция была доступна, следует в начале программы подключить модуль bisect с помощью команды
import bisect
Данный метод работает гораздо быстрее простой сортировки, описанной в начале этой статьи, но в разы медленнее, чем сортировка слиянием.
Метод можно применять в случаях, когда программа последовательно читает числа из файла, причем требуется получить отсортированный массив из этих чисел.
Практика показала, что для небольших массивов (длиной менее нескольких тысяч элементов) вполне пригоден простой метод сортировки. Если массив содержит порядка 100 тысяч элементов, то можно использовать функцию bisect.insort. Для массивов из миллионов элементов из описанных выше методов пригодна только сортировка слиянием (или сортировка quicksort, которая примерно вдвое быстрее).
(c) Ю.Д.Красильников, 2021 г.
Комментарии
Отправить комментарий