Лекция 16. Математические методы (сортировки) (1152918)
Текст из файла
1Воробьева И.А. «Информатика. Язык Питон»Основные математические методы,используемые при решении числовых задач (продолжение)Методысортировки:выбора,слиянием(внутренняя и внешняя).методпузырька,сортировка11. МАТЕМАТИЧЕСКИЕ МЕТОДЫ ПОИСКА И СОРТИРОВКИ11.3.2. Обменная сортировка (метод «пузырька»)Простая обменная сортировка (в просторечии называемая"методом пузырька") для массиваработаетследующим образом. Начиная с конца массива, сравниваются двасоседних элементаи. Если выполняется условие, то значения элементов меняются местами.
Процесс продолжаетсядляии т.д., пока не будет произведено сравнениеи. Понятно, что после этого на местеокажется элемент массивас наименьшим значением. На втором шаге процесс повторяется, нопоследними сравниваются элементыи. И так далее. Напоследнем шаге будут сравниваться только текущие значенияи. Понятна аналогия с пузырьком, поскольку наименьшиеэлементы (самые "легкие") постепенно "всплывают" к верхней границемассива.Таким образом, мы получим массив, упорядоченный повозрастанию (неубыванию), когда MIN элемент расположен в началемассива, а MAX в конце массива. При этом MIN элемент встает на своеместо первым, сначала сортируется «голова массива».Точно такого же конечного результата – упорядоченный повозрастанию (неубыванию) массив – можно добиться, двигаясь в другомнаправлении: начинать просмотр с начала массива и «топить»наибольшие элементы (самые «тяжелые») в сторону конца массива.
Приэтом MAX элемент встает на свое место первым, сначала сортируется«хвост массива».2Воробьева И.А. «Информатика. Язык Питон»Получается, что в данном виде сортировки, во-первых, есть понятие«направления сортировки», а во-вторых, за один шаг сортировки одинэлемент встает на свое место в отсортированном массиве. Оба этисвойства вместе полезны, особенно для больших массивов данных или,если сортировка используется как часть другого процесса, так как всегдаможно сказать на каждом шаге сортировки, какая часть массива ужеотсортирована. Например, можно начать какой-либо параллельныйпроцесс на уже отсортированной части массива не дожидаясь окончанияпроцесса собственно сортировки.Приведем оба варианта алгоритмов, которые приводят к одномурезультату, но для разных направлений сортировки.Алгоритм сортировки пузырьком на псевдокоде.Направление сортировки: MIN в начало массива первойсортируется «голова» массива.– массив длины .– шаг сортировки.BUBBLE_SORT_UP( X )FOR S=1 TO (n – 1): #за один шаг S один элемент встанет на свое местоFOR i = n DOWNTO (S + 1) : # просмотр от «хвоста» к «голове»IF X[i] < X[i-1] THEN:X[i]X[i – 1] # обмен элементов – пузырек всплывает влевоНаправление сортировки: MAX в конец массива первымсортируется «хвост» массива.– массив длины .– шаг сортировки.3Воробьева И.А.
«Информатика. Язык Питон»BUBBLE_SORT_DOWN( X )FOR S=1 TO (n – 1): #за один шаг S один элемент встанет на свое местоFOR i = S + 1 TO n : # просмотр от «головы» к «хвосту»IF X[i] < X[i-1] THEN:X[i]X[i – 1] # обмен элементов – пузырек всплывает влевоЧисло шагов алгоритма (сравнений и обменов) –.–Сложность алгоритма –.Достоинства: сортировка «на месте»; за один шаг алгоритма один элемент встает на свое место, причемлегко определить уже «отсортированную часть» массива; допускается простое улучшение по количеству шагов алгоритма.Недостатки: в «худшем случае», сложность алгоритма не улучшаетсядаже модификацией.Обратите внимание, что единственное отличие этих вариантовзаключается в диапазонах внутреннего параметрического цикла: одинначинает работу от «хвоста» массива к «голове» с шагом «-1», а другой –от «головы» к «хвосту» с шагом «1».Пример сортировки методом пузырька показан в таблице ниже.Пример 11.4.
Сортировка методом пузырька. Направление: MIN в началомассива.(серым цветом выделено состояние массива перед началом работывнутреннего цикла FOR) 8 23 5 65 44 33 1 6Начальное состояние массива8 23 5 65 44 33 1 6Шаг 18888823232323235555165 44 33 165 44 1 3365 1 44 331 65 44 335 65 44 33666664Воробьева И.А.
«Информатика. Язык Питон»8 1 23 5 65 44 33 61 8 23 5 65 44 33 61 8 23 5 65 44 33 6Шаг 211111188888523 523 523 523 55 238 2365 44 665 6 446 65 446 65 446 65 446 65 443333333333331 5 8 23 6 65 44 33Шаг 311111555558888623 623 623 66 238 236533333333336565656544444444441 5 6 8 23 33 65 44Шаг 4 (фактически, начинаяс этого шага, алгоритмработает вхолостую)1111555566668888232323233333333344444444656565651 5 6 8 23 33 44 65Шаг 51 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 65Шаг 6Шаг 71 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 65Метод пузырька допускает простое усовершенствование. Какпоказывает пример в таблице, на четырех последних шагах расположение5Воробьева И.А.
«Информатика. Язык Питон»значений элементов не менялось (массив оказался уже упорядоченным).Поэтому, если на некотором шаге не было произведено ни одногообмена, то выполнение алгоритма можно прекращать. Это можнореализовать с помощью уже известного вам «метода флажка» ициклов while.11.3.3. Сортировка выборомПри сортировке массиваметодом простоговыбора среди всех элементов находится элемент с наименьшимзначением, после чего первый элементи найденный экстремумобмениваются значениями. Затем этот процесс повторяется дляполучаемых подмассивов, затемит.д.
до тех пор, пока мы не дойдем до подмассива. Таким образом,мы на уменьшающихся частях массива ищем экстремум (MIN) и ставимего «на свое место» в отсортированном массиве.Разумеется, если требуется отсортировать массив в обратномпорядке (по убыванию), мы просто будем искать не MIN, а MAX.Алгоритм сортировки выбором на псевдокоде.– массив длины .– шаг сортировки.SELECTION_SORT( X )FOR s=1 TO (n – 1) :j MIN_SEARCH(s, n, X) # алгоритм поиска минимума# в массиве X[s .. n]# от индекса s до индексаIF j ≠ s THEN : # исключаем лишнее: обмен элементов только, если# МИН_элемент еще не стоит на своем местеX[s]X[j]Сложность алгоритма –6Воробьева И.А.
«Информатика. Язык Питон»Достоинства: сортировка «на месте»; за один шаг алгоритма один элемент встает на свое место, причемлегко определить уже «отсортированную часть» массива;Работа алгоритма иллюстрируется примером в таблице ниже.Пример 11.5. Сортировка простым выбором.(серым цветом выделено состояние массива перед началом поискаМИНИМУМА на очередном цикле)Начальное состояние 8 23 5 65 44 33 1 6массиваШаг 1Шаг 2Шаг 3Шаг 4Шаг 5Шаг 6Шаг 78 23 5 65 44 33 1 61 23 5 65 44 33 8 61| 23 5 65 44 33 8 61 5 23 65 44 33 8 61 5| 23 65 44 33 8 61 5 6 65 44 33 8 231 5 6| 65 44 33 8 231 5 6 8 44 33 65 231 5 6 8| 44 33 65 231 5 6 8 23 33 65 441 5 6 8 23| 33 65 441 5 6 8 23 33 65 441 5 6 8 23 33| 65 441 5 6 8 23 33 44 65 числочислосравнений обменов716151413120117Воробьева И.А.
«Информатика. Язык Питон»Число шагов алгоритма в худшем случае (сравнений и обменов) –.–Сложность алгоритма –.11.3.4. Метод сортировки со слияниемСортировки разделяют на внутренние – это сортировки, которыеполностью производят над массивами данных в ОП и внешние – этосортировки над большими массивами данных, которые не помещаютсяцеликом в ОП. Такие данные записаны в файл на жестких носителях исортировки производят либо полностью только в файлах, либокомбинируя работу в файлах с методами внутренних сортировок начастях файла. Сортировки со слиянием, как правило, применяются вовнешних сортировках, однако существуют и эффективные методывнутренней сортировки, основанные на разбиениях и слияниях.Сначала поясним, что такое слияние.
Пусть имеются два ужеотсортированных в порядке возрастания массиваии имеется пустой массивкоторыймы хотим заполнить значениями массивов и в порядке возрастания.Для слияния выполняются следующие действия: сравниваютсязначенияи; меньшее из значений записывается в.Предположим, что это было значение. Тогда на следующем шагесравнивается параи; меньшее из значений заносится в.Предположим, что это оказалось значение. На следующем шагесравниваются значенияии т.д., пока один из массивовполностью не исчерпается. Тогда остаток другого массива простодописывается в «хвост» массива .
Пример слияния двух массивовпоказан на рисунке 11.1.ВАЖНО: Слияние применяется к упорядоченным массивам. Т.е. делаетиз двух упорядоченных массивов один вновь упорядоченный массив.8Воробьева И.А. «Информатика. Язык Питон»Рис. 11.1. Пример слияния двух массивов.9Воробьева И.А. «Информатика. Язык Питон»Для сортировки со слиянием массивазаводитсяпарный массив. Обратите внимание, что теперь мыговорим уже о неупорядоченном массиве. Удвоение памяти нам попрежнему понадобится, а вот тот факт, что изначально массивнеупорядочен, но слияние допустимо, обеспечивается в методеспециальным выбором индексов. Для простоты изложения методасчитаем, что является степенью числа 2.На первом шаге производится слияниерезультата вслияниеирезультата в, ..., слияниеирезультата в.ис размещениемс размещениемс помещениемНа втором шаге производится слияние парис помещением результата в, слияние парис помещением результата вслияние парс помещениемрезультата в.
И т.д.На последнем шаге производится слияние последовательностейэлементов массива (будет это очередь массива A или B зависит от )длиной, например:ис помещением результата в.Для случая массива, используемого ранее в примерах различныхсортировок, последовательность шагов показана в таблице ниже.Пример 11.6. Пример сортировки со слиянием в массивах.Начальное состояние массиваМАССИВ_AМАССИВ _BМАССИВ _AМАССИВ _B8 23 5 65 44 33 1 66 8 | 1 23 | 5 33 | 44 656 8 44 65 | 1 5 23 331 5 6 8 23 33 44 6510Воробьева И.А.
«Информатика. Язык Питон».Достоинства: метод пригоден для внешней сортировки «по частям» так как всегдаработает с «кусками» отсортированных элементов; быстрый – сложность алгоритма составляет, что такжеважно при работе с файлами без использования ОП.Недостатки: для выполнения алгоритма для сортировки массива размера nтребуется 2*n элементов памяти; элементы выставляются на «свои отсортированные места» только напоследнем шаге алгоритма.11.3.5. Методы внешней сортировкиНапомним, что внешней сортировкой называют сортировкупоследовательных файлов, располагающихся во внешней памяти ислишком больших, чтобы можно было целиком переместить их восновную память и применить один из рассмотренных в предыдущемразделе методов внутренней сортировки. Наиболее часто внешняясортировка применяется в системах управления базами данных привыполнении запросов, и от эффективности применяемых методовсущественно зависит производительность СУБД.Следует пояснить, почему речь идет именно о последовательныхфайлах, т.е.
о файлах, которые можно читать «запись» за «записью» впоследовательном режиме, а писать можно только после последнейзаписи. Все дело в том, что практически все используемые в настоящеевремя дисковые устройства снабжены подвижными магнитнымиголовками. При выполнении обмена с дисковым накопителемвыполняется подвод головок к нужному цилиндру, выбор нужной головки(дорожки), прокрутка дискового пакета до начала требуемого блока и,наконец, чтение или запись блока. Среди всех этих действий самоебольшое время занимает подвод головок. Именно это время определяет11Воробьева И.А.
«Информатика. Язык Питон»общее время выполнения операции. Единственным доступным приемомоптимизации доступа к магнитным дискам является как можно более"близкое" расположение на накопителе последовательно адресуемыхблоков файла. Но и в этом случае движение головок будетминимизировано только в том случае, когда файл читается или пишется вчисто последовательном режиме. Именно с такими файлами припотребности сортировки работают современные СУБД [см.
1].Прямое слияниеНачнем с того, как можно использовать в качестве метода внешнейсортировки алгоритм простого слияния. Предположим, что имеетсяпоследовательный файл , состоящий из записей(снова дляпростоты предположим, что является степенью числа 2). Будем считать,что каждая запись состоит ровно из одного элемента. Для сортировкииспользуются два вспомогательных файла и (размер каждого из нихбудет).Сортировка состоит из последовательности шагов, в каждом изкоторых выполняется распределение записей файла A в файлы B и C, азатем слияние файлов B и C в файл A (заметим, что процедура слияниядля файлов полностью иллюстрируется рисунком 11.1.). Распределениепроисходит немного иначе, чем выбор индексов, описанный длявнутренней сортировки (ведь там, имея дело с произвольным доступом клюбому элементу массива, можем себе это позволить), но смыслраспределения записей тот же: сначала поэлементный выбор, затемпопарный, затем выбирают четверки и т.д., отсюда и выбор -- степеньчисла 2.На первом шаге для распределения последовательно читается файлA, и записипишутся в файл B, а записив файл C (начальное распределение).Начальноеслияниепроизводитсянадпарами, и результат записывается в файл A.На втором шаге снова последовательно читается файл A, и в файл Bзаписываются последовательные пары с нечетными номерами, а в файл C- с четными.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
