Разработка программ обработки массивов

              Оглавление.                                                             Стр. 

     Введение

     1. Математическая постановка задачи.

     2. Описание алгоритма решения задачи. 

     3. Обоснование выбора языка программирования.

     4.Разработка  и описание программы.

     5.Листинг  программы. 

     6.Результаты  работы программы.

     Заключение 
 
 
 
 
 
 
 
 
 
 
 
 

Введение.

  1. Тема курсового проекта:  Разработка программ обработки массивов.

  2. Исходные  данные и основные требования:

  Характеристикой строки заданной целочисленной матрицы  размером 10×10 назовем сумму её  положительных четных элементов. Разработать алгоритм и составить программу перестановки строк заданной матрицы в соответствии с ростом их характеристик. Предусмотреть в программе два варианта задания значений элементов исходной матрицы:

• генератором случайных чисел;
• путем ввода значений с клавиатуры.

  Программа должна быть составлена на языке программирования Паскаль или в среде  программирования Delphi.

  Задачи  сортировки массивов, часто встречаются  в приложениях. Задачи сортировки встречаются повсеместно, об области применения излишне говорить. Сортировка данных необходима практически для любой их базы.

  В наиболее современных языках программирования эти задачи просто решаются встроенными  функциями или опциями. Например, набрав такой код в Visial Basic: 

  Private Sub CommandButton1_Click()

  Range("A1:I10").Select

      Selection.Sort Key1:=Range("I1"), Order1:=xlAscending, Header:=xlGuess, _

          OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, _

          DataOption1:=xlSortNormal

  End Sub 

  ..мы  добьемся следующего: при нажатии  кнопки по величине значений  в 10-м столбца некой таблицы  в диапазоне "A1:I10"  будут сортироваться сверху вниз по возрастанию строки. То есть будет решена основная часть нашей задачи. В Delphy есть объекты ActiveX с аналогичными функциями. Свойство Sorted есть у объекта DataSourse, этот объект служит для связи с внешними базами данных, затем они отражаются виде таблиц F1Book, таким образом, данные можно отсортировать ещё при поступлении в программу. Между тем алгоритмы сортировки достаточно сложны.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.Математическая  постановка задачи.

С математической точки зрения проблема сортировки представляет собой просто различные способы  перебора массивов с отслеживанием  некой величины – критерия сортировки. Рассмотрим 4 способа сортировки.

  1.1. Сортировка включением

  Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями. Идея алгоритма очень проста. Пусть  имеется массив ключей a[1], a[2], ..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2] ...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если эти элементы поменялись местами, то повторяется процедура сравнения/обмена местами нового элемента, включенного в блок, с нижестоящими элементами. То есть, повторится сравнение/обмен для нового элемента a[i-1] с элементами с меньшим индексом. Процедура спустится, как бы на уровень вниз, до сравнения  нового, включенного элемента a[i-1] с прежним элементом a[i-2]. Если и они поменяются местами, процедура опять спустится на уровень вниз. Таким образом, вниз прогоняются  минимальные элементы. Когда удается встретить такой элемент a[j], что a[j] <= a[i], (то есть, не надо делать обмен и гнать элемент далее вниз) производится переход к обработке элемента a[i+1] – то процедура есть идет на уровень вверх. То же самое будет, если эта процедура обмена/сравнения достигла нижней границы массива (то есть сравнены/спущены вниз все элементы обрабатываемой области). Так продолжается, пока обработанная область не достигнет верхней границы массива.  Поскольку в обработанную область каждый раз включается новый элемент метод и назван сортировкой включением.

  Легко видеть, что в лучшем случае (когда  массив уже упорядочен) для выполнения алгоритма с массивом из n элементов  потребуется n-1 сравнение и 0 пересылок. В худшем случае (когда массив упорядочен в обратном порядке) потребуется n(n-1)/2 сравнений и столько же пересылок. Таким образом, можно оценивать сложность метода простых включений как O(n²).

Таблица 1.  Пример сортировки методом  простого включения

 

  Можно сократить число сравнений, применяемых  в методе простых включений, если воспользоваться тем фактом, что при обработке элемента a[i] массива элементы a[1], a[2], ..., a[i-1] уже упорядочены, и воспользоваться для поиска элемента, с которым должна быть произведена перестановка, методом двоичного деления. В этом случае оценка числа требуемых сравнений становится O(n∙log(n)). Заметим, что поскольку при выполнении перестановки требуется сдвижка на один элемент нескольких элементов, то оценка числа пересылок остается O(n²). Это будет усовершенствованный метод.

1.2. Обменная сортировка.

  Простая обменная сортировка (в просторечии  называемая "методом пузырька") для массива a[1], a[2], ..., a[n] работает следующим  образом. Начиная с конца массива  сравниваются два соседних элемента (a[n] и a[n-1]). Если выполняется условие a[n-1] > a[n], то значения элементов меняются местами. Процесс продолжается для a[n-1] и a[n-2] и т.д., пока не будет произведено сравнение a[2] и a[1]. Понятно, что после этого на месте a[1] окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются a[3] и a[2]. И так далее. На последнем шаге будут сравниваться только текущие значения a[n] и a[n-1]. Понятна аналогия с пузырьком, поскольку наименьшие элементы (самые "легкие") постепенно "всплывают" к верхней границе массива. Для метода простой обменной сортировки требуется число сравнений n∙(n-1)/2, минимальное число пересылок 0, а среднее и максимальное число пересылок - O(n²).  
 
 
 
 
 
 

  Таблица 2. Пример сортировки методом пузырька  

  1.3. Сортировка выбором

  При сортировке массива a[1], a[2], ..., a[n] методом  простого выбора среди всех элементов  находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3], ..., a[n], ... a[j], a[j+1], ..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение. Работа алгоритма иллюстрируется примером в таблице 3.

  Таблица3 Пример сортировки простым выбором

 

  Для метода сортировки простым выбором  требуемое число сравнений – n(n+2)/2. Порядок требуемого числа пересылок (включая те, которые требуются  для выбора минимального элемента) в худшем случае составляет O(n²). Однако порядок среднего числа пересылок есть O(n∙log(n)), что в ряде случаев делает этот метод предпочтительным.

  1.4. Сортировка разделением (Quicksort)

  Метод сортировки разделением был предложен  Чарльзом Хоаром  в 1962 г. Этот метод  является развитием метода простого обмена и настолько эффективен, что его стали называть "методом быстрой сортировки - Quicksort".

  Основная  идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x, после  чего массив просматривается слева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массив просматривается справа, пока не встретится элемент a[j] такой, что a[j] < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x. Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Понятно, что как обычно, рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива. Проследим этот процесс на примере нашего стандартного массива.

  Таблица 4. Пример быстрой  сортировки

 

  Алгоритм  недаром называется быстрой сортировкой, поскольку для него оценкой числа сравнений и обменов является O(n×log n). На самом деле, в большинстве утилит, выполняющих сортировку массивов, используется именно этот алгоритм.

  1.4. Сравнение методов  сортировки.

  Для рассмотренных в простых методов сортировки существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее число сравнений ключей (C) и пересылок элементов массива (M). Эти формулы приведены в таблице 5.

   Для  оценок сложности усовершенствованных методов сортировки точных формул нет. Известно лишь, что для сортировки методом Quicksort - O(n×log n). Однако результаты экспериментов показывают, что Quicksort показывает результаты в 2-3 раза лучшие, чем другие методы. Видимо, по этой причине именно Quicksort обычно используется в стандартных утилитах сортировки.

  Таблица 5. Характеристики простых  методов сортировки