Каталог Индекс раздела
Назад Оглавление Вперед

ЛАБОРАТОРНАЯ РАБОТА #5

Тема: Сортировка

1. Цель работы

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

2. Прорабатываемые темы

Статические структуры данных. Поиск. Сортировка.

3. Постановка задачи

Разработать программу, которая выполняет сортировку набора данных.

4. Варианты индивидуальных заданий

Номер п/п
Задание
Вариант алгоритма сортировки
1
В массиве A[1..n] каждый элемент равен 0, 1 или 2. Отсортировать по возростанию.
1
2
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания.
2
3
Дано N целых чисел. Упорядочить их по возростанию
3
4
Дан одномерный массив целых чисел. Проверить, является ли он упорядоченным по убыванию.
4
5
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по убыванию.
5
6
В массиве A[1..n] каждый элемент изменяется в пределах от 0..20. Отсортировать по возростанию.
6
7
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания.
7
8
Дано N целых чисел от -50 до 50. Упорядочить их по возростанию
8
9
Дан одномерный массив целых чисел > 43. Проверить, является ли он упорядоченным по убыванию.
9
10
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по возростанию.
10
11
В массиве A[1..30] каждый элемент равен 0, 7 или 14. Отсортировать по возростанию.
11
12
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания.
12
13
Дано N целых чисел. Упорядочить их по возростанию
13
14
Дан одномерный массив целых чисел. Проверить, является ли он упорядоченным по убыванию.
14
15
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по убыванию.
15
16
В массиве A[1..n] каждый элемент изменяется в пределах от 0..15. Отсортировать по возростанию.
15
17
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания.
14
18
Дано N целых чисел от 3 до 14. Упорядочить их по возростанию
13
19
Дан одномерный массив целых чисел > 10. Проверить, является ли он упорядоченным по убыванию.
12
20
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по возростанию.
11
21
В массиве A[1..n] каждый элемент равен 5, 7 или 9. Отсортировать по возростанию.
10
22
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания.
9
23
Дано N целых чисел. Упорядочить их по возростанию
8
24
Дан одномерный массив целых чисел. Проверить, является ли он упорядоченным по убыванию.
7
25
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по убыванию.
6
26
В массиве A[1..n] каждый элемент изменяется в пределах от 0..50. Отсортировать по возростанию.
5
27
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания.
4
28
Дано N целых чисел от -100 до 0. Упорядочить их по возростанию
3
29
Дан одномерный массив целых чисел > 0. Проверить, является ли он упорядоченным по убыванию.
2
30
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по возростанию.
1

Номер сортировки по вариантам:

  1. Сортировка обменом
  2. Сортировка выбором
  3. Пузырьковая сортировка
  4. Сортировка включениями
  5. Пузырьковая сортировка вставками.
  6. Быстрая сортировка
  7. Сортировка Шелла
  8. Шейкер-сортировка
  9. Пирамидальная сортировка
  10. Модификация пузырьковой с признаком.
  11. Пузырьковая с запоминанием места последней перестановки.
  12. Модификация простыми вставками.
  13. Турнирная.
  14. Поразрядная цифровая сортировка.
  15. Сортировка Хоара.

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

5.1. Разработка алгоритма решения

Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке.

Цель сортировки - облегчение последующего поиска элементов в отсортированном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах.

Основное требование к методам сортировки массивов - экономное использование памяти. Это означает, что переупорядочивание элементов нужно выполнять на том же месте и что методы, которые пересылают элементы из массива A в массив B, не представляют для нас интереса.

Проблема сортировки неупорядоченного массива относится в вычислительной технике к классическим. Она кажется простой, ведь всем приходилось выполнять какую-либо механическую сортировку, была ли то раскладка игральных карт, гардеробных номерков, карточек из библиотечного каталога или денежных счетов. Простота эта иллюзорна. Хотя первые программы сортировки были написаны фон Нейманом в 1945 г., какого-либо значительного продвижения в теории сортировки не наблюдалось в течение последующих двадцати лет [Грогоно,1982].

5.2. Выбор метода

Сортировка обменом

 Сортировка обменом  - метод, при котором все соседние элементы массива попарно сравниваются друг с другом и меняются местами в том случае, если предшествующий элемент больше последующего. В результате этого максимальный элемент постепенно смещается вправо и в конце концов занимает крайнее правое место в массиве, после чего он исключается из дальнейшей обработки. Затем процесс повторяется и свое место занимает второй по величине элемент, который также исключается из дальнейшего рассмотрения. Так продолжается до тех пор, пока вся последовательность не будет упорядочена. Сортировку обменом называют еще "пузырьковой" (сравнение с всплытием пузырьков воздуха в жидкости).

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

   PROCEDURE BubbleSort (var a: Integer);
        var i,j: Integer;
            f  : Boolean; { Если был обмен, то f=TRUE,  }
                          { если не было обмена f=FALSE }
     BEGIN
        f := TRUE;
        i := N-1;
        While  (i>=1) AND f  do
           begin
              f := FALSE;
              For j:=1 to i  do
                 If  a[j]>a[j+1]  then
                     begin  f := TRUE;
                            Swap (a[j],a[j+1])  
                     end
              i := i-1
           end
     END;  

Необходима также процедура, обеспечивающая обмен местами двух элементов - найденного при i-м просмотре минимального элемента и элемента с индексом i.

   PROCEDURE  Swap (var a,b: Integer);
        var c: Integer;
     BEGIN
        c := a; a := b; b := c
     END;  

Приведем еще одну реализацию алгоритма простого выбора.

   PROGRAM  B_u_b_b_l_e_S_o_r_t (Input,Output);
        const N=8;
        type  index  = 1..N;
              massiv = Array[0..N] of Integer;
        var   x  : Integer;
              a  : massiv;
              i,j: index;
     BEGIN
        For i:=1 to N  do  ReadLn (a[i]);
        For i:=2 to N  do
           For j:=n downto i  do
              If  a[j-1]>a[j]
                 then  begin  x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x  end;
        For i:=1 to N  do  Write (a[i],' ')
     END.  
Сортировка выбором

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

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

а) Минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) другого специально созданного массива, а в старом, исходном, на месте выбранного размещается какое-то очень большое число, превосходящее по величине любой элемент сортируемого массива. Измененный таким образом массив принимается за исходный, и осуществляется следующий просмотр.

б) Минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) заданного массива, а элемент с i-го места - на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т.е. размер каждого последующего обрабатываемого массива на единицу меньше размера предыдущего.

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

   FUNCTION  I_m_i_n (start: Integer; a: tarray): Integer;
     { Ищет минимальный элемент правее start (включая start) }
     { и возвращает его номер                                }
        var m: Integer;
            i: Integer;
     BEGIN
        m := start;
        For i:=start+1 to N  do
           If  a[i]<a[m]  then  m := i;
        I_m_i_n :=m
     END;  

Необходима также процедура, обеспечивающая обмен местами двух элементов - найденного при i-м просмотре минимального элемента и элемента с индексом i.

   PROCEDURE Swap (var a,b: Integer);
        var c: Integer;
     BEGIN
        c := a; a := b; b := c
     END;  

Процедура сортировки выбором имеет вид:

   PROCEDURE sort_choice (var t:array);
        var i: Integer;
     BEGIN
        For i:=1 to N-1  do  Swap (a[I_m_i_n(i,a)],a[i])
     END;  

Приведем еще одну реализацию алгоритма простого выбора.

   PROGRAM  Sort (Input,Output);     { Сортировка простым выбором }
        const  N=8;
        type  index  = 0..N;
              massiv = Array[0..N] of Integer;
         var  x    : Integer;
              a    : massiv;
              i,j,k: index;
     BEGIN
        For i:=1 to N  do readln(a[i]);
        For i:=1 to N-1  do
           begin
              k := i; x := a[i];
              For  j:=i+1 to N  do
                 If  a[j]<x  then  begin  k := j; x := a[j]
                                   end;
                 a[k] := a[i]; a[i] := x
           end;
        For i:=1 to N  do  Write (a[i],' ')
     END.  
Сортировка включениями

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

Для сортировки включениями необходима вспомогательная процедура, которая обеспечивает перемещение элемента с индексом i на место элемента с индексом j и смещение всех элементов с индексами от j до i на одну позицию вправо.

Приведем реализацию алгоритма сортировки включениями на языке Pascal (диалект TURBO Pascal).

   PROGRAM  S_o_r_t (Input,Output);
     { Сортировка простыми включениями }
         const N=8;
         type  index=0..N;
               massiv = Array[0..N] of Integer;
         var   x:   Integer;
               a:   massiv;
               i,j: index;
     BEGIN
        For i:=1 to N  do  ReadLn (a[i]);
        For i:=2 to N  do
           begin
              x := a[i]; a[0] := x; j := i-1;
              While  x<a[j]  do
                   begin  a[j+1] := a[j]; j := j-1  end;
              a[j+1] := x
           end;
        For i:=1 to N  do  Write (a[i],' ')
     END.

       PROGRAM  Sort (Input,Output);
     { Сортировка бинарными включениями }
        const N=8;
        type  index=0..N;
              massiv = Array[0..N] of Integer;
        var   x        : Integer;
              a        : massiv;
              i,j,l,r,m: index;
     BEGIN
        For i:=1 to N  do  Readln (a[i]);
        For i:=2 to N  do
           begin
              x := a[i]; l := 1; r := i-1;
              While  l<=r  do
                 begin
                     m := (l+r) DIV 2;
                     If  x<a[m]  then  r := m-1  else  l := m+1
                 end;
              For j:=i-1 downto l  do  a[j+1] := a[j];
              a[l] := x;
        end;
        For i:=1 to N  do  Write (a[i],' ')
     END.  
Быстрая сортировка (рекурсивный алгоритм)
   PROGRAM  Q_u_i_c_k_S_o_r_t (Input,Output);
        const N = 7;
        type  index  = 0..N;
              massiv = Array [0..N] of Integer;
        var  a: massiv;
             i: index;
    { ------------------------------ }
     PROCEDURE  S_O_R_T (l,r: index);
        var i,j: index;
            x,w: Integer;
     BEGIN
        i := l; j := r; x := a[(l+r) DIV 2];
        Repeat
           While a[i]<x  do  i := i+1;
           While x<a[j]  do  j := j-1;
              If  i<=j
                 then  begin
                          w := a[i]; a[i] := a[j]; a[j] := w; i := i+1; j := j-1
                       end
        until i>j;
        If  l<j  then  S_O_R_T (l,j);
        If  i<r  then  S_O_R_T (i,r)
     END;
    { --- }
     BEGIN
        For i:=1 to N  do  Readln (a[i]);
        S_O_R_T (1,N);
        For i:=1 to N  do  Write (a[i],' ')
     END.  
Быстрая сортировка (нерекурсивный алгоритм)
   PROGRAM  NonRecursiveQuickSort (Input,Output);
     { Обратите внимание на то, что в программе использован тип Record }
         const  N = 8; M = 12;
         type index  = 0..N;
              massiv = Array [0..N] of Integer;
              zapis  = Record
                          L,R: index
                       end;
          var x,w    : Integer;
              a      : massiv;
              i,j,L,R: index;
              s      : 0..M;
              stack  : Array [1..M] of zapis;
     BEGIN
        For  i:=1 to N  do  ReadLn (a[i]);
        s := 1; stack[1].L := 1; stack[s].R := N;
        Repeat
        { Выбор из стека последнего запроса }
           L := stack[s].L; R := stack[s].R; s := s-1;
           Repeat
           { Разделение a[L],...,a[R] }
              i := L; j := R; x := a[(L+R) DIV 2];
              Repeat
                 While  a[i]<x  do  i := i+1;
                 While  x<a[j]  do  j := j-1;
                 If  i<=j
                    then begin
                            w := a[i]; a[i] := a[j]; a[j] := w; i := i+1; j := j-1
                         end;
              until i>j;
              If  i<R
                 then { Запись в стек запроса из правой части }
                 begin
                    s := s+1; stack[s].L := i; stack[s].R := R
                 end;
              R := j {Теперь L и R ограничивают левую часть}
           until L>=R;
        until s=0;
        For  i:=1 to N  do  Write (a[i],' ')
     END.  
Сортировка Шелла (1959)
   PROGRAM  S_h_e_l_l_s_o_r_t (Input,Output);
        const  N = 780;
               t = 4;
        type  Index  = 0..N;
              Massiv = Array [-9..N] of Integer;
              Mas    = Array [1..t] of Integer;
        var   x      : Integer;
              a      : Massiv;
              h      : Mas;
              i,j,k,s: Index;
              m      : 1..t;
              L      : Index;
    { --- }
     BEGIN
        Writeln ('Введите исходный массив...');
        For L:=1 to N  do  begin  a[L] := Random (23); Write (a[L],' ')  end;
        WriteLn;
        h[1] := 9; h[2] := 5; h[3] := 3; h[4] := 1;
        For  m:=t downto 1  do
           begin
              k := h[m]; s := -k; { Место барьера }
              For i:=k+1 to n  do
                 begin
                    x := a[i]; j := i-k;
                    If  s=0  then  s := -k;
                    s := s+1; a[s] := x;
                    While  x<a[j]  do  begin  a[j+k] := a[j]; j := j-k  end;
                    a[j+k] := x
                 end;
           end;
        Writeln ('Результаты сортировки...');
        For L:=1 to N  do
            Write (a[L],' ');
            WriteLn
     END.  
Шейкер-сортировка
   PROGRAM  S_h_a_k_e_S_o_r_t (Input,Output);
        const N=8;
        type  index  = 0..N;
              massiv = Array[0..N] of Integer;
        var   x:         Integer;
              a:         massiv;
              i,j,k,l,r: index;
     BEGIN
        For i:=1 to N do  ReadLn (a[i]);
        l := 2; r := n; k := n;
        Repeat
           For j:=r downto l  do
              If  a[j-1]>a[j]
                 then  begin
                          x := a[j-1]; a[j-1] := a[j]; a[j] := x; k := j
                       end;
           l := k + 1;
           For j:=l to r  do
              If  a[j-1]>a[j]
                 then  begin  x:=a[j-1];a[j-1]:=a[j];a[j]:=x; k:=j  end;
           r := k - 1;
        until l>r;
        For i:=1 to N  do  Write (a[i],' ')
     END.  
Пирамидальная сортировка
   PROGRAM  Heapsort (Input,Output);
        const N=8;
        type  index=0..N;
              massiv = Array[0..N] of Integer;
         var  x:     Integer;
              a:     massiv;
              i,l,r: index;
    { -------------------- }
     PROCEDURE sift;
        label metka;
        var   i,j: index;
     BEGIN
        i := l; j := 2*i; x := a[i];
        While  j<=r  do
           begin
              If  j<r  then  If  a[j]<a[j+1]  then  j := j+1;
              If  x>=a[j]  then  Goto metka;
              a[i] := a[j]; i := j; j := 2*i
           end;
        metka: a[i] := x
     END;
    { --- }
     BEGIN
        For i:=1 to N do  ReadLn (a[i]);
        l := (n DIV 2)+1; r := n;
        While  l>1  do  begin  l := l-1; sift  end;
        While  r>1  do
           begin  x := a[1]; a[1] := a[r]; a[r] := x; r := r-1; sift  end;
        For  i:=1 to N  do  Write (a[i],' ')
     END.  

6. Оформить отчет

В отчет включить:

ПРИЛОЖЕНИЕ

Оценка времени выполнения сортировки

void main()
{ struct time t;
    int t1,t2;
clrscr();
input();
gettime(&t);
t1=t.ti_hund;
sort();
gettime(&t);
t2=t.ti_hund;
printf("\nвремя выполнение сортировки %d секунд \n",t2-t1);
vivod();
getch();
}

Каталог Индекс раздела
Назад Оглавление Вперед