43448

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

Курсовая

Информатика, кибернетика и программирование

Затем нужно подсчитать количество сравнений обменов время работы для каждого случая. Построить таблицу сделать вывод от чего зависит количество обменов сравнений и время работы программы для каждой из сортировок.ЗАДАНИЕ Массив Количество сравнений Количество обменов Время работы Подсчитать количество сравнений обменов время работы для каждого случая.

Русский

2013-11-05

71.5 KB

3 чел.

Министерство образования Российской Федерации

Сибирский государственный технологический университет

Факультет: Автоматизации и информационных технологий

Кафедра: Информационных технологий

Курсовая работа

Тема: «Методы сортировок»

Проверила:

                            Глиценко Е.М.

            (подпись)

                        (оценка, дата)

Разработала:

студентка гр. 21–7

                                 Ларченко А.Н.

                  (подпись)

СОДЕРЖАНИЕ

Реферат……………………………………………………………..3 ст.

Введение………………………………...………………………….4 ст.

1.Задание…………………. ………………………………………..5 ст.

2.Программы сортировок……………………….…………………6-9 ст.

3.Таблицы…………………………………………………………..10 ст.

4.Вывод……………………………………………………………..11-12 ст.

5.Список использованных источников……………………………13 ст.

КР.ИТ.00000.015.П3.

Курсовая работа

литера

лис

листо

Изм

Лист

№ докум

Подпись

Дата

2

13

Разработал

Проверил

Т.Контр

Сиб.Г.Т.У.

Фаит

Гр. 21-7

Н.Контр

Утв.

РЕФЕРАТ

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

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

 

КР.ИТ.00000.015.П3.

Лист

3

Изм

Лист

№ докум.

Подпись

Дата

ВВЕДЕНИЕ

По сортировкам мне достались 3, 7, 13, 17 варианты. Ниже вы увидите примеры их решения и к каждой сортировке своя отдельная таблица, в которую занесены данные о количестве сравнений, обменов (перестановок, вставок) и времени выполнения самой сортировки. Каждая сортировка была протестирована 3 раза согласно заданию.   

КР.ИТ.00000.015.П3.

Лист

4

Изм

Лист

№докум.

Подпись

Дата

1.ЗАДАНИЕ

Массив

Количество сравнений

Количество обменов

Время работы

1..1000

 

 

 

1000..1

 

 

 

Random(1000)

 

 

 

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

3. Шейкер-сортировка (не без метода пузырька). Шейкер-сортировка является модификацией сортировки методом пузырька. Здесь как и в методе пузырька проводят по парное сравнение элементов и обмен в паре, если имеется необходимость, но первый проход осуществляется снизу вверх, второй сверху вниз и т.д. Иными словами меняют направление проходов. Переменная Н указывает направление прохода.

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

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

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

2.ПРОГРАММЫ СОРТИРОВОК

Программа №3.

Program Sortic3;

Uses Crt,dos;

Type

  TVector=array[1..1000] of real;

Var

  a:TVector;

  x: boolean;

  max: real;

  h,m,s,ms,h1,m1,s1,ms1:word;

  i,k,kol,j:Integer;

  c,p:Longint;

begin

  ClrScr;

  Randomize;

  for i:=1 to 1000 do

    a[i]:=random(1000);

  gettime(h,m,s,ms);

  x:=true;  kol:=1000;

  j:=0; k:=1000; p:=0;c:=0;

    repeat

       if x then

         begin

           inc(j);

           inc(p);

           if(a[j]>a[j+1]) then

             while (a[j]>a[j+1])and(j>0) do

               begin

                 max:=a[j];

                 a[j]:=a[j+1];

                 a[j+1]:=max;

                 j:=j-1;

                 inc(c);

               end;

         end

       else

         begin

           dec(k);

           inc(p);

           if(a[k]>a[k+1]) then

             while (a[k]>a[k+1])and(k<kol) do

               begin

                 max:=a[k];

                 a[k]:=a[k+1];

                 a[k+1]:=max;

                 inc(k);

                 inc(c);

               end;

         end;

       x:=not x;

     until (j=kol-1) or (k=1);

  gettime(h1,m1,s1,ms1);

  Writeln('Отсортированный массив:');

  for i:=1 to 1000 do Write (a[i]:8:2);

  Writeln;

  h:=h1-h;

  m:=m1-m;

  s:=s1-s;

  ms:=ms1-ms;

  writeln('Время сортировки ', h,':', m,':', s,':', ms, ' ');

  Writeln;

  writeln('Кол-во сравнений ', p);

  writeln('Кол-во перестановок ', c);

ReadLn;

End.

Программа №7.

Program Sortic7;

Uses Crt,dos;

Type

  TVector=array[1..1000] of real;

Var

  Vector: TVector;

  j: real;

  h,m,s,ms,h1,m1,s1,ms1: word;

  i,k: Integer;

  c,a: Longint;

begin

  ClrScr;

  Randomize;

  For i:=1 to 1000 do

    Vector[i]:=i;

  a:=0;

  c:=0;

  gettime(h,m,s,ms);

  For k:=2 to 1000 do

     begin

        j:=Vector[k-1];

        c:=c+1;

        If j>Vector[k] then

          begin

             Vector[k-1]:=Vector[k];

             Vector[k]:=j;

             k:=k-2;

             a:=a+1;

          end;

     end;

  gettime(h1,m1,s1,ms1);

  Writeln('Отсортированный массив:');

  for i:=1 to 1000 do Write(Vector[i]:8:2);

  Writeln;

  h:=h1-h;

  m:=m1-m;

  s:=s1-s;

  ms:=ms1-ms;

  writeln('Время сортировки ', h,':', m,':', s,':', ms, ' ');

  Writeln;

  writeln('Кол-во сравнений ', c);

  writeln('Кол-во перестановок ', a);

ReadLn;

End.

Программа №13.

Program Sortic13;

Uses Crt,dos;

Type

  TVector=array[1..1000] of real;

Var

  Vector:TVector;

  j   :real;

  h,m,s,ms,h1,m1,s1,ms1:word;

  i,k:Integer;

  c,a:Longint;

begin

  ClrScr;

  Randomize;

  for i:=1 to 1000 do

    Vector[i]:=1000-i;

  a:=0;

  c:=0;

  gettime(h,m,s,ms);

  for i:=1 to 1000 do

    begin

       For k:=i to 999 do

         begin

           j:=Vector[i];

           c:=c+1;

           If j>Vector[k+1] then

             begin

                Vector[i]:=Vector[k+1];

                Vector[k+1]:=j;

                a:=a+1;

             end;

         end;

    end;

  gettime(h1,m1,s1,ms1);

  Writeln('Отсортированный массив:');

  for i:=1 to 1000 do Write (Vector[i]:8:2);

  Writeln;

  h:=h1-h;

  m:=m1-m;

  s:=s1-s;

  ms:=ms1-ms;

  writeln('Время сортировки ', h,':', m,':', s,':', ms, ' ');

  Writeln;

  writeln('Кол-во сравнений ', c);

  writeln('Кол-во перестановок ', a);

ReadLn;

End.

Программа №17.

Program Sortic17;

Uses Crt,dos;

Type

  TVector=array[1..1000] of real;

Var

  Vector: TVector;

  j: real;

  h,m,s,ms,h1,m1,s1,ms1: word;

  i,k,l,p: Integer;

  c,a: Longint;

begin

  ClrScr;

  Randomize;

  For i:=1 to 1000 do

    Vector[i]:=random(1000);

  a:=0;

  c:=0;

  gettime(h,m,s,ms);

  For i:=2 to 1000 do

     begin

        k:=0;

        j:=Vector[i];

        Repeat

            inc(k);

        Until (i<k) or (j<Vector[k]);

        inc(c);

        If k<i then

          begin

             inc(a);

             For p:=i downto k+1 do

                Vector[p]:=Vector[p-1];

             Vector[k]:=j;

          end;

     end;

  gettime(h1,m1,s1,ms1);

  Writeln('Отсортированный массив:');

  for i:=1 to 1000 do Write(Vector[i]:8:2);

  Writeln;

  h:=h1-h;

  m:=m1-m;

  s:=s1-s;

  ms:=ms1-ms;

  writeln('Время сортировки ', h,':', m,':', s,':', ms, ' ');

  Writeln;

  writeln('Кол-во сравнений ', c);

  writeln('Кол-во перестановок ', a);

ReadLn;

End.

3.ТАБЛИЦЫ

Таблица для №3.

Массив

Количество сравнений

Количество обменов

Время работы, мс

1..1000

 1997

 0

 0

1000..1

 251498

 250000

 5

Random(1000)

 190212

 188838

 6

Таблица для №7.

Массив

Количество сравнений

Количество обменов

Время работы, мс

1..1000

 999

0

0

1000..1

 1000001

499501 

11

Random(1000)

 509791

 254396

6

Таблица для №13.

Массив

Количество сравнений

Количество обменов

Время работы, мс

1..1000

 499500

 0

1000..1

 499500

 499500

 5

Random(1000)

 499500

191523 

 5

Таблица для №17.

Массив

Количество сравнений

Количество обменов

Время работы, мс

1..1000

 999

 0

 0

1000..1

 999

 999

 0

Random(1000)

 999

994 

 0

4.ВЫВОД

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

С чем это связано??????

       И так, рассмотрим сортировку №3. Количество обменов зависит от метода тестирования. В первом случае количество обменов равно 0, потому что массив уже упорядочен. Во втором и третьем методе массив не упорядочен и количество обменов равно 250000 и 188838 соответственно.

       Количество сравнений так же зависит от метода. В методе (1..1000) оно равно 1997. В случае (1000..1) количество равно 251498.В третьем случае, когда массив состоит из случайных чисел количество сравнений равно 190212.

       Больше времени затратилось на сортировку случайных чисел (6 мс).

Самое маленькое время (0 мс) программа затратила на сортировку (точнее на сравнение элементов, количество перестановок равно 0) первого метода (1..1000), т.е. упорядоченного массива.

В сортировке №7 количество обменов зависит от метода тестирования. В таблице указано, что при первом тестировании (1..1000) количество обменов равно 0. Так как здесь не нужно ничего упорядочить (в этом варианте элемент массива всегда больше предыдущего). Во втором же тестировании (1000..1) количество обменов равно 499501. В этом случае массив обратно упорядочен (элемент массива всегда меньше предыдущего) и элемент меняется местом с предыдущим, затем возврат на один шаг и снова сравнивают 2 элемента, затем опять возврат … и так до конца массива. В третьем случае (Random(1000))  массив состоит из случайных чисел и количество обменов равно 254396. В этом варианте не все элементы переставляются местами.

Количество сравнений в этой же сортировке также зависит от метода тестирования. В первом методе (1..1000) каждый элемент сравнивается с предыдущим и количество сравнений равно 999. В этом случае нет возврата на один шаг, так как  нет обменов. Во втором же случае (1000..1) количество сравнений равно 1000001. Как я уже говорила, в этом случае каждый элемент меньше предыдущего и поэтому происходит обмен, а затем возврат на один шаг. И так до конца массива. В случае случайных чисел количество сравнений равно 509791. Это количество меньше предыдущего, так как здесь не обязательно, что каждый элемент будет меньше предыдущего.

Время же зависит, как мне кажется, от количества обменов. Чем  больше обменов, тем больше сравнений и тем больше времени  затрачивается на сортировку. В нашем случае самое большое время  затратилось на второй метод (1000..1) в связи с большим количеством обменов. Самое маленькое время (оно равно 0) сортировка затратила на сравнение 1000 упорядоченных элементов. Сортировка затратила на 3 метод (Random(1000)) 6 мс.  

Сортировка №13. Суть сортировки в том, что в массиве находят минимальный элемент и помещают в начало, затем ищут минимальный элемент из оставшихся и помещают на место за предыдущим минимальным. Количество обменов также зависит от метода тестирования. В первом случае количество равно 0, так как массив упорядочен, и его не нужно сортировать. Во втором случае количество обменов равно 499500. Это зависит от того, что массив обратно упорядочен, и необходимо элементы отсортировать.  В случае  случайных чисел количество обменов равно 191523.

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

В этой сортировке время также во всех 3 случаях одинаково. Это зависит, как мне кажется, оттого, что количество сравнений одинаково. Сортировка затрачивает 5 мс. на сравнение 1000 элементов массива не зависимо от его, так сказать, вида.

И, наконец, рассмотрим последнюю сортировку №17. Эта сортировка из самая быстрая из рассмотренных выше. Она  затрачивает самое наименьшее время равное 0 во всех 3 случаях. На мой взгляд, время зависит от количества сравнений, так как количество сравнений так же одинаково в 3 случаях и оно равно 999. Количество сравнений не зависит от того, какой массив. Просто берется элемент из данного массива и помещается в нужное место отсортированной части массива.

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

На мой взгляд, 17 сортировка, так сказать, лучше предыдущих (3,7,13). Программа затрачивает мало времени во всех трех случаях. Количество обмена и количество сравнений так же наименьшие из всех рассмотренных.  

5. ИСПОЛЬЗОВАННЫЕ ИСТЧНИКИ

1.Электронный справочник по информатике.

2.”Turbo Pascal”, О.А. Меженный

      “Диалектика” г. Москва, 2001 год


 

А также другие работы, которые могут Вас заинтересовать

47880. Загальна патологія 135.5 KB
  Павлова про розвиток хвороби та його основні положення. Наука яка вивчає закономірності виникнення розвитку і кінця хвороби або іншими словами вивчає життєдіяльність хворого організму називається патологічною фізіологією. Перша частина нозологія або загальне вчення про хвороби. При аналізі хвороби виникає два запитання: чому виникла хвороба і як вона розвивається.
47881. Судова, правоохоронна та правозахисна діяльність 271 KB
  Поняття правоохоронного органу та правоохоронної діяльності Поняття правоохоронного органу. Під правоохоронним органом розуміють державну установу або державну юридичну особу яка діє в системі органів влади й виконує на основі закону державні функції владні організаційнорозпорядчі контрольноперевірочні тощо в різних сферах внутрішньої та зовнішньої діяльності Української держави. За законом до правоохоронного органу належить такий державний орган предмет діяльності якого законодавче зафіксовано як його завдання або функції саме...
47882. ГОСПОДАРСЬКІ РІШЕННЯ У РІЗНИХ СФЕРАХ ПІДПРИЄМНИЦЬКОЇ ДІЯЛЬНОСТІ 814 KB
  Сутнісна характеристика господарських рішень План: Господарські рішення та їх види Способи формалізації та реалізації господарських рішень Якість і ефективність господарських рішень Доповідь: Особливості управління ризиками господарської діяльності Л1Ст. ГОСПОДАРСЬКІ РІШЕННЯ ТА ЇХ ВИДИ Від прийняття господарських рішень їх якості раціональності й обґрунтованості в багатьох випадках залежать реальні можливості досягнення цілей організації її ефективна діяльність....
47884. Субєкти правової роботи на підприємствах, в установах, організаціях 266.5 KB
  Правова робота в нових ринкових нестабільних відносинах стає невід'ємною виробничою частиною діяльності юридичних осіб незалежно від форм власності і господарювання
47885. Методологія наукового пізнання та журналістика 149.5 KB
  Специфіка об’єкта пізнання в журналістиці. Схеми пізнання об’єкта. Специфіка об’єкта пізнання в журналістиці. Схеми пізнання об’єкта.
47886. Барокко. Архітектура. Скульптура. Живопис 519 KB
  Мета завдання лекції Метою викладання теоретичного курсу є знайомство з основними теоретичними поняттями мистецтвознавства особливостями історичних етапів світової образотворчості декоративноужиткового мистецтва та архітектури пам’ятками світової культури допоможе студентам оволодіти належним рівнем методичної готовності до професійної діяльності виховати високий рівень художньоестетичного смаку креативний підхід у поєднанні традицій та новацій у професійній діяльності. засвоєння історії образотворчого декоративноужиткового...
47887. Міждисциплінарні методи в журналістиці 502 KB
  Міждисциплінарні методи в журналістиці Міждисциплінарні методи в журналістиці Логіка викладу Вступ. Методи історії: метод повної історичної реконструкції метод часткової історичної реконструкції порівняльноісторичний метод метод архівного дослідження. Біографічний та автобіографічний метод як важливе джерело відомостей про особу у роботі журналіста.