Jól megalapozott tény, hogy az egyesítési rendezés gyorsabban fut, mint a beillesztési rendezés. Használata aszimptotikus elemzés . bebizonyíthatjuk, hogy az egyesítési rendezés O(nlogn) idő alatt fut, a beillesztési rendezés pedig O(n^2). Nyilvánvaló, mert az összevonásos rendezés oszd meg és uralkodj megközelítést használ a problémák rekurzív megoldásával, ahol a beillesztési rendezés növekményes megközelítést követ. Ha még jobban megvizsgáljuk az időbonyolultság elemzését, akkor megtudjuk, hogy a beillesztési rendezés nem olyan rossz. Meglepő módon a beillesztési rendezési ütemek összevonják a rendezést kisebb bemeneti méretnél. Ennek az az oka, hogy kevés olyan állandó van, amelyet figyelmen kívül hagyunk az időbonyolultság következtetése során. Nagyobb, 10^4-es nagyságrendű bemeneti méreteknél ez nem befolyásolja függvényünk viselkedését. De ha a bemeneti méretek kisebbek, mint mondjuk 40, akkor az egyenletben szereplő állandók uralják az „n” bemeneti méretet. Eddig jó. De nem voltam megelégedve ezzel a matematikai elemzéssel. Számítástechnikai egyetemistaként hinnünk kell a kódírásban. Írtam egy C programot, hogy átérezhessem, hogyan versenyeznek egymással az algoritmusok a különböző bemeneti méretekért. És azt is, hogy miért végeznek ilyen szigorú matematikai elemzést ezeknek a rendezési algoritmusoknak a futási idejű összetettségének megállapítására.
szelén
Végrehajtás:
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();
Összehasonlítottam a következő algoritmusok futási idejét:
javascript karakterlánc csere
- Beillesztési rendezés : A hagyományos algoritmus módosítások/optimalizálás nélkül. Nagyon jól teljesít a kisebb bemeneti méreteknél. És igen, ez veri az összevonási fajta
- A sorsra jut : Az oszd meg és uralkodj megközelítést követi. A 10^5-ös nagyságrendű bemeneti méreteknél ez az algoritmus a megfelelő választás. Ez a beillesztési rendezést kivitelezhetetlenné teszi ilyen nagy bemeneti méretek esetén.
- A beillesztési rendezés és az összevonás rendezés kombinált változata: Kicsit módosítottam az egyesítési rendezés logikáját, hogy lényegesen jobb futási időt érjek el kisebb bemeneti méreteknél. Mint tudjuk, a merge sort két részre osztja a bemenetet, amíg az már elég triviális lesz az elemek rendezéséhez. De itt, amikor a bemeneti méret egy küszöbérték alá esik, például „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.
- Gyors rendezés: Ezt az eljárást nem hajtottam végre. Ez a qsort() könyvtárfüggvény, amely a következőben érhető el. Ezt az algoritmust azért vettem figyelembe, hogy megismerjem a megvalósítás jelentőségét. Nagy programozási szakértelmet igényel a lépések számának minimalizálása és legfeljebb az alapul szolgáló nyelvi primitívek felhasználása az algoritmus lehető legjobb megvalósításához. Ez a fő oka annak, hogy a könyvtári függvények használata javasolt. Arra írták őket, hogy bármit és mindent kezeljenek. A lehető legnagyobb mértékben optimalizálnak. És mielőtt elfelejtenék az elemzésemből, a qsort() rendkívül gyorsan fut gyakorlatilag bármilyen bemeneti méretűen!
Az elemzés:
- Bemenet: A felhasználónak meg kell adnia, hogy hányszor akarja tesztelni az algoritmust a tesztesetek számának megfelelően. Minden tesztesethez a felhasználónak két szóközzel elválasztott egész számot kell megadnia, amelyek az 'n' bemeneti méretet jelölik, valamint a 'num_of_times' értéket, amely azt jelzi, hogy hányszor szeretné lefuttatni az elemzést és átlagot venni. (Egyértelműség: Ha az ’idők_száma’ 10, akkor a fent megadott algoritmusok mindegyike 10-szer lefut, és az átlagot veszik. Ez azért van így, mert a bemeneti tömb véletlenszerűen jön létre az Ön által megadott bemeneti méretnek megfelelően. A bemeneti tömb lehet rendezve. A miénk a legrosszabb esetnek felelhet meg .azaz az ilyen futási idők sorrendje a csökkenő sorrendben. futtassa a 'num_of_times'-t, és az átlagot veszik.) clock() rutin és a CLOCKS_PER_SEC makrót használja az eltelt idő mérésére. Összeállítás: A fenti kódot Linux környezetben (Ubuntu 16.04 LTS) írtam. Másolja ki a fenti kódrészletet. Fordítsd le a bemenetekben megadott gcc kulcs segítségével, és csodáld meg a rendezési algoritmusok erejét!
- Eredmények: Amint látható, kis bemeneti méreteknél a beillesztési rendezési ütemek összevonása 2 * 10^-6 mp szerint történik. De ez az időbeli különbség nem olyan jelentős. Másrészt a hibrid algoritmus és a qsort() függvénykönyvtár függvény is ugyanolyan jól teljesít, mint a beillesztési rendezés.
A bemeneti méret most körülbelül 100-szor nőtt n = 1000-re n = 30-ról. A különbség most kézzelfogható. Az egyesített rendezés 10-szer gyorsabban fut, mint a beillesztési rendezés. A hibrid algoritmus és a qsort() rutin teljesítménye között ismét holtverseny van. Ez azt sugallja, hogy a qsort() olyan módon van megvalósítva, amely többé-kevésbé hasonlít a hibrid algoritmusunkhoz, azaz váltogatunk a különböző algoritmusok között, hogy a legjobbat hozzuk ki belőlük.
Végül a bemeneti méret 10^5-re (1 lakh!) nő, ami valószínűleg a gyakorlati forgatókönyvekben használt ideális méret. Az előző bemenethez képest, n = 1000, ahol az egyesített rendezés ütembeszúrásos rendezés 10-szer gyorsabban fut, itt még jelentősebb a különbség. Merge sort veri beszúrás rendezés 100-szor! Az általunk írt hibrid algoritmus valójában a hagyományos egyesítési rendezést hajtja végre, 0,01 másodperccel gyorsabban. És végül a qsort() könyvtárfüggvény végre bebizonyítja, hogy az implementáció is döntő szerepet játszik, miközben 3 ezredmásodperccel gyorsabban precízen méri a futási időket! :D
Megjegyzés: Ne futtassa a fenti programot n >= 10^6 értékkel, mivel az sok számítási teljesítményt igényel. Köszönöm és jó kódolást! :)
Kvíz létrehozása