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


 

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

27278. Влияние факторов макросреды 25.5 KB
  Внутр: колво штатных ед корпорат культ взаимоотнош внутри коллектива профессионализм сотруд. Внешние: Микросреда штат внутр управл внутр связи партнеры конкуренты Макросреда данные факторы во многом опр потребн в обществе природные вопросы рац использ явл важн элементом побуждения кл к соверш путеш тур бренды разрабат на основе привлекат прир ресурсов демократические расчет числ населения для каждой группы населения треб свой турпродукт эконом платежеспособность населения соцкультурные...
27279. Технология перевозки туристов на ЖД транспорте 23.5 KB
  Единая железнодорожная сеть 2.Вагоны разграничены по классу билеты по категориям пассажиров по возрасту ЖД сеть РФ поделена на жел дороги 17 Перевозки грузов и пассажиров между ж д осуществляться по единому перевозочному документу оформленному по всему пути следования.
27280. Типология и классификация 26.5 KB
  Сущ различные типологии совр отелей: Отельтрадиц тип гост предпр отель люкс гост ср класса гостапартномера кварт типа гост эконом кл мотели отель курортширокий спектр услуг частные гостночлег завтрак отель гарниогран колво услуг апарт отелипредпр из неск квартир пансионпредпр с огран набором усл гост двор бунгалостроение из легких матер ротельпередвиж гост вагон кемпинглагерь авто мото туристов флотелькрупная плав гост флайтельаэрогостиница ботельспец оборуд судно на воде.
27281. Туризм как многогранное явление 26 KB
  Туризм как вид отдыха путешествия Туризм как бизнес транспорт размещение питание развлечение торговые предпр экск бюро музеи турфирмы Туризм как отрасль экономики Туризм как рынок рынок потребителей спрос на турпродукт рынок производителейвысокая конкуренция появление новых видов услуг Турпродукт комплекс услуг по перевозке и размещению оказываемых за общую цену по договору о реализации туристского продукта. Туризм как общественное движение зона предпринимат распределений...
27282. Туристские макрорег мира 30.5 KB
  АзиатскоТихоокеанский Страны Восточной и ЮВ Азии Австралия и Океания 4.Африканский Страны Африки кроме Египта и Ливии 5. Исходя из экономических природных исторических и других предпосылок можно выделить 4 туристских территории: 1ВосточноЕвропейская зона: Польша Центральный Чехия Словакия Венгрия Причерноморский Румыния Болгария 2Зона Северной Европы Скандинавские страны Норвегия Швеция Финляндия Дания 3ЗападноЕвропейская зона Британский Великобритания Ирландия Альпийский Франция Швейцария Австрия...
27283. Факторы регионализма 25 KB
  К факторам регионализма можно отнести: 1.Этнический фактор Этнос исторически возникший вид социальной группировки людей который обладает совокупностью признаков.Демографический фактор демографиянаука которая изучает воспроизводство населения.
27284. Сегментирование. Целевой рынок 24 KB
  Целевой рынок Сегментация рынка заключается в делении рынка на четкие группы покупателей которым следует адресовать разные продукты и разные маркет усилия. Целевой рынок совокупность сущ и потенц покупателей. Стратегия охвата целевого рынка: Недиффер маркет товар рынок организация выходит на рынок с одним продуктомПр. Диффер маркет товар1 рынок1 товар2 рынок2 деят организации на неск сегментахПр.
27286. Цикл обслуживания туриста 26 KB
  Обслуживание во время пребывания Основные услуги Орг прожив гостей питание услуги горничной выдача ключей на ресепшен. Дополнит услуги Услуги бизнесцентра пользование междунар междугор связью копир работы предоставл компьютера переводческие услуги услуги сервисбюро брон билетов орг экс обслуж орг питанияразл подраздел общепита обслуж в номерах орг банкетов орг хран личных вещей камера хранения депозитная ячейка платная эл инд сейфы телекоммуникац услугипобудка услуги платного ТВ анимац услуги Выезд и выписка...