gavrik/goit-algo-hw-04

Task1

Для зручності створення набору було використана бібліотека random і за допомогою циклу генерується набір даних заданої довжини.

Для запуску різних методів сортування використовував листі які містять наступну кількість елементів:

• 100
• 1000
• 10000

Також для встановлення часу виконная алгоритму було використано різна кількість повторень:

• 100
• 1000
• 10000

Таким чином ми отримали наступні результати.

--- 100 ---
sorted 100:  0.005488354014232755
merge sort 100:  0.01604384699021466
insertion sort 100:  0.017093519010813907
sorted 1k:  0.04875973201706074
merge sort 1k:  0.1559590180113446
insertion sort 1k:  0.16378373198676854
sorted 10k:  0.4951278299849946
merge sort 10k:  1.5839365730062127
insertion sort 10k:  1.6745387710107025
--- 1000 ---
sorted 100:  0.06062367101549171
merge sort 100:  0.21852757199667394
insertion sort 100:  1.9611723799898755
sorted 1k:  0.5974720329977572
merge sort 1k:  2.3214316590165254
insertion sort 1k:  19.344265755004017
sorted 10k:  5.876803764986107
merge sort 10k:  21.73627353500342
insertion sort 10k:  271.3914908320003
--- 10000 ---
sorted 100:  0.9692907040007412
merge sort 100:  3.5630584970058408
insertion sort 100:  222.15100905799773
sorted 1k:  6.7854557700047735
merge sort 1k:  30.091832017991692
insertion sort 1k:  2214.4334438480146
sorted 10k:  64.22350621598889
merge sort 10k:  272.91889471100876
insertion sort 10k: ..... taking a lot of time .....

Висновки. Як бачимо TimSort алгоритм виконцується майже однаково на різних наборах даних.
insertion sort алгоритм просідає найбільше з ростом кількості елементів в наборі.

Висновки 2. Всі ці алгоритми не використовують всі доступні ресурси системи.
Для подальшої оптимізації плгоритмів потрібно робити шось на кшатлт Map&Reduce, щоб завантажити всі доступні CPU на системі.
Тако ж можна переходити на більш низкій рівень програмування RUST/C++.