Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Дослідження швидкості сортування масиву (табличний варіант)





 

Практична частина полягає у наступному:

1. Створюємо довільні масиви

2. Сортуємо їх двома різними способами

3. Під час сортування рахуємо кількість проходів по циклам та час сортування

4. Порівнюємо кількість проходів одним та другим способом

 

Кількість елементів масиву Особливості масиву Quicksort Bubble
Час виконання (c) Кількість порівнянь Час виконання (c) Кількість порівнянь
  Довільні числа     0.006  
  Довільні числа     0.006  
  Довільні числа     0.006  
  Довільні числа     0.007  
  Довільні числа     0.006  
  Довільні числа     0.006  
  Довільні числа     0.006  
  Довільні числа     0.005  
  Довільні числа     0.005  
  Довільні числа     0.007  
  Довільні числа     0.01  
  Довільні числа 0.001   0.016  
  Довільні числа 0.001   0.024  
  Довільні числа 0.001   0.122  
  Довільні числа 0.003   0.466  
  Довільні числа 0.005      
  Довільні числа 0.007   1.804  
  Довільні числа 0.01   2.71  
  Довільні числа 0.015   6.333  
  Довільні числа 0.02   10.984  
  Довільні числа 0.043   43.012  
  Довільні числа 0.069   98.719  
  Довільні числа 0.121   276.11  
  Відсортований масив     0.006  
  Відсортований масив     0.007  
  Відсортований масив     0.005  
  Відсортований масив     0.003  
  Відсортований масив 0.001   0.005  
  Відсортований масив 0.001   0.008  
  Відсортований масив 0.001   0.004  
  Відсортований масив 0.002   0.003  
  Відсортований масив 0.002   0.006  
  Відсортований масив 0.002   0.01  
  Відсортований масив 0.003   0.08  
  Відсортований масив 0.004   0.08  
  Масив спадаючий     0.004  
  Масив спадаючий 0.001   0.006  
Кількість елементів масиву Особливості масиву Quicksort Bubble
Час виконання (c) Кількість порівнянь Час виконання (c) Кількість порівнянь
  Масив спадаючий     0.016  
  Масив спадаючий     0.058  
  Масив спадаючий 0.001   0.212  
  Масив спадаючий 0.001   1.307  
  Масив спадаючий 0.003   4.96  
  Масив спадаючий 0.003   7.205  
  Масив спадаючий 0.004   9.95  
  Масив спадаючий 0.006   20.198  
               

 

Дослідження швидкості сортування масиву (графічний варіант)

 

Quickosort

Залежність часу виконання від кількості елементів у масиві. Довільний масив.

Залежність кількості порівнянь від кількості елементів у масиві. Довільний масив.

 

Залежність кількості порівнянь від кількості елементів у масиві. Відсортований масив.

Залежність часу роботи від кількості елементів у масиві. Спадаючий масив.

Залежність кількості порівнянь від кількості елементів у масиві. Спадаючий масив.

Сортування «бульбашкою»

Залежність часу порівнянь від кількості елементів у масиві. Довільний масив.

 

Залежність кількості порівнянь від кількості елементів у масиві. Довільний масив.

 

Залежність кількості порівнянь від кількості елементів у масиві. Спадаючий масив.

 

Залежність часу роботи від кількості елементів у масиві. Спадаючий масив.

Висновок

 

Проаналізувавши пророблену роботу, можна прийти до наступних висновків:

1. Алгоритм швидкого сортування є значно ефективнішим за алгоритм сортування «бульбашкою» і у швидкості роботи і у кількості порівнянь елементів. Найгірший варіант роботи цього алгоритму це той, коли, поділивши масив на дві частини, в одній буде 0 елементів, а в іншій n-1. Найкращим варіантом є той, коли масив поділений рівно на дві частини.

2. Алгоритм сортування «бульбашкою» є дуже ефективним лише у тому, єдиному, випадку, коли масив відсортований. Тоді кількість проходів по циклу рівне одному і час роботи є дуже швидким. В усіх інших випадках алгоритм працює дуже повільно. Можна навести приклад, что для сортування масиву з 50000 елементів алгоритм Quicksort витратив 0.121 секунду часу та приблизно 250 тисяч проходів, а алгоритм «бульбашкового» сортування 276 секунд та більше, ніж 600 мільйонів проходів по циклу.

Список використаної літератури

 

1. Седжвік Р. Фундаментальні алгоритми на С++ — Київ, 2001. — 299-330 с.

2. http://uk.wikipedia.org/wiki/Алгоритм_сортування







Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.