Изучение и программирование алгоритмов сортировки. Сортировка данных. Основные понятия. Метод обмена соседних элементов (метод "пузырька")

ЛАБОРАТОРНАЯ РАБОТА ПММ  9

ИЗУЧЕНИЕ И ПРОГРАММИРОВАНИЕ АЛГОРИТМОВ СОРТИРОВКИ

Цель работы: изучение  основных  алгоритмов  внутренней  сортировки данных и их программная реализация

Сортировка данных. Основные понятия

Многие задачи, связанные с обработкой и поиском информации, решаются эффективнее, если данные хранятся в памяти ЭВМ в  определенном порядке. Можно представить, насколько трудно было  бы  пользоваться  словарем или телефонным справочником, если бы записи в них не располагались по алфавиту. Точно так же от порядка, в котором хранятся элементы в памяти ЭВМ, во многом зависит скорость и простота алгоритмов, предназначенных для их обработки.

Хотя в словарях слово "сортировка" определяется как "распределение, отбор по сортам; деление  на  категории",  программисты  традиционно используют это слово в гораздо более узком смысле, обозначая им расстановку элементов в возрастающем или убывающем порядке. Можно  дать следующее определение: сортировкой называется упорядочение элементов  массива (записей файла) в соответствии с заданным условием следования.

По способу размещения данных  выделяют  сортировку  внутренюю  (все данные помещаются в ОП) и внешнюю (данные находятся на магнитном диске). По типу обрабатываемых данных различают: а) простую (скалярную) сортировку: элементы числового или строкового массива расставляются по убыванию или возрастанию их значений; б) сортировку по ключу: обрабатываются массивы  или  файлы  записей (таблицы). Каждая запись состоит из полей, содержащих информацию определенного типа. При сортировке одно из полей  рассматривается  как главное (ключ), и записи расставляются таким образом, чтобы это главное поле было упорядоченным. Например, если ключом является фамилия, то  файл может сортироваться с целью упорядочить фамилии по алфавиту. Если ключ - период полураспада изотопа, то - по убыванию этой величины, и т.п.

Существует множество различных методов сортировки, причем  для разных типов задач подходящими являются разные методы.  Практически  каждый метод сортировки содержит такие этапы:

-  сравнение, определяющее упорядоченность пары элементов;

-  перестановку, меняющую местами пару элементов;

-  способ организации операций сравнения и перестановки до  тех пор, пока все элементы не будут упорядочены.

В данной работе рассмотрены алгоритмы сортировки, которые наиболее часто излагаются в учебной литературе и достаточно просты для программирования.

1. Метод обмена соседних элементов (метод "пузырька")

При сортировке числового массива из N элементов  методом "пузырька" обрабатываемый массив просматривается несколько раз, от элемента  к элементу, причем текущий элемент сравнивается с соседним. Если числа в паре расположены в правильном порядке, то переходят к следующему  элементу, в противном случае меняют элементы местами и также переходят  к следующему элементу. За один просмотр самый большой из обрабатываемых элементов переставляется на самое последнее (N-е) место, так что на  следующем этапе обрабатывать нужно на один элемент меньше. Минимальный элемент  при этом перемещается на одну позицию вверх ("всплывает").  На  каждом  следующем просмотре максимальные из оставшихся элементов занимают  места  в  конце массива. Сортировка считается оконченной, если в ходе просмотра  не была произведена ни одна перестановка.

Рассмотрим пример массива из 6 чисел:

исходный массив:          1 7 6 4 2 5

1-й просмотр:             . 6 7 . . .     (за один проход

                          . . 4 7 . .      самый большой элемент

                          . . . 2 7     "тонет" на дно, а минимальный

                          . . . 5 7      "всплывает" на одну позицию) после 1-го просмотра:     1 6 4 2 5 7

                          └───────┘        (──── - область просмотра) 2-й просмотр:             . 4 6 . . .      ( для 2-го прохода)                           . . 2 6 . .

                                                                                                                                              2

                          . . . 5 6 . после 2-го просмотра:     1 4 2 5 6 7

                          └─────┘          (──── - область просмотра)

                           . . .           ( для 3-го прохода)  после 3-го просмотра:     1 2 4 5 6 7

Сортировка окончена, так как во время четвертого просмотра  не было совершено ни одной перестановки. Описание алгоритма:

               Заполнение массива (ввод данных)

               просмотр=0                Повторять

               │ перестановка=0

               │ просмотр=просмотр+1

               │ Для i=1 до N-просмотр выполнить

               │ │ Если A[i] > A[i+1] то

               │ │  │ Переставить(A[i],A[i+1])                │ │  │ перестановка=1 

               до выполнения условия перестановка=0

Вспомогательный алгоритм Переставить(a,b) осуществляет обмен значениями переменных a и b.