Преобразование одномерных массивов данных - сортировка

Преобразование одномерных массивов данных  ­ сортировка        Занятие 8 1. Урок 1.  Преобразование   одномерных    массивов    данных ­ сортировка.      Методы   сортировки   числовых  данных. Сортировка обменом. 2. Урок 2.  Сортировка выбором. 3. Урок 3.  Сортировка вставкой. 4. Контрольные вопросы и упражнения.  Урок 1.  Преобразование   одномерных   массивов   данных ­ сортировка.  Методы сортировки числовых  данных. Сортировка обменом. 1.1. Преобразование   одномерных   массивов   данных ­ сортировка. 1.2. Методы сортировки числовых данных. 1.3. Сортировка обменом. 1.1.  Преобразование   одномерных   массивов   данных ­ сортировка Под преобразованием массива данных следует понимать действия, которые приводят к его изменению, как с количественной,   так   и   с   качественной   стороны.   Под   количественной   стороной   преобразования   массива   следует понимать   изменение   значения   его   элементов   по   некоторому   логическому   условию.   Под   качественной   стороной преобразования   массива   данных   следует   понимать   изменение   порядка   следования   его   элементов,   оставляя неизменными их значения. Примером качественного преобразования массивов данных может служить  сортировка  ­ классическая задача в вычислительной технике.   Слово  сортировка  используется   в   вычислительной   технике   для   обозначения   процесса   перестановки элементов неупорядоченного массива данных для обеспечения их порядка ­ возрастания или убывания, по какому либо параметру. Механические сортировки ­ построение солдат по росту, раскладка денежных купюр или игральных карт по их достоинству и т.д., имеют место в повседневной жизни и кажутся простыми. Простота эта иллюзорна,   потому что сортируется небольшое количество элементов. Первые программы сортировки были написаны фон Нейманом в 1945 году, и до середины 60­х годов какого­ либо продвижения в теории сортировки не наблюдалось. Проблема   сортировки   остро   возникла   с   широким   внедрением   ЭВМ   в   бизнес,   где   необходимо   было обрабатывать огромные массивы числовой и текстовой информации. Технические средства внешней памяти тогдашних компьютеров ­ накопители на магнитной ленте (НМЛ) обеспечивали только последовательную запись данных.   Для быстрого  поиска информации  в этом  случае,  необходимо было  упорядочить данные,  чтобы использовать быстрые алгоритмы поиска информации в них. Современные   устройства   внешней   памяти   компьютеров   ­   накопители   на   магнитных   дисках   (НГМД) обеспечивают прямой доступ к записанной  на  них  информации,   что,   в некоторых   случаях   организации массивов данных,   позволяет обходиться без сортировки, но до сих пор сортировка остается   необходимым элементом почти любого  программного продукта обработки информации. 1.2.  Методы сортировки числовых данных Все методы сортировки делятся на  прямые и улучшенные. Прямые методы разделяются по принципу, лежащему в их основе, на сортировки: ­ ­ ­ обменом ("пузырьковая сортировка"); выбором (выделением); вставкой (включением). На практике прямые методы сортировки используются крайне редко, т.к. имеют относительно низкое быстродействие, но для  небольших массивов данных вполне приемлемы в качестве изучения принципов и методов сортировок. Улучшенные   методы   сортировки   основываются   на   тех   же   принципах,   что   и   прямые,   с   использованием оригинальных идей и рационализацию  для ускорения процесса  преобразования  массива данных. 1.3.  Сортировка  обменом Этот метод сортировки является самым простым. Он применяется для преобразования небольших массивов данных,  и получил название "пузырьковой сортировки".  Основой метода является  сравнение  двух элементов и их перестановка  для получения порядка по возрастанию или  убыванию значений элементов массива. Метод "пузырька" предполагает следующую физическую модель преобразования массива данных.   Из   n   чисел массива всплывает (как в бокале с шампанским) "пузырек" ­ число, оказывающееся меньше, в случае сортировки по возрастанию, чем  n ­ 1 чисел.  Затем всплывает "пузырек" ­ число, оказывающееся меньше чем  n ­ 2  оставшихся, но больше чем первый  всплывший "пузырек" и т.д. В качестве примера рассмотрим задачу сортировки одномерного массива методом "пузырька". 49 Преобразование одномерных массивов данных ­ сортировка.  Методы сортировки числовых данных. Сортировка обменом, выбором, вставкой Задача.  Дан вектор, состоящий из 5­ти случайных положительных целых чисел. Отсортировать   исходный массив чисел в порядке возрастания значений элементов. Постановка задачи 1. Значения  элементов массива  получить  их  генерацией  случайным  образом, используя функцию Random в диапазоне  [0, 100]. 2. Вывести на экран дисплея исходный массив чисел. 3. Отсортировать исходный массив чисел по возрастанию их значений, распечатывая    на экране дисплея каждую итерацию преобразования массива. 4. Вывести  на экран дисплея отсортированный массив. Алгоритм  задачи 1. Вызвать библиотечный модуль  Crt,  для обеспечения работы с экраном дисплея. 2. В блоке описания переменных определить имя массива  a  из 5­ти элементов и его тип  byte. 3. Там   же   определить   имена   индексных   переменных   идентификаторами    i,  j,  p    тип    byte    и     имена переменных  k, c  тип  byte. 4. Очистить   экран от возможно присутствующей там информации. 5. Вывести на экран сообщение:  "Исходный массив:" 6. Организовать         цикл     со     счетчиком     для       генерации       и  вывода  на  экран   дисплея  5    случайных положительных  целых чисел в диапазоне [0, 100]. 7. Вывести на экран сообщение "Сортировка:" 8. Организовать внешний цикл со счетчиком для осуществления выбора первого элемента,  второго  и т.д.  до n  ­ 1,   где   n  ­ количество элементов массива, для осуществления операций просмотра, сравнения   и перестановки элементов массива  во  внутреннем  цикле. 9. Организовать   внутренний   цикл   для   осуществления   просмотра,   сравнения   и  перестановки  элементов массива,   начиная  со  второго.  Через  некоторую  переменную    k   поменять  местами     значение  первого элемента с позицией наименьшего числа в массиве. 10. Выводить   состояние   вектора   на   экран   дисплея   после   каждой   итерации   перестановки   до   окончания процесса сортировки. 11. Накопить количество итераций перестановок в некоторой переменной  c. 12. Вывести на экран сообщение "Количество итераций: " и распечатать это количество c. 13. Вывести на экран сообщение "Отсортированный массив: ". 14. Организовать цикл вывода отсортированного массива. 15. Задержать изображение на экране до нажатия любой клавиши на клавиатуре. Алгоритм сортировки одномерного массива (вектора) реализован следующей программой. Здесь предлагается для рассмотрения и применения на практике стиль написания текста программы в виде ступенек, который позволяет не запутаться с операторными скобками  begin  end  и с вложениями циклических операций друг в друга. Program V1L09P1; {Сортировка вектора методом "пузырька"} Uses Crt; Const n=5; Var  a :array [1..n] of byte; i,j,p,k,c :byte; {} begin ClrScr; Randomize; n:=5; WriteLn('Исходный массив:'); {Стирание экрана} {Установка генератора случайных чисел} {Определение верхней границы массива} {Генерация исходного массива} for i:=1 to n do  begin a[i]:=Random(100); Write(a[i]:3)        {Генерация знач. элем. массива} {Печать элементов массива} end; {} WriteLn('Сортировка:'); {} c:=0; for i:=1 to n­1 do 50    {Начальное значение счетчика итераций} {Внешний цикл сортировки} begin     for j:=i+1 to n do       begin         if a[i]>a[j] then              begin                k:=a[i];                 a[i]:=a[j];                  a[j]:=k           end        end; for p:=1 to n do     Write(a[p]:3); {Внутренний цикл сортировки} {Условие перестановки} {Переменная для обмена значений элементов массива} {Обмен значений элементов массива} {Обмен закончен} {Цикл печати состояния массива} {Счетчик итераций}        WriteLn;        c:=c+1   end; {} WriteLn('Количество итераций: ',c); Write('Отсортированный массив: '); for i:=1 to n do Write(a[i]:3); {} ReadKey end. {Цикл печати отсортированного массива} Возможный вариант результата решения Исходный массив 47 94  34  26  37 Сортировка: 26 94  47  34  37 26 34  94  47  37 26 34  37  94  47 26 34  37  47  94 Количество итераций: 4 Отсортированный массив: 26 34  37  47  94 Урок 2.  Сортировка выбором Сортировку выбором называют еще  сортировкой поиском последовательных минимумов. При первом проходе ищется минимальное значение элементов массива, который затем меняется на первый элемент. Далее поиск продолжается   на   оставшихся   значениях.   Из   оставшихся   элементов   ищется   элемент   с   минимальным   значением   и меняется местами с первым из оставшихся, т.е. со вторым элементом исходного массива и т.д. Решая задачу предыдущего урока, произведем сортировку исходного массива по следующей программе:  {Вызов библиотечного модуля} {Значение верхней границы массива} Program V1L09P2; {Сортировка выбором} Uses Crt; Const n=5; Var          v :array [1..n] of byte; i,j,min,imin,c :byte; begin ClrScr; Randomize; WriteLn('Сортировка методом выбора (вставкой)'); WriteLn('Исходный массив:'); {Стирание экрана} {Установка генератора случайных чисел} {Генерация исходного массива} for i:=1 to n do     begin          v[i]:=Random(100);          Write(v[i]:3)     end; {} WriteLn; WriteLn('Сортировка:'); {} c:=0; for j:=1 to n­1 do {Генерация случайных целых чисел от 0 до 100} {Двойной перевод строки} {Начальное значение счетчика итераций} {Внешний цикл сортировки} 51 Преобразование одномерных массивов данных ­ сортировка.  Методы сортировки числовых данных. Сортировка обменом, выбором, вставкой begin   min:=v[j];   imin:=j;   for i:=j+1 to n do     if v[i]a[j] do      j:=j+1; {Фиксация позиции вставки} {Цикл сдвига элементов массива для вставки}  for k:=i­1 downto j do  a[k+1]:=a[k]; a[j]:=b; {Вставка элемента массива в найденную позицию} {Цикл печати итераций сортировки}   for p:=1 to n do       Write(a[p]:3);   c:=c+1;   WriteLn   end; {} WriteLn('Количество итераций', c); WriteLn; WriteLn('Отсортированный массив: '); {Счетчик итераций} {Цикл печати отсортированного массива} for i:=1 to n do Write(a[i]:3); {} ReadKey end. Возможный вариант результата решения Сортировка методом вставки Исходный массив:  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 53 Преобразование одномерных массивов данных ­ сортировка.  Методы сортировки числовых данных. Сортировка обменом, выбором, вставкой В   данном   занятии   были   изучены   прямые   методы   сортировок   числовых   данных   ­   обменом   ("пузырьковая сортировка"), выбором, вставкой, которые лежат в основе улучшенных методов сортировок. Приведены практические примеры программ, реализующих эти методы. Контрольные вопросы и упражнения Зачем нужно упорядычевать (сортировать) массив данных? 1. Что такое сортировка массива данных? Дайте определение. Приведите примеры. 2. 3. Какие группы сортировок существуют. Назовите? 4. Назовите методы простых сортировок? Чем  они одинаковы и чем отличны ? 5. В чем состоит  принцип "пузырьковой" сортировки? 6. В чем состоит принцип сортировки вставкой? 7. В чем состоит принцип сортировки выбором? 8. Предложите способы исследования выбора метода простой сортировки по времени ее осуществления с максимальным массивом данных, размещаемым в ОЗУ компьютера. 9. Предложите  показатели для оценки методов простых сортировок? 10. Предложите свой способ сортировки. Для заметок, вопросов и ответов ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ 54 ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ _____________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ ______________________________________________________________________________________________________ 55