Информатика, 10 класс К. Ю. Поляков, Е. А. Еремин
 Скачать 0.95 Mb.
|
|
§ 64. Сортировка Введение Сортировка – это расстановка элементов массива в заданном порядке. Порядок сортировки может быть любым для чисел обычно рассматривают сортировку по возрастанию (или убыванию) значений. Возникает естественный вопрос зачем сортировать данные. На него легко ответить, вспомнив, например, работу со словарями сортировка слов по алфавиту облегчает поиск нужной информации. Программисты изобрели множество способов сортировки. В целом их можно разделить на две группы 1) простые, но медленно работающие (на больших массивах) и 2) сложные, но быстрые. Мы изучим два классических метода из первой группы и один метод из второй – знаменитую быструю сортировку, предложенную Ч. Хоаром. Далее мы будем, как принято в учебниках, рассматривать алгоритмы сортировки элементов массива по возрастанию (или убыванию) значений. Для массивов, в которых есть одинаковые элементы, используются понятия сортировка по неубыванию» и сортировка по невозрас- танию». Метод пузырька (сортировка обменами) Название этого метода произошло от известного физического явления – пузырёк воздуха вводе поднимается вверх. Если говорить о сортировке массива, сначала поднимается наверх (к началу массива) самый «лёгкий» (минимальный) элемент, затем следующий и т.д. Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно меньший элемент ниже, то меняем их местами. Далее также рассматриваем следующую пару элементов и т.д. (см. рисунок. Задачи и задания Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 42 Когда мы обработали пару ( A[0], A[1]), минимальный элемент стоит на месте A[0]. Это значит, что наследующих этапах его можно не рассматривать. Первый цикл, устанавливающий на свое место первый (минимальный) элемент, можно на псевдокоде записать так для j от N- 2 до 0 шаг -1 если A[j+ 1 ]< A[j] то поменять местами A[j] и A[j+ 1 ] Здесь j – целочисленная переменная. Обратите внимание, что на очередном шаге сравниваются элементы A[j] и A[j+1], поэтому цикл начинается с j=N-2. Если начать стона первом же шаге получаем выход заграницы массива – обращение к элементу A[N]. За один проход такой цикл ставит на место один элемент. Чтобы подтянуть второй элемент, нужно написать еще один почти такой же цикл, который будет отличаться только конечным значением j в заголовке цикла. Так как верхний элемент уже стоит на месте, его ненужно трогать сделать для j от N- 2 до 1 шаг -1 если A[j+ 1 ]< A[j] то поменять местами A[j] и A[j+ 1 ] При установке го элемента конечное значение для j будет равно 2 и т.д. Таких циклов нужно сделать N-1 – на 1 меньше, чем количество элементов массива. Почему не N? Дело в том, что если N-1 элементов поставлены на свои места, то оставшийся автоматически встает на своё место – другого места для него нет. Поэтому полный алгоритм сортировки представляет собой такой вложенный цикл for ( i = 0 ; i < N- 1 ; i++ ) for ( j = N- 2 ; j >= i; j-- ) if ( A[j] > A[j+ 1 ] ) { // поменять местами A[j] и A[j+1] } Записать полную программу вы можете самостоятельно. Метод выбора Еще один популярный простой метод сортировки – метод выбора, при котором на каждом этапе выбирается минимальный элемент (из оставшихся) и ставится на свое место. Алгоритм в общем виде можно записать так для i от 1 до N- 1 найти номер nMin минимального элемента из A[i]..A[N] если i != nMin то поменять местами A[i] и A[nMin] Здесь перестановка происходит только тогда, когда найденный минимальный элемент стоит не на своём месте, то есть i != nMin. Поскольку поиск минимального элемента выполняется в цикле, этот алгоритм сортировки также представляет собой вложенный цикл for ( i = 0 ; i < N- 1 ; i++ ) { nMin = i; for ( j = i+ 1 ; j < N; j++ ) if ( A[j] < A[nMin] ) nMin = j; if ( i != nMin ) { // поменять местами A[i] и A[nMin] } } 4 5 2 1 3 4 5 2 1 3 4 5 1 2 3 4 1 5 2 3 1 4 5 2 3 Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 43 Быстрая сортировка Методы сортировки, описанные в предыдущем параграфе, работают медленно для больших массивов данных (более 1000 элементов. Поэтому в середине XX века математики и программисты серьезно занимались разработкой более эффективных алгоритмов сортировки. Один из самых популярных быстрых алгоритмов, разработанный в 1960 году английским учёным Ч. Хоаром, таки называется – быстрая сортировка (англ. quicksort). Будем исходить из того, что сначала лучше делать перестановки элементов массива на большом расстоянии. Предположим, что у насесть элементов и известно, что они уже отсортированы в обратном порядке. Тогда за N/2 обменов можно отсортировать их как нужно – сначала поменять местами первый и последний, а затем последовательно двигаться с двух сторон к центру. Хотя это справедливо только тогда, когда порядок элементов обратный, подобная идея положена в основу алгоритма Quicksort. Пусть дан массив A из N элементов. Выберем сначала наугад любой элемент массива (назовем его X). На первом этапе мы расставим элементы так, что слева от некоторой границы впервой группе) находятся все числа, меньшие или равные X, а справа (во второй группе) – большие или равные X. Заметим, что элементы, равные X, могут находиться в обеих частях. Теперь элементы расположены так, что ни один элемент из первой группы при сортировке не окажется во второй и наоборот. Поэтому далее достаточно отсортировать отдельно каждую часть массива. Такой подход называют разделяй и властвуй (англ. divide and conquer). Лучше всего выбирать X так, чтобы в обеих частях было равное количество элементов. Такое значение X называется медианой массива. Однако для того, чтобы найти медиану, надо сначала отсортировать массив, то есть заранее решить ту самую задачу, которую мы собираемся решить этим способом. Поэтому обычно в качестве X выбирают средний элемент массива или элемент со случайным номером. Сначала будем просматривать массив слева до тех пор, пока не обнаружим элемент, который больше X (и, следовательно, должен стоять справа от X). Затем просматриваем массив справа до тех пор, пока не обнаружим элемент меньше X (он должен стоять слева от X). Теперь поменяем местами эти два элемента и продолжим просмотр до тех пор, пока два просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на 2 части левую со значениями меньшими или равными X, и правую со значениями большими или равными X. На этом первый этап (разделение) закончен. Затем такая же процедура применяется к обеим частям массива до тех пор, пока в каждой части не останется один элемент (и таким образом, массив будет отсортирован. Чтобы понять сущность метода, рассмотрим пример. Пусть задан массив Выберем в качестве X средний элемент массива, равный 67. Найдем первый слева элемент массива, который больше или равен X и должен стоять во второй части. Это число 78. Обозначим индекс этого элемента через L. Теперь находим самый правый элемент, который меньше X идол- жен стоять впервой части. Это число 34. Обозначим его индекс через R. Теперь поменяем местами два этих элемента. Сдвигая переменную L вправо, а R – влево, находим следующую пару, которую надо переставить. Это числа 82 и 44. 11 Хотя есть и другие, тоже достаточно непростые алгоритмы. R L 78 6 82 67 55 44 34 X 78 6 82 67 55 44 34 A[i]≤ X A[i]≥ X Ч.Э. Хоар (р. 1934) (en.wikipedia.org) Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 44 Следующая пара элементов для перестановки – числа 67 и 55. После этой перестановки дальнейший поиск приводит к тому, что переменная L становится больше, то есть массив разбит на две части. В результате все элементы массива, расположенные левее, меньше или равны X, а все правее A[R] – больше или равны X. Таким образом, сортировка исходного массива свелась к двум сортировкам частей массива, то есть к двум задачам того же типа, но меньшего размера. Теперь нужно применить тот же алгоритм к двум полученным частям массива первая часть – с ого до ого элемента, вторая часть – с ого до последнего элемента. Как вызнаете, такой прием называется рекурсией. Сначала предположим, что в нашей программе один глобальный массив A индексами от 0 до N-1, который нужно сортировать. Это значит, что массив доступен всем процедурами функциям, в том числе и нашей процедуре сортировки. Глобальные данные объявляются выше основной программы const int N = 7 ; int A[N]; Тогда процедура сортировки принимает только два параметра, ограничивающие её рабочую зону номер первого элемента, и nEnd – номер последнего элемента. Если nStart = nEnd, тов рабочей зоне один элемент и сортировка не требуется, то есть нужно выйти из процедуры. В этом случае рекурсивные вызовы заканчиваются. Приведем полностью процедуру быстрой сортировки void qSort( int nStart, int nEnd ) { int L, R, c, X; if ( nStart >= nEnd ) return ; // массив отсортирован L = nStart; R = nEnd; X = A[(L+R)/ 2 ]; while ( L <= R ) { // разделение A[L] < X ) L ++; while ( A[R] > X ) R --; if ( L <= R ) { c = A[L]; A[L] = A[R]; A[R] = c; L ++; R --; } } qSort ( nStart, R ); // рекурсивные вызовы qSort ( L, nEnd ); } Для того, чтобы отсортировать весь массив, нужно вызвать эту процедуру так qSort( 0 , N- 1 ); К сожалению, эта процедура сортирует только глобальный массив A, чтобы использовать её для сортировки других массивов, добавим в заголовок еще один параметр – целочисленный массив L R L 34 6 44 67 55 82 78 R L 34 6 82 67 55 44 78 Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 45 Размер массива указывать необязательно, такая процедура будет работать с массивами любого размера. Изменятся также и рекурсивные вызовы (на первом месте в списке аргументов нужно указать имя массива void qSort( int A[], int nStart, int nEnd ) { ... qSort ( A, nStart, R ); // рекурсивные вызовы qSort ( A, L, nEnd ); } а также вызов процедуры из основной программы qSort ( A, 0 , N- 1 ); Скорость работы быстрой сортировки зависит оттого, насколько удачно выбирается вспомогательный элемент X. Самый лучший случай – когда на каждом этапе массив делится на две равные части. Худший случай – когда водной части оказывается только один элемента в другой – все остальные. При этом глубина рекурсии достигает N, что может привести к переполнению стека нехватке стековой памяти. Для того, чтобы уменьшить вероятность худшего случая, в алгоритм вводят случайность в качестве X на каждом шаге выбирают не середину рабочей части массива, а элемент со случайным номером X = A[irand(L,R)]; Здесь используется написанная нами ранее (см. § 62) функция irand, которая возвращает случайное целое число на отрезке [L,R]. В таблице сравнивается время сортировки (в секундах) массивов разного размера, заполненных случайными значениями, с использованием трёх изученных алгоритмов. Как показывают эти данные, преимущество быстрой сортировки становится подавляющим при увеличении N. 1. Что такое сортировка 2. На какой идее основан метод пузырька метод выбора 3. Объясните, зачем нужен вложенный цикл в описанных методах сортировки. 4. Сравните метод пузырька и метод выбора. Какой из них требует меньше перестановок 5. Расскажите про основные идеи метода быстрой сортировки. 6. Как выдумаете, можно ли использовать метод быстрой сортировки для нечисловых данных, например, для символьных строк 7. Отчего зависит скорость быстрой сортировки Какой самый лучший и самый худший случай. Как выдумаете, может ли метод быстрой сортировки работать дольше, чем метод выбора (или другой простой метод Если да, то при каких условиях 9. Как нужно изменить приведенные алгоритмы, чтобы элементы массива были отсортированы по убыванию 1. Отсортировать массив и найти количество различных чисел в нм. 2. Напишите программу, в которой сортировка выполняется методом камня – самый тяж- лый» элемент опускается вконец массива. N метод пузырька метод выбора быстрая сортировка 1000 0,24 с 0,12 с 0,004 с 5000 5,3 с 2,9 с 0,024 с 15000 45 с 34 с 0,068 с Задачи и задания ? Контрольные вопросы Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 46 22.10.2015 3. Напишите программу, которая выполняет неполную сортировку массива ставит в начало массива три самых меньших по величине элемента в порядке возрастания (неубывания). Положение остальных элементов неважно. Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. 5. Напишите программу, которая сортирует массив по возрастанию последней цифры числа. 6. Напишите программу, которая сортирует массив по убыванию суммы цифр числа. 7. Напишите программу, которая сортирует первую половину массива по возрастанию, авто- рую – по убыванию (элементы из первой половины не должны попадать во вторую и наоборот. Напишите программу, которая сортирует массива затем находит максимальное из чисел, встречающихся в массиве несколько раз. 9. Напишите программу, которая сравнивает количество перестановок при сортировке одного итого же массива разными методами. Проведите эксперименты для возрастающей последовательности (уже отсортированной, убывающей (отсортированной в обратном порядке) и случайной. § 65. Двоичный поиск Ранее мы уже рассматривали задачу поиска элемента в массиве и привели алгоритм, который сводится к просмотру всех элементов массива. Такой поиск называют линейным. Для массива из 1000 элементов нужно сделать 1000 сравнений, чтобы убедиться, что заданного элемента в массиве нет. Если число элементов (например, записей в базе данных) очень велико, время поиска может оказаться недопустимым, потому что пользователь не дождется ответа. Как вы помните, основная задача сортировки – облегчить последующий поиск данных. Вспомним, как мы ищем нужное слово (например, слово «гравицапа») в словаре. Сначала открываем словарь примерно в середине и смотрим, какие там слова. Если они начинаются на букву Л, то слово «гравицапа» явно находится на предыдущих страницах, и вторую часть словаря можно не смотреть. Теперь также проверяем страницу в середине первой половины, и т.д. Такой поиск называется двоичным. Понятно, что он возможен только тогда, когда данные предварительно отсортированы. Для примера на рисунке показан поиск числа X = 44 в отсортированном массиве Серым фоном выделены ячейки, которые уже не рассматриваются, потому что в них не может быть заданного числа. Переменные L и R ограничивают рабочую зону массива L содержит номер первого элемента, а R – номер элемента, следующего за последним. Таким образом, нужный элемент (если он есть) находится в части массива, которая начинается с элемента A[L] и заканчивается элементом A[R-1]. На каждом шаге вычисляется номер среднего элемента рабочей зоны, он записывается в переменную c. Если X < A[c], то этот элемент может находиться только левее A[c], и правая 6 34 44 55 67 78 82 L R 6 34 44 55 67 78 82 L R 6 34 44 55 67 78 82 L R с с с 6 34 44 55 67 78 82 R L A[0] A[N] |