Q04.6. (*) Adaptability due to sub-algorithms.

[Balukova]

*Q04.6. () Adaptability due to sub-algorithms.**

• Implement a recursive sorting algorithm quicksort or merge sort for small sub-array sizes use one of the quadratic algorithms (insertion, selection, bubble,...)

• Check whether this will accelerate the overall algorithms and how much

• Pick up experimentally the optimal threshold values for the transition to the quadratic algorithm

• Consider adaptive and nonadaptive implementations of the quadratic algorithm and compare their performance for those arrays where adaptability is preferred. Determine the effect of the adaptability of the quadratic sub-algorithm on the running time of the algorithm as a whole

• This task is more difficult, but it will score more points. Can be performed in commands. You can implement different combinations of algorithms, in different programming languages,,

*Q04.6. () Адаптивність за рахунок під-алгоритмів**

• Реалізувати рекурсивний алгоритм сортування quicksort або merge sort, причому для маленьких розмірів під-масивів використовувати один з квадратичних алгоритмів (insertion, selection, bubble, …)

• Перевірити, чи буде від цього прискорення загального алгоритму, і на скільки

• Підібрати експериментально оптимальні значення порогу для переходу до квадратичного алгоритму

• Розглянути адаптивні та неадаптивні реалізації квадратичного алгоритму і порівняти їх роботу для тих масивів, де адаптивність дає перевагу. Визначити, який вплив має адаптивність квадратичного під-алгоритму на час роботи алгоритму в цілому

• Це завдання є більш складним, але за нього буде більше балів. Можна виконувати в командах. Можна реалізовувати різні комбінації алгоритмів, на різних мовах програмування, …

[PickDough]

Для цього завдання я обрав QuickSort та MergeSort для перевірки їх роботи з адаптивними квадратичними алгоритмами та без. Щодо самих квадаратичних алгоритмів, то мною були обрані InsertionSort та SelectionSort. Тестування відбувалось на мові Python і я старавя виконати його з урахуванням ООП підходу, тому є 4 класи алгоритмів сортування з статичними методати та два класи тестування для парних та одинарних випадків. З усім кодом можна ознайомитись за цим посиланням

Тепер перейдемо до тестування :) Ось час, який був необхідний для алгоритмів, коли вони працювали самі по собі: Я не запускав Selection та Insertion для розмірів більших за 10_000, оскільки очевидно, що це зайняло б багато часу.

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

Щодо пошуку найоптимальнішого числа для переходу, то було проведено перевірку для всіх пар з QuickSort та окремо всіх пар MergeSort і з них обрано середній для проміжку числе [6, 12]

Нарешті, я провів порівняльне тестування з та без використання адаптивного підходу:

Який з цього можна зрбити висновок? Якщо подивитись на останні скріншоти, то можна побачити, що виграш в часі адаптивного підходу присутній, порівняно з використанням лише nlogn алгоритмів, але на перший погляд важко сказати, що він надто суттєвий, проте можна також помітити, що зі збільшенням розміру масиву цей виграш у часі також збільшується. Ось приблизний виграш у часі у %, у MergeSort він доволі великий через виграш у невеликих масивах.

Отже, адаптивний підхід до сортування масивів може відчутно зекономити час на великих дистанціях.

[bastikk]

Для реалізація цього завдання мною було вирішено використати сортування вставкою для невеликих масивів та швидке сортування для масивів значних розмірів. Для цього я реалізував дані алгоритми: `def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr

def quickSort(massive): if len(massive) < 2: return massive middle = massive[0] less = [i for i in massive[1:] if i <= middle] more = [i for i in massive[1:] if i > middle] return quickSort(less) + [middle] + quickSort(more)`

Далі переді мною постало завдання визначити розмір масиву до якого слід застосовувати сортування вставкою, а після якого слід використовувати швидке сортування. Визначення цього числа проводилося експериментальним шляхом. Для точності створювалося 10 масивів рандомно заповнені n елементами. Далі ви можете побачити заміри часу. Було вирішено зупинитися на числі 650, адже саме при такому розмірі массива, вид сортування майже не грає роль. 10:

100:

1000:

650:

Після визначення даного числа ми створили функцію адаптивного алгоритма. def adaptiveSort(): start_time = datetime.now() for arr in arrays: if len(arr)>650: quickSort(arr) else: insertionSort(arr) print("AdaptiveSort used:", datetime.now() - start_time)

Для замір часу було створено 10 масивів розміром від 1 до 1000 елементів. Нижче ви можете побачити результати, з яких можна зробити вивід, що адаптивний алгоритм працює ефективніше ніж алгоритм сортування вставкою чи швидке сортування.

Нижче ви можете ознайомитися з повним кодом програми. `import random from datetime import datetime import sys

sys.setrecursionlimit(50000)

def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr

def quickSort(massive): if len(massive) < 2: return massive middle = massive[0] less = [i for i in massive[1:] if i <= middle] more = [i for i in massive[1:] if i > middle] return quickSort(less) + [middle] + quickSort(more)

arrays = [] for i in range(10): arr = [] for j in range(random.randint(0, 1000)): arr.append(random.randint(0, 100000000000)) arrays.append(arr)

start_time = datetime.now() for arr in arrays: insertionSort(arr) print("InsertionSort used:", datetime.now() - start_time)

start_time = datetime.now() for arr in arrays: quickSort(arr) print("QuickSort used:", datetime.now() - start_time)

def adaptiveSort(): start_time = datetime.now() for arr in arrays: if len(arr)>650: quickSort(arr) else: insertionSort(arr) print("AdaptiveSort used:", datetime.now() - start_time)

adaptiveSort() `