Добре відомо, що сортування злиттям працює швидше, ніж сортування вставкою. Використання асимптотичний аналіз . ми можемо довести, що сортування злиттям виконується за O(nlogn) часу, а сортування вставкою займає O(n^2). Це очевидно, оскільки сортування злиттям використовує підхід «розділяй і володарюй», рекурсивно вирішуючи проблеми, де сортування вставкою слідує інкрементальному підходу. Якщо ми детальніше розглянемо аналіз складності часу, то зрозуміємо, що сортування вставкою не таке вже й погане. На диво сортування вставкою перевершує сортування злиттям на меншому розмірі вхідних даних. Це пояснюється тим, що є кілька констант, які ми ігноруємо, виводячи часову складність. На більших розмірах вхідних даних порядку 10^4 це не впливає на поведінку нашої функції. Але коли розміри вхідних даних падають нижче, скажімо, менше 40, тоді константи в рівнянні домінують над розміром вхідних даних «n». Поки що добре. Але мене не влаштовував такий математичний аналіз. Як студенти інформатики ми повинні вірити в написання коду. Я написав програму на C, щоб відчути, як алгоритми конкурують один з одним за різні розміри вхідних даних. А також чому проводиться такий ретельний математичний аналіз для встановлення складності часу роботи цих алгоритмів сортування.
псевдокод java
Реалізація:
CPP#include
import java.util.Scanner; import java.util.Arrays; import java.util.Random; public class SortingAlgorithms { // Maximum element in array static final int MAX_ELEMENT_IN_ARRAY = 1000000001; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); for (int i = 0; i < t; i++) { int size = scanner.nextInt(); int num_of_times = scanner.nextInt(); testSortingRuntimes(size num_of_times); } scanner.close(); } static int[] generateRandomArray(int n) { // Generate an array of n random integers. int[] arr = new int[n]; Random random = new Random(); for (int i = 0; i < n; i++) { arr[i] = random.nextInt(MAX_ELEMENT_IN_ARRAY); } return arr; } static void insertionSortAsc(int[] a int start int end) { // Perform an in-place insertion sort on a from start to end. for (int i = start + 1; i <= end; i++) { int key = a[i]; int j = i - 1; while (j >= start && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } } static void merge(int[] a int start int end int mid) { // Merge two sorted sublists of a. // The first sublist is a[start:mid+1] and the second sublist is a[mid+1:end+1]. int[] aux = new int[end - start + 1]; int i = start j = mid + 1 k = 0; while (i <= mid && j <= end) { if (a[i] <= a[j]) { aux[k++] = a[i++]; } else { aux[k++] = a[j++]; } } while (i <= mid) { aux[k++] = a[i++]; } while (j <= end) { aux[k++] = a[j++]; } System.arraycopy(aux 0 a start aux.length); } static void mergeSort(int[] a) { // Perform an in-place merge sort on a. mergeSortHelper(a 0 a.length - 1); } static void mergeSortHelper(int[] a int start int end) { // Recursive merge sort function. if (start < end) { int mid = start + (end - start) / 2; mergeSortHelper(a start mid); mergeSortHelper(a mid + 1 end); merge(a start end mid); } } static void insertionAndMergeSortCombine(int[] a int start int end int k) { /* Perform an in-place sort on a from start to end. If the size of the list is less than or equal to k use insertion sort. Otherwise use merge sort. */ if (start < end) { int size = end - start + 1; if (size <= k) { insertionSortAsc(a start end); } else { int mid = start + (end - start) / 2; insertionAndMergeSortCombine(a start mid k); insertionAndMergeSortCombine(a mid + 1 end k); merge(a start end mid); } } } static void testSortingRuntimes(int size int num_of_times) { // Test the runtime of the sorting algorithms. double insertionSortTime = 0; double mergeSortTime = 0; double mergeSortAndInsertionSortMixTime = 0; double qsortTime = 0; for (int i = 0; i < num_of_times; i++) { int[] a = generateRandomArray(size); int[] b = Arrays.copyOf(a a.length); long start = System.currentTimeMillis(); insertionSortAsc(b 0 b.length - 1); long end = System.currentTimeMillis(); insertionSortTime += end - start; int[] c = Arrays.copyOf(a a.length); start = System.currentTimeMillis(); mergeSort(c); end = System.currentTimeMillis(); mergeSortTime += end - start; int[] d = Arrays.copyOf(a a.length); start = System.currentTimeMillis(); insertionAndMergeSortCombine(d 0 d.length - 1 40); end = System.currentTimeMillis(); mergeSortAndInsertionSortMixTime += end - start; int[] e = Arrays.copyOf(a a.length); start = System.currentTimeMillis(); Arrays.sort(e); end = System.currentTimeMillis(); qsortTime += end - start; } insertionSortTime /= num_of_times; mergeSortTime /= num_of_times; mergeSortAndInsertionSortMixTime /= num_of_times; qsortTime /= num_of_times; System.out.println('nTime taken to sort:n' + '(i) Insertion sort: ' + insertionSortTime + 'n' + '(ii) Merge sort: ' + mergeSortTime + 'n' + '(iii) Insertion-mergesort-hybrid: ' + mergeSortAndInsertionSortMixTime + 'n' + '(iv) Qsort library function: ' + qsortTime + 'n'); } }
import time import random import copy from typing import List # Maximum element in array MAX_ELEMENT_IN_ARRAY = 1000000001 def generate_random_array(n: int) -> List[int]: #Generate a list of n random integers. return [random.randint(0 MAX_ELEMENT_IN_ARRAY) for _ in range(n)] def insertion_sort_asc(a: List[int] start: int end: int) -> None: #Perform an in-place insertion sort on a from start to end. for i in range(start + 1 end + 1): key = a[i] j = i - 1 while j >= start and a[j] > key: a[j + 1] = a[j] j -= 1 a[j + 1] = key def merge(a: List[int] start: int end: int mid: int) -> None: #Merge two sorted sublists of a. #The first sublist is a[start:mid+1] and the second sublist is a[mid+1:end+1]. aux = [] i = start j = mid + 1 while i <= mid and j <= end: if a[i] <= a[j]: aux.append(a[i]) i += 1 else: aux.append(a[j]) j += 1 while i <= mid: aux.append(a[i]) i += 1 while j <= end: aux.append(a[j]) j += 1 a[start:end+1] = aux def _merge_sort(a: List[int] start: int end: int) -> None: #Recursive merge sort function. if start < end: mid = start + (end - start) // 2 _merge_sort(a start mid) _merge_sort(a mid + 1 end) merge(a start end mid) def merge_sort(a: List[int]) -> None: #Perform an in-place merge sort on a. _merge_sort(a 0 len(a) - 1) def insertion_and_merge_sort_combine(a: List[int] start: int end: int k: int) -> None: ''' Perform an in-place sort on a from start to end. If the size of the list is less than or equal to k use insertion sort. Otherwise use merge sort. ''' if start < end: size = end - start + 1 if size <= k: insertion_sort_asc(a start end) else: mid = start + (end - start) // 2 insertion_and_merge_sort_combine(a start mid k) insertion_and_merge_sort_combine(a mid + 1 end k) merge(a start end mid) def test_sorting_runtimes(size: int num_of_times: int) -> None: #Test the runtime of the sorting algorithms. insertion_sort_time = 0 merge_sort_time = 0 merge_sort_and_insertion_sort_mix_time = 0 qsort_time = 0 for _ in range(num_of_times): a = generate_random_array(size) b = copy.deepcopy(a) start = time.time() insertion_sort_asc(b 0 len(b) - 1) end = time.time() insertion_sort_time += end - start c = copy.deepcopy(a) start = time.time() merge_sort(c) end = time.time() merge_sort_time += end - start d = copy.deepcopy(a) start = time.time() insertion_and_merge_sort_combine(d 0 len(d) - 1 40) end = time.time() merge_sort_and_insertion_sort_mix_time += end - start start = time.time() a.sort() end = time.time() qsort_time += end - start insertion_sort_time /= num_of_times merge_sort_time /= num_of_times merge_sort_and_insertion_sort_mix_time /= num_of_times qsort_time /= num_of_times print(f'nTime taken to sort:n' f'(i)Insertion sort: {insertion_sort_time}n' f'(ii)Merge sort: {merge_sort_time}n' f'(iii)Insertion-mergesort-hybrid: {merge_sort_and_insertion_sort_mix_time}n' f'(iv)Qsort library function: {qsort_time}n') def main() -> None: t = int(input()) for _ in range(t): size num_of_times = map(int input().split()) test_sorting_runtimes(size num_of_times) if __name__ == '__main__': main()
// Importing required modules const { performance } = require('perf_hooks'); // Maximum element in array const MAX_ELEMENT_IN_ARRAY = 1000000001; // Function to generate a list of n random integers function generateRandomArray(n) { return Array.from({length: n} () => Math.floor(Math.random() * MAX_ELEMENT_IN_ARRAY)); } // Function to perform an in-place insertion sort on a from start to end function insertionSortAsc(a start end) { for (let i = start + 1; i <= end; i++) { let key = a[i]; let j = i - 1; while (j >= start && a[j] > key) { a[j + 1] = a[j]; j -= 1; } a[j + 1] = key; } } // Function to merge two sorted sublists of a function merge(a start end mid) { let aux = []; let i = start; let j = mid + 1; while (i <= mid && j <= end) { if (a[i] <= a[j]) { aux.push(a[i]); i += 1; } else { aux.push(a[j]); j += 1; } } while (i <= mid) { aux.push(a[i]); i += 1; } while (j <= end) { aux.push(a[j]); j += 1; } for (let i = start; i <= end; i++) { a[i] = aux[i - start]; } } // Recursive merge sort function function _mergeSort(a start end) { if (start < end) { let mid = start + Math.floor((end - start) / 2); _mergeSort(a start mid); _mergeSort(a mid + 1 end); merge(a start end mid); } } // Function to perform an in-place merge sort on a function mergeSort(a) { _mergeSort(a 0 a.length - 1); } // Function to perform an in-place sort on a from start to end function insertionAndMergeSortCombine(a start end k) { if (start < end) { let size = end - start + 1; if (size <= k) { insertionSortAsc(a start end); } else { let mid = start + Math.floor((end - start) / 2); insertionAndMergeSortCombine(a start mid k); insertionAndMergeSortCombine(a mid + 1 end k); merge(a start end mid); } } } // Function to test the runtime of the sorting algorithms function testSortingRuntimes(size numOfTimes) { let insertionSortTime = 0; let mergeSortTime = 0; let mergeSortAndInsertionSortMixTime = 0; let qsortTime = 0; for (let _ = 0; _ < numOfTimes; _++) { let a = generateRandomArray(size); let b = [...a]; let start = performance.now(); insertionSortAsc(b 0 b.length - 1); let end = performance.now(); insertionSortTime += end - start; let c = [...a]; start = performance.now(); mergeSort(c); end = performance.now(); mergeSortTime += end - start; let d = [...a]; start = performance.now(); insertionAndMergeSortCombine(d 0 d.length - 1 40); end = performance.now(); mergeSortAndInsertionSortMixTime += end - start; start = performance.now(); a.sort((a b) => a - b); end = performance.now(); qsortTime += end - start; } insertionSortTime /= numOfTimes; mergeSortTime /= numOfTimes; mergeSortAndInsertionSortMixTime /= numOfTimes; qsortTime /= numOfTimes; console.log(`nTime taken to sort:n(i)Insertion sort: ${insertionSortTime}n(ii)Merge sort: ${mergeSortTime}n(iii)Insertion-mergesort-hybrid: ${mergeSortAndInsertionSortMixTime}n(iv)Qsort library function: ${qsortTime}n`); } // Main function function main() { let t = parseInt(prompt('Enter the number of test cases: ')); for (let _ = 0; _ < t; _++) { let size = parseInt(prompt('Enter the size of the array: ')); let numOfTimes = parseInt(prompt('Enter the number of times to run the test: ')); testSortingRuntimes(size numOfTimes); } } // Call the main function main();
Я порівняв час роботи наступних алгоритмів:
довго нанизувати
- Сортування вставкою : Традиційний алгоритм без модифікацій/оптимізації. Він дуже добре працює для менших розмірів вхідних даних. І так, він перевершує сортування злиттям
- Йде доля : Дотримується підходу «розділяй і володарюй». Для вхідних розмірів порядку 10^5 цей алгоритм є правильним вибором. Це робить сортування вставлення непрактичним для таких великих розмірів вхідних даних.
- Комбінована версія сортування вставкою та сортування злиттям: Я трохи налаштував логіку сортування злиттям, щоб досягти значно кращого часу роботи для менших розмірів вхідних даних. Як ми знаємо, сортування злиттям розділяє вхідні дані на дві половини, поки вони не стануть достатньо тривіальними для сортування елементів. Але тут, коли розмір вхідних даних падає нижче порогового значення, такого як «n»< 40 then this hybrid algorithm makes a call to traditional insertion sort procedure. From the fact that insertion sort runs faster on smaller inputs and merge sort runs faster on larger inputs this algorithm makes best use both the worlds.
- Швидке сортування: Я не реалізував цю процедуру. Це бібліотечна функція qsort(), яка доступна в . Я розглянув цей алгоритм, щоб зрозуміти важливість реалізації. Це вимагає великого досвіду програмування, щоб мінімізувати кількість кроків і максимально використати примітиви базової мови для реалізації алгоритму найкращим чином. Це головна причина, чому рекомендується використовувати бібліотечні функції. Вони написані для роботи з усім і вся. Вони максимально оптимізуються. І поки я не забуду з мого аналізу, qsort() працює неймовірно швидко практично з будь-яким розміром вхідних даних!
Аналіз:
- введення: Користувач повинен вказати кількість разів, які він/вона хоче протестувати алгоритм відповідно до кількості тестів. Для кожного тесту користувач повинен ввести два цілі числа, розділені пробілами, що позначають розмір вхідних даних «n» і «num_of_times», що позначає кількість разів, які він/вона хоче виконати аналіз і отримати середнє значення. (Пояснення: якщо «num_of_times» дорівнює 10, тоді кожен алгоритм, указаний вище, запускається 10 разів і береться середнє значення. Це робиться тому, що вхідний масив генерується випадковим чином відповідно до вказаного вами розміру. Вхідний масив може бути відсортований. Наш він може відповідати найгіршому випадку, тобто порядку спадання. Щоб уникнути часу виконання таких вхідних масивів. виконується алгоритм «num_of_times» і береться середнє значення.) програма clock() і макрос CLOCKS_PER_SEC з використовуються для вимірювання витраченого часу. Компіляція: я написав наведений вище код у середовищі Linux (Ubuntu 16.04 LTS). Скопіюйте наведений вище фрагмент коду. Скомпілюйте його, використовуючи ключ gcc у вхідних даних, як зазначено, і захоплюйтеся потужністю алгоритмів сортування!
- Результати: Як ви бачите, для малих розмірів вхідних даних сортування вставкою перевершує сортування злиттям за 2 * 10^-6 с. Але ця різниця в часі не настільки значна. З іншого боку, гібридний алгоритм і функція бібліотеки qsort() працюють так само добре, як сортування вставкою.
Розмір вхідних даних тепер збільшено приблизно в 100 разів до n = 1000 з n = 30. Різниця тепер відчутна. Сортування злиттям працює в 10 разів швидше, ніж сортування вставкою. Знову існує зв’язок між продуктивністю гібридного алгоритму та підпрограмою qsort(). Це свідчить про те, що qsort() реалізовано у спосіб, який більш-менш схожий на наш гібридний алгоритм, тобто перемикання між різними алгоритмами, щоб отримати з них найкраще.
Нарешті розмір вхідних даних збільшено до 10^5 (1 Lakh!), що, ймовірно, є ідеальним розміром, який використовується в практичних сценаріях. Порівняно з попереднім введенням n = 1000, де сортування злиттям випереджає сортування вставленням, працюючи в 10 разів швидше, тут різниця ще більша. Сортування злиттям перевершує сортування за вставкою в 100 разів! Гібридний алгоритм, який ми написали, фактично не виконує традиційне сортування злиттям, працюючи на 0,01 секунди швидше. І, нарешті, бібліотечна функція qsort() нарешті доводить нам, що реалізація також відіграє вирішальну роль під час ретельного вимірювання часу роботи, працюючи на 3 мілісекунди швидше! :D
Примітка. Не запускайте наведену вище програму з n >= 10^6, оскільки це займе багато обчислювальної потужності. Дякую і щасливого кодування! :)
Створіть вікторину