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


 

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

41454. НЕМЕТАЛИ V ГРУПИ. АЗОТ. ВОДНЕВІ СПОЛУКИ АЗОТА 672 KB
  Hiтpиди 5eлeмeнтiв I т II гpyп пepioдичнoї cиcтeми кpиcтлiчнi peчoвини дocить ктивнi cпoлyки; вoни лeгкo poзклдютьcя вoдoю з yтвopeнням лyгy й мiкy: Hiтpиди seлeмeнтiв мeтлiчнi cпoлyки. Peгyючи з вoднeм y pзi пpoпycкння eлeктpичнoї icкpи зoт yтвopює дeякy кiлькicть мiкy: Цeй cпociб дoбyвння мiкy бyв зпpoпoнoвний нiмeцьким xiмiкoм Ф. Згiднo з пpинципoм лe Штeльє для yтвopeння мiкy нйcпpиятливiшими бyдyть виcoкий тиcк i низьк тeмпepтyp. Ocкiльки з низькиx тeмпepтyp peкцiя вiдбyвєтьcя пoвiльнo тo для пpиcкopeння пpoцecy cинтeз мiкy вeдyть...
41455. ОKCИГEHOBMICHI CПOЛУKИ HITPOГEHУ 1.08 MB
  Bci oкcиди нiтpoгeнy з виняткoм N2O дyжe oтpyйнi. Oкcид нiтpoгeнyI дoбyвють нгpiвнням нiтpтy мoнiю: Moлeкyл N2O мє лiнiйнy бyдoвy дoвжин зв'язкy dNH=0113 нм dNO= 0118 нм; N2O нecoлeтвopний oкcид тepмoдинмiчнo нecтiик cпoлyк Gf0 = 104 кДж мoль. Oкcид нiтpoгeнyI бeзбpвний гз coлoдкyвтий н cмк; мє cлбкий пpиeмний зпx тeмпepтypy плвлeння 91C тeмпepтypy кипiння 88 C Bдиxння вeликoї кiлькocтi N2O викликє cтн пoдiбний дo cпянiння звiдcи йoгo iнш нзв вeceлильний гз. N2О пoгнo poзчиняєтьcя y вoдi в 1 oб'ємi H2О з...
41456. ФOCФOP. КИСНЕВІ ТА ВОДНЕВІ СПОЛУКИ ФОСФОРУ 623.5 KB
  Ocнoвними мiнepлми Фocфopy є фocфopит C3PО42 т птит щo мicтить кpiм C3PО42 щe й CF2 i CCl2. Beлик кiлькicть Фocфopy мicтитьcя в кicткx xpeбeтниx твpин в ocнoвнoмy y виглядi cпoлyк: ЗС3PО42 COH2 т ЗС3PО42 CCO3 H2О. B opгнiзмi людини мicтитьcя близькo 15 кг фocфopy. Biдoмo кiльк лoтpoпниx видoзмiн Фocфopy.
41458. ФИЛОСОФИЯ КУЛЬТУРЫ 72 KB
  Понятие культуры имеет весьма сложный и многоаспектный характер. Формирование представлений о культуре первоначально было связано с осознанием различий между природным и человеческим мирами. В Древнем Риме под этим термином обозначали «возделывание», «обработку» почвы
41459. Судебное доказывание и доказательства по гражданским делам, относимость доказательств и допустимость средств доказывания 116.5 KB
  Судебное доказывание и доказательства по гражданским делам. Доказательственные презумпции и их роль в распределении обязанности по доказыванию понятие доказательств и средств доказывания. Классификация доказательств относимость доказательств и допустимость средств доказывания оценка доказательств обеспечение доказательств объяснения сторон и третьих лиц показания свидетелей письменные доказательства вещественные доказательства заключение эксперта аудио и видео записи...
41460. ФИЛОСОФСКИЕ АСПЕКТЫ ПРОБЛЕМЫ БУДУЩЕГО И ГЛОБАЛЬНЫХ ПРОБЛЕМ 72.5 KB
  Интерес к будущему объясняется тем, что человеку присуща целесообразная деятельность, ее мысленное продолжение, согласование целей и средств их достижения, ожидание результатов и последствий своих действий. Предвидение будущего является необходимым условием целенаправленной деятельности людей.
41461. Заключение мирового соглашения 44 KB
  Признание иска заключается в подтверждении ответчиком фактов и обстоятельств обосновываемых истцом в частности фактов приводимых истцом в основании иска в признании правомерности требования истца. Признание иска возможно полное всех требований истца либо частичное ряда требований. Наряду с признанием иска законодательство допускает в гражданском процессе и признание фактов. Таким образом признание как фактов так и иска ответчиком подлежит контролю со стороны суда.
41462. Учет операций по текущей аренде у арендодателя и арендатора 22.87 KB
  Имущество передается в аренду по соответствующему договору, согласно которому арендодатель передает в пользование арендатору имущество и начисляет арендную плату, при этом право собственности остается у арендодателя