Среда программирования Free Pascal, методы сортировки

По условию оба массива-части упорядочены. Сформировать массив с, который будет содержать 13 элементов.

Решение:

Введем обозначения:

• i — номер обрабатываемого элемента части a;

• j - номер обрабатываемого элемента части b;

• l — номер заполняемого элемента массива c.

Поскольку заполнение массива  c  ведется с его начала, на первом шаге значение  l = 1.

1-й шаг: на первое место в массиве  c  претендуют а [k + 1] = 3  и  b [m + 1] = 1

(i = k + 1, j = m + 1). Так как 1 < 3, в массив  c  надо занести 1 и перейти к следующему

элементу части b, то есть увеличить  j  на 1 (значение j  станет равно т + 2), а  также увеличить на 1 значение l (значением l будет 2).

2-й шаг: теперь надо сравнить а [k + 1] = 3  и  b [m + 2] = 5.  3 < 5, следовательно, на

второе место в  c  надо занести а [k + 1] = 3. Затем надо увеличить на 1 значения i и l.

3-й шаг: на третье место массива  c  претендуют два одинаковых элемента —

а [k + 2] = 5  и  b [m + 2] = 5. В этом и подобных случаях договоримся заносить в  c

первым элемент из части  a. Таким образом, с [ 3 ] = а [k + 2], а значение l = 4, i = k + 3,      

j остается равным т + 2.

4 - 11-й шаги: рассуждая аналогичным образом, надо занести в  c  элементы 6, 7, 8, 9, 11, 12, 13, 16. После выполнения 11-го шага первая часть будет занесена в  c  полностью, значение j равно т + 7, значение l равно 12.

12-й шаг: так как часть  a закончилась, а «хвост» части  b  упорядочен по условию,

то двенадцатым элементом массива с будет первый элемент «хвоста»  b, то

есть b [ m + 7 ] = 18.

13-й шаг: последним элементом массива с будет последний элемент b - 20.

На рисунке схематично изображен процесс заполнения массива с.

Сейчас можем описать процедуру слияния двух упорядоченных массивов размерностей

n  и  m  в третий упорядоченный массив, размерность которого   p (р = n + m).

Procedure  sorting4 (k, m, n : integer);

Begin

         i : = k + l;

         j : = m + l;

         k : = l;

         while  ( i < = m )  and  ( j < = n )  do  {пока не закончилась хотя бы одна часть}

         Begin

                    if  a [ i ] < = b [ j ]   then

                    Begin

                              c [ k ] : = a [ i ];   inc ( i );

                    End

                    else

                             Begin

                                        c [ k ] : = b [ j ];  inc ( j );

                             End;

                    inc ( k );

         End;   {один из массивов-частей обработан полностью, осталось  перенести  

         в 'с' остаток другого массива-части}                                                                                                 

         while  i < = m   do

         Begin

                 c [ k ] : = a [ i ];  inc ( i );  inc ( k )

         End;

         while  j < = n  do

         Begin

                 c [ k ] : = b [ j ];  inc ( j );  inc ( k )

         End

End.

Далее остается лишь переписать результат слияния рассматриваемых частей  массив с - обратно в массив а.

5. Обменная сортировка с разделением (сортировка Хоара)

Сортировка методом вставок (методом «пузырька») часто является самой неэффективной. Это обусловлено самой идеей метода, которая требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы.

Можно существенно улучшить метод сортировки, основанный на обмене.

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

Он основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. Предложил этот метод Ч.Э.Р.Хоар в 1962 г. Поскольку производительность этого метода просто впечатляюща, автор назвал его «быстрой сортировкой».

Идея метода:

1. В исходном неотсортированном массиве выбрать некоторый элемент х = а[к] (барьерный элемент).

2. Переставить элементы массива таким образом, чтобы слева от х оказались элементы массива, меньшие или равные х, а справа — элементы массива, большие х.

Пусть при этом элемент х попадет в позицию с номером к, тогда массив будет иметь вид ( a [1], а [2], ..., а [к-1] ), а [к], ( а [к+1], ..., а [n] ).

Каждый из элементов a [1], a [2], ..., а [к - 1] меньше либо равен а [к], каждый из элементов а [к+1],..., а [n] больше а [к]. Отсюда можно сделать вывод, что элемент а [к] стоит на своем месте. А исходный массив при этом разделится на две неотсортированные части, барьером между которыми является элемент а [к].

Для дальнейшей сортировки необходимо применить пп.1, 2 для каждой из этих частей. И так до тех пор, пока не останутся подмассивы, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.

Одной из целей сортировки является облегчение последующего поиска элементов в отсортированном множестве. Результатом поиска служит элемент множества, равный эталону, или отсутствие такового.

Пример решения задачи.

Задание:

Составить программу «быстрой сортировки».

Решение:

Пусть исходный массив состоит из восьми элементов:

                                     8   12  3   7  19   11  4  16

В качестве барьерного элемента будем брать средний элемент массива. Барьерный               элемент - 7. Произведя необходимые перестановки для разделения, получим:

                                    (4   3)   7   (12   19  11   8   16)

Число 7 стоит на своем месте. Далее сортируем подмассивы, элементы которых заключены в скобки. Этот процесс будем повторять до тех пор, пока не получим полностью отсортированный массив.

Массив отсортирован полностью.

Алгоритм «быстрой» сортировки можно определить как рекурсивную процедуру, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива.

Program  Example;

var  a :  array[1..10]  of   integer;

Procedure   init;  {формирование массива из файла}

var  f :  text;

i:  integer;

Begin

           assign ( f , ' c : \ s . dat ' );  reset ( f );

           for  i : = l  to  10  do  read ( f , a [ i ] );

End;

Procedure  Print; {печать массива}

var  i :  integer;

Begin

          for  i : = l  to 10  do  Write  ( a [ i ] : 5);

          writeln

End;

Procedure Quick_sorting ( m, 1:  integer);

var  i, j, x, w:  integer;

Begin

             i : = m;  j : = l;  x : = a [ ( m + l )   div 2 ];

             repeat

             while  a [ i ] < x   do  inc ( i );                                                                                             

             while  a [ j ] > x   do  dec ( j );

             if   i < j   then

             Begin

                         w : = a [ i ];  a [ i ] : = a [ j ];   a [ j ] : = w;  inc ( i);  dec ( j );

             End

             until   i > j;

             if   m < j   then  quick_sorting ( m, j ) ;

             if   i < l   then  quick_sorting ( i, 1 );

End;

Begin  {основная программа}

             writeln ( 'массив: ' );  init;  print;  quick_sorting ( 1, 10 );

             writeln ( 'отсортированный массив' );  print;

End.

Заключение

Основными достоинствами языка Паскаль являются лёгкость при изучении и наглядность и простота написания программ. Кроме того, в Паскале отражена концепция структурного программирования, имеется богатый набор различных типов данных и программные средства, позволяющие доказывать правильность написанных программ, в том числе и программ, использующих алгоритмы сортировки.

В курсовой работе нами были подробно описаны следующие виды сортировок:

       сортировка вставками;

       сортировка методом простого выбора;

       сортировка методом прямого включения;

       сортировка методом слияния;

       обменная сортировка с разделением.

А также рассмотрены примеры задач и приведены алгоритмы их выполнения на Паскале с применением данных сортировок.

Сравнивая различные методы сортировок, можно сделать следующие выводы:

1.       Каждый вид сортировки необходим при решении задачи с определённым типом массива;

2.       Сортировка вставками наиболее часто используется в качестве примера при обсуждении других языков, но она не эффективна при упорядочивании массивов с большим числом элементов;

3.       Для массивов, не содержащих повторяющихся элементов, более часто применяется сортировка методом простого выбора;

4.       Наиболее эффективной и «быстрой» сортировкой является обменная сортировка с разделением.

Список используемой литературы

1. Баррон Д. Рекурсивные методы в программировании: Пер. с англ. - М.: Мир, 1974.
2. Бердж В. Методы рекурсивного программирования: Пер. с англ. - М.: Машиностроение, 1983.
3. Брукс Ф. П. Как проектируются и создаются программные комплексы / Очерк

            по системному программированию: Пер. с англ. - М.: Наука, 1979.

4. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. - М.: Мир, 1989.
5. Вирт Н. Алгоритм + структура данных = программа: Пер. с англ. - М.: Мир, 1985.
6. Кнут Д. Искусство программирования: Пер. с англ. Т. 1, 2, 3.-М.: Мир, 1976-1978.
7. Кристиан К.  Руководство по программированию на языке МОДУЛА-2: Пер. с англ. - М.: Мир, 1989.
8. Лорин Г. Сортировка и системы сортировки: Пер. с англ. - М.: Наука, 1983.
9. Миков А. И. Информатика. Введение в компьютерные науки. - Пермь: ПГУ, 1998.
10. Могилёв А. В. Практикум по информатике: Учеб. пособие для студ. высш. учеб. заведений; Под ред. Е. К. Хеннера. - М.: Издательский центр «Академия», 2001. 608 с.
11. Рейнгольд Э., Нивергелът Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: Пер. с англ. — М.: Мир, 1980.
12. Свердлов С. З. Языки программирования и методы трансляции: Учебное пособие. Спб.; Питер, 2007.
13. Холстед М. Х. Начала науки о программах: Пер. с англ. - М.: Финансы и статистика, 1981.

4