Под преобразованием массива данных следует понимать перестановку его элементов, оставляя неизменными их значения. Примером преобразования массивов данных может служить сортировка - классическая задача в вычислительной технике.
Слово сортировка используется в вычислительной технике для обозначения процесса перестановки элементов неупорядоченного массива данных для обеспечения их порядка- возрастания или убывания по какому либо параметру.
Механические сортировки- построение солдат по росту, раскладка денежных купюр или игральных карт по их достоинству и т.д., имеют место в повседневной жизни и кажутся простыми. Простота эта иллюзорна, потому что сортируется небольшое количество элементов.
Первые программы сортировки были написаны фон Нейманом в 1945 году и до середины 60-х годов какого-либо продвижения в теории сортировки не наблюдалось.
Проблема сортировки остро возникла с широким внедрением ЭВМ в бизнес, где неоходимо было обрабатывать огромные массивы числовой и текстовой информации. Технические средства внешней памяти тогдашних компьютеров - накопители на магнитной ленте (НМЛ) обеспечивали только последовательную запись и чтение информации, поэтому необходимо было упорядочивать данные для того, чтобы обеспечить их быстрый поиск.
Современные устройства внешней памяти компьютеров- накопители на магнитных дисках (НГМД) обеспечивают прямой доступ к записанной на них информации, что, в некоторых случаях организации массивов данных, позволяет обходиться без сортировки, но до сих пор сортировка остается важным аспектом вычислительной техники.
Методы сортировки делятся на прямые и улучшенные.
Прямые методы разделяются по принципу, лежащему в их основе, на сортировки:
Øобменом ('пузырьковая сортировка');
Øвыбором (выделением);
Øвставкой (включением).
На практике прямые методы сортировки используются крайне редко, так как имеют относительно низкое быстродействие, но для небольших массивов данных вполне приемлемы в качестве изучения принципов и методов сортировок.
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, с использованием оригинальных идей и рационализаций для ускорения процесса преобразования массива данных.
Этот метод сортировки является самым простым. Он применяется для преобразования небольших массивов данных и получил название 'пузырьковой сортировки'. Основой метода является сравнение двух элементов и их перестановка для получения порядка по возрастанию или убыванию значений элементов массива.
Метод 'пузырька' предполагает следующую физическую модель преобразования массива данных.
Из n чисел массива всплывает (как в бокале с шампанским) 'пузырек' - число, оказывающееся меньше, в случае сортировки по возрастанию, чем n-1 чисел. Затем всплывает 'пузырек' - число, оказывающееся меньше чем n-2 оставшихся, но больше чем первый всплывший 'пузырек' и т.д.
В качестве примера рассмотрим задачу сортировки одномерного массива методом 'пузырька'.
Задание. Прорешайте задачу. Дан вектор, состоящий из пяти случайных положительных целых чисел. Отсортировать исходный массив чисел в порядке возрастания значений элементов.
Постановка задачи.
Значения элементов массива получить их генерацией случайным образом, используя функцию Random в диапазоне [0, 100].
Вывести на экран дисплея исходный массив чисел.
Отсортировать исходный массив чисел по возрастанию их значений, распечатывая на экране дисплея каждую итерацию преобразования массива.
Вывести на экран дисплея отсортированный массив.
Алгоритм задачи.
Вызвать библиотечный модуль Crt, для обеспечения работы с экраном дисплея.
В блоке описания переменных определить имя массива a из пяти элементов и его тип byte.
Там же определить имена индексных переменных идентификаторами i, j, p тип byte и имена переменных k, c тип byte.
Очистить экран от возможно присутствующей там информации.
Вывести на экран сообщение: 'Исходный массив:'.
Организовать цикл со счетчиком для генерации и вывода на экран дисплея 5 случайных положительных целых чисел в диапазоне [0, 100].
Вывести на экран сообщение 'Сортировка:'.
Организовать внешний цикл со счетчиком для осуществления выбора первого элемента, второго и т.д. до n-1, где n - количество элементов массива, для осуществления операций просмотра, сравнения и перестановки элементов массива во внутреннем цикле.
Организовать внутренний цикл для осуществления просмотра, сравнения и перестановки элементов массива, начиная со второго. Через некоторую переменную k поменять местами значение первого элемента с позицией наименьшего числа в массиве.
Выводить состояние вектора на экран дисплея после каждой итерации перестановки до окончания процесса сортировки.
Накопить количество итераций перестановок в некоторой переменной c.
Вывести на экран сообщение 'Количество итераций: ' и распечатать это количество c.
Вывести на экран сообщение 'Отсортированный массив: '.
Организовать цикл вывода отсортированного массива.
Задержать изображение на экране до нажатия любой клавиши на клавиатуре.
Алгоритм сортировки одномерного массива (вектора) реализован следующей программой (см sortirovka.rar ). Здесь предлагается для рассмотрения и применения на практике стиль написания текста программы в виде ступенек, который позволяет не запутаться с операторными скобками begin end и с вложениями циклических операций друг в друга.
Один из возможных результатов работы программы выглядит следующим образом:
Сортировку выбором называют еще сортировкой поиском последовательных миниумов. При первом проходе ищется минимальное значение элементов массива, который затем меняется на первый элемент, затем поиск продолжается на оставшихся. Из оставшихся элементов ищется элемент с минимальным значением и меняется местами с первым из оставшихся, т.е. со вторым элементом исходного массива и т.д.
Один из возможных результатов работы программы выглядит следующим образом:
Сортировка методом выбора
Исходный массив
93
22
74
65
60
Сортировка:
93
22
74
65
60
22
93
74
65
60
22
60
74
65
93
22
60
65
74
93
Количество итераций: 4
Отсортированный массив:
22
60
65
74
93
Увеличивая количество сортируемых элементов массива, попробуйте оценить время сортировки. Предложите способ автоматической оценки времени работы программы в зависимости от количества сортируемых элементов.
Суть метода заключается в следующем алгоритме. Массив данных разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части принимается первый элемент массива.
Таким образом будет иметь место n-1 проход (где n размерность массива), каждый из которых будет включать четыре действия:
взятие очередного элемента из неотсортированной части и сохранение в дополнительной переменной;
поиск позиции в отсортированной части массива для вставки элемента взятого предыдущим действием, который бы не нарушил порядок;
сдвиг элементов массива для вставки элемента массива в отсортированную часть;
вставка элемента в найденную позицию.
Для реализации данного метода существует несколько алгоритмов, которые отличаются способом поиска позиции вставки.
Упражнение
Задание. Выполните приведенную программу. Она реализует один из способов сортировки вставкой.
Один из возможных результатов работы программы выглядит следующим образом (см sortirovka.rar ).
Сортировка методом вставки
Исходный массив
95
85
98
32
73
Сортировка:
85
95
98
32
73
85
95
98
32
73
32
85
95
98
73
32
73
85
95
98
Количество итераций: 4
Отсортированный массив:
32
73
85
95
98
В данном уроке были изучены прямые методы сортировок числовых данных- обменом ('пузырьковая сортировка'), выбором, вставкой, которые лежат в основе улучшенных методов сортировок. Приведены практические примеры программ, реализующих эти методы.
