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 год


 

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

45750. Гегель. Наука Логики 27.5 KB
  Наука Логики. В этом смысле наука логики есть изложение самой Абсолютной Идеи в ее необходимом развертывании. Именно в этом смысле Наука логики является фундаментом всей системы гегелевской философии. Следует заметить что Наука логики не опровергает формальную логику но по замыслу Гегеля развивает понимание логического до уровня спекулятивного.
45751. Гегель. Кто мыслит абстрактно? 31.5 KB
  Кто мыслит абстрактно в ней речь идетде о метафизике. доказывается что какие бы то ни было объяснения на этот счет совершенно излишни: именно потому что свет прекрасно знает что такое абстрактное он его и избегает. в добропорядочном обществе каждый из присутствующих прекрасно знает что значит мыслить и что такое абстрактно а именно в таком обществе мы и находимся. Вопрос стало быть заключается только в том чтобы показать на того кто мыслит абстрактно.
45752. Гуссерль. Картезианские размышления 40 KB
  Феноменология определяется в данной работе Гуссерля как самоистолкование трансцендентального ego показывающее как оно конституирует в себе трансцендентное; как трансцендентальный идеализм трансцендентальная теория познания в отличие от традиционной где основной проблемой является проблема трансцендентного бессмысленная в феноменологии. Трансцендентальнофеноменологическая редукция эпохé делая мир лишь опытом феноменом обнаруживает что естественному бытию мира в качестве самого по себе более первичного бытия предшествует бытие...
45754. Критика способности суждения 24.5 KB
  Критика способности суждения нем. Кант также замечает что эстетическое не исчерпывается прекрасным нем. Помимо него существует возвышенное нем.
45755. Критика чистого разума 32.5 KB
  Кант начинает свои рассуждения со специфической классификации суждений. Он выделяет суждения синтетическиеаналитические и априорныеапостериорные.Синтетическими называются суждения несущие новое знание не содержащееся в понятии которое является их субъектом.Аналитическими называются суждения которые всего лишь раскрывают свойства присущие понятию субъекта содержащиеся в нём самом и не несут нового знания.
45756. Кун. Структуры научных революций 28.5 KB
  сформулировал новую концепцию развития науки и научного знания которая произвела настоящий переворот во всей философии науки. Внутри парадигмы существование науки определяется Куном как нормальная наука; ученые еще не подвергают сомнению свою научную деятельность которая состоит в вписывании фактов в уже существующую теорию. Прогресс имеет место только внутри нормальной науки.Периоду нормальной науки Кун противопоставляет деятельность ученых в рамках кризиса то есть период экстраординарной науки причем если целью нормальной науки...
45757. Лейбниц. Об основных аксиомах познания 31 KB
  Если чтото отрицается как истинное то очевидно оно является ложным; а если чтото отрицается как ложное то оно является истинным. Подобным же образом если истинно то что нечто ложно или ложно то что нечто истинно то утверждение является ложным; а если истинно то что нечто истинно и лоншо то что нечто ложпо то оно является истинным. С другой стороны среди истинных предложений первыми являются те которые обычно называют тождественными как А есть Л Не А есть не А Если истинно предложение L то следовательно истинно...
45758. Лейбниц. Монадология 53.5 KB
  Согласно Лейбницу основаниями существующих явлений или феноменов служат простые субстанции или монады. Все монады просты и не содержат частей. Монады не могут претерпеть изменения в своём внутреннем состоянии от действия какихлибо внешних причин кроме Бога. Монада способна к изменению своего состояния и все естественные изменения монады исходят из её внутреннего принципа.