Методы сортировки массивов

СОДЕРЖАНИЕ:

 

        
 
 
 
 
 
 
 
 
 

Введение.

Около трех с половиной десятилетий  минуло с тех пор, как в педвузах введено в качестве учебной дисциплины программирование для ЭВМ. При колоссальной скорости изменений в самом предмете, всегда существенно превышавшей скорость центральных издательских механизмов, специально ориентированные на программы педвузов книги выходили не чаще, чем раз в десятилетие – едва ли не соразмерно скорости смены поколений ЭВМ. Сегодня полки книжных магазинов ломятся  от изданий по информатике. Однако преподавателю (а более всего студенту) специальные учебные книги, содержание  и направленность которых отвечают заданному учебному плану и программе все-таки очень нужны. Сейчас помимо программирования на некоторых специальностях в педвузах введены и другие более сложные спецкурсы, находящиеся на стыке прикладной (дискретной) математики и информатики.    

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

1. Задачи сортировки.

1.1.Общие  положения.

Основная задача – продемонстрировать различные методы  сортировки  и выделить  наиболее  эффективные из  них. Сортировка – достаточно  хороший пример  задачи,  которую  можно  решать с помощью многих  различных алгоритмов. Каждый  из  них  имеет  и  свои  достоинства,  и  свои  недостатки, и  выбирать  алгоритм  нужно,  исходя из  конкретной  постановки  задачи.

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

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

Выбор  алгоритма  зависит  от  структуры  обрабатываемых  данных – это  почти  закон, но  в  случае  сортировки  такая  зависимость  столь  глубока, что соответствующие  методы  разбили  на  два  класса – сортировку  массивов  и  сортировку  файлов  (последовательностей). Иногда  их  называют внутренней  и  внешней  сортировкой, поскольку  массивы хранятся  в быстрой, оперативной, внутренней  памяти  машины  со  случайным доступом, а файлы обычно  размещаются в более медленной, но  и более емкой внешней памяти, на  устройствах, основанных  на  механических  перемещениях  (дисках  или лентах).

Прежде  чем  идти  дальше, введем  некоторые  понятия  и  обозначения. Если  у нас есть  элементы а , a , …… , а то  сортировка  есть  перестановка  этих  элементов в массив  аk , ak , …… ,ak где ak <= ak <= ….. <= ak .

Считаем, что тип  элемента  определен  как  INTEGER .

Const n=???; //здесь указывается нужная длина массива

Var A: array[1..n] of integer;

Выбор  INTEGER  до  некоторой степени произволен. Можно было  взять и

другой  тип, на  котором  определяется  общее  отношение  порядка.

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

1.2. Постановка задачи  сортировки  массивов.

Основное  условие:  выбранный  метод  сортировки  массивов  должен  экономно  использовать  доступную  память. Это предполагает, что  перестановки, приводящие  элементы  в  порядок, должны  выполняться  на  том  же  месте  т. е.  методы, в  которых  элементы  из  массива  а  передаются  в  результирующий массив  b, представляют  существенно меньший интерес. Мы  будем сначала классифицировать  методы  по  их  экономичности, т. е.  по  времени  их  работы. Хорошей  мерой  эффективности  может  быть C – число необходимых сравнений ключей и M – число пересылок (перестановок)  элементов. Эти числа суть  функции от  n – числа сортируемых элементов. Хотя  хорошие  алгоритмы  сортировки  требуют  порядка  n*log n  сравнений, мы  сначала разберем несколько простых и очевидных методов, их  называют  прямыми, где требуется порядка n2  сравнений ключей. Начинать  разбор  с прямых  методов, не трогая  быстрых  алгоритмов, нас заставляют  такие причины:

1. Прямые  методы  особенно  удобны  для  объяснения  характерных черт  основных  принципов  большинства  сортировок.
2. Программы  этих  методов  легко  понимать, и  они  коротки.
3. Усложненные  методы  требуют  большого  числа  операций, и поэтому  для  достаточно  малых  n  прямые  методы  оказываются быстрее, хотя  при больших n  их  использовать, конечно, не  следует.

Методы  сортировки  “ на  том  же  месте “  можно  разбить  в  соответствии  с  определяющими  их  принципами  на  три  основные  категории:

• Сортировки  с  помощью  включения  (by  insertion).
• Сортировки с помощью выделения (by  selection).
• Сортировка  с  помощью  обменов  (by  exchange).                      

Теперь  мы  исследуем  эти  принципы  и  сравним  их. Все  программы оперируют  массивом  а.

Const n=<длина массива>

a: array[1..n] of integer;

2. Методы сортировки  массивов.

2.1. Простые методы  сортировки массивов.

2.1.1. Сортировка  с   помощью  прямого   включения.

Такой  метод  широко  используется  при  игре  в  карты. Элементы  мысленно делятся  на  уже  “готовую”  последовательность  а , … , а    и исходную последовательность. При каждом  шаге, начиная с I = 2  и увеличивая  i каждый  раз  на  единицу, из исходной  последовательности  извлекается  i- й элементы  и перекладывается в готовую последовательность, при этом  он вставляется на  нужное  место.

ПРОГРАММА 2.1. ССОРТИРОВКА  С  ПОМОЩЬЮ  ПРЯМОГО  ВКЛЮЧЕНИЯ.

PROGRAM SI;

VAR

    I,J,N,X:INTEGER;

    A:ARRAY[0..50] OF INTEGER;

BEGIN

     WRITELN(‘Введите  длину массива’);

     READ(N);

     WRITELN(‘Введите  массив’);

         FOR I:=1 TO N DO READ(A[I]);

       FOR I:=2 TO N DO

           BEGIN

               X:=A[I];

              A[0]:=X;

               J:=I;

               WHILE X<A[J-1] DO

                    BEGIN

                        A[J]:=A[J-1];

                        DEC(J)

                    END;

                  A[J]:=X

           END;

    WRITELN('Результат:');

    FOR I:=1 TO N DO WRITE(A[I],' ')

END.

Такой  типичный  случай  повторяющегося  процесса  с  двумя  условиями 

окончания  позволяет  нам  воспользоваться  хорошо  известным  приемом 

“барьера” (sentinel).

Анализ  метода  прямого  включения. Число  сравнений ключей  (Ci) при i- м просеивании самое большее равно i-1, самое меньшее – 1; если  предположить, что все перестановки  из  n ключей  равновероятны, то среднее число сравнений – I/2. Число же  пересылок Mi  равно Ci + 2 (включая барьер). Поэтому  общее  число  сравнений  и   число  пересылок  таковы:

Cmin = n-1                 (2.1.)                  Mmin = 3*(n-1)                (2.4.)

Cave = (n2+n-2)/4      (2.2.)                  Mave = (n2+9*n-10)/4     (2.5.)

Cmax = (n2+n-4)/4     (2.3.)                  Mmax = (n2+3*n-4)/2     (2.6.)

Алгоритм  с прямыми  включениями  можно  легко улучшить, если обратить  внимание  на  то, что  готовая  последовательность, в  которую  надо вставить  новый  элемент, сама  уже  упорядочена. Естественно  остановиться  на двоичном  поиске, при  котором  делается  попытка  сравнения  с  серединой готовой  последовательности, а  затем  процесс  деления  пополам  идет  до  тех пор, пока  не  будет  найдена  точка  включения. Такой  модифицированный алгоритм  сортировки  называется  методом  с    двоичным  включением ( binary insertion). 

ПРОГРАММА 2.2. СОРТИРОВКА  МЕТОДОМ  ДЕЛЕНИЯ  ПОПОЛАМ.

PROGRAM BI;

VAR

    I,J,M,L,R,X,N:INTEGER;

    A:ARRAY[0..50] OF INTEGER;

BEGIN

    WRITELN('Введи длину массива');

    READ(N);

    WRITELN('Введи массив');

    FOR I:=1 TO N DO READ(A[I]);

    FOR I:=2 TO N DO

       BEGIN

            X:=A[I];L:=1;R:=I;

            WHILE L<R DO

                BEGIN

                    M:=(L+R) DIV 2;

                    IF A[M]<=X THEN L:=M+1 ELSE R:=M

                END;

             FOR J:=I DOWNTO R+1 DO A[J]:=A[J-1];

             A[R]:=X

       END;

    WRITELN('Результат:');

    FOR I:=1 TO N DO WRITE(A[I],' ')

END.

Анализ  двоичного  включения. Место  включения  обнаружено, если  L=R. Таким образом, в конце поиска  интервал  должен  быть  единичной длины; значит, деление  его  пополам  происходит I*log I  раз. Таким образом:

C = Si: 1<=i<=n: [log I ]        (2.7.)

Аппроксимируем  эту  сумму  интегралом

Integral (1:n) log x dx = n*(log n – C) + C       (2.8.)

Где  C = log e = 1/ln 2 =  1.4426… .                (2.9.)

2.1.2.Сортирвка  с помощью прямого  выбора.

Этот  прием  основан  на  следующих  принципах:

1. Выбирается элемент с наименьшим  ключом
2. Он  меняется  местами  с  первым  элементом  а1.
3. Затем  этот  процесс  повторяется  с  оставшимися  n-1 элементами, n-2 элементами  и т.д.  до  тех пор, пока  не  останется один, самый большой элемент.

ПРОГРАММА 2.3. СОРТИРВКА  С  ПОМОЩЬЮ  ПРЯМОГО  ВЫБОРА.

PROGRAM SS;

VAR

     I,J,R,X,N:INTEGER;

    A:ARRAY[0..50] OF INTEGER;

BEGIN

    WRITELN('Введи длину массива');

    READ(N);

    WRITELN('Введи массив');

    FOR I:=1 TO N DO READ(A[I]);

    FOR I:=1 TO N-1 DO

       BEGIN

            R:=I;

            X:=A[I];