Добре установен факт е, че сортирането чрез сливане работи по-бързо от сортирането чрез вмъкване. Използване асимптотичен анализ . можем да докажем, че сортирането чрез сливане се изпълнява за O(nlogn) време, а сортирането чрез вмъкване отнема O(n^2). Очевидно е, защото сортирането чрез сливане използва подход "разделяй и владей" чрез рекурсивно решаване на проблемите, където сортирането чрез вмъкване следва постепенен подход. Ако разгледаме още повече анализа на времевата сложност, ще разберем, че сортирането на вмъкване не е толкова лошо. Изненадващо сортирането чрез вмъкване побеждава сортирането чрез сливане при по-малък входен размер. Това е така, защото има няколко константи, които пренебрегваме, докато извеждаме времевата сложност. При по-големи входни размери от порядъка на 10^4 това не влияе на поведението на нашата функция. Но когато входните размери паднат под да речем по-малко от 40, тогава константите в уравнението доминират над входния размер „n“. Дотук добре. Но не бях доволен от такъв математически анализ. Като студент по компютърни науки трябва да вярваме в писането на код. Написах програма на C, за да усетя как алгоритмите се конкурират един срещу друг за различни входни размери. А също и защо се прави толкова строг математически анализ за установяване на сложността на времето за изпълнение на тези алгоритми за сортиране.
мултиплексор две към едно
Изпълнение:
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 този алгоритъм е правилният избор. Това прави сортирането чрез вмъкване непрактично за такива големи входни размери.
- Комбинирана версия на сортиране чрез вмъкване и сортиране чрез сливане: Промених малко логиката на сортиране чрез сливане, за да постигна значително по-добро време за работа за по-малки входни размери. Както знаем, merge sort разделя своя вход на две половини, докато стане достатъчно тривиален, за да сортира елементите. Но тук, когато размерът на входа падне под праг като „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, тъй като ще отнеме много изчислителна мощност. Благодаря ви и приятно кодиране! :)
Създаване на тест