C'est un fait bien établi que le tri par fusion s'exécute plus rapidement que le tri par insertion. En utilisant analyse asymptotique . nous pouvons prouver que le tri par fusion s'exécute en un temps O (nlogn) et que le tri par insertion prend O (n ^ 2). C'est évident car le tri par fusion utilise une approche diviser pour régner en résolvant les problèmes de manière récursive alors que le tri par insertion suit une approche incrémentielle. Si nous examinons encore plus attentivement l’analyse de la complexité temporelle, nous découvrirons que le tri par insertion n’est pas si mauvais. Étonnamment, le tri par insertion bat le tri par fusion sur une taille d'entrée plus petite. En effet, il y a peu de constantes que nous ignorons lors de la déduction de la complexité temporelle. Sur des tailles d'entrée plus grandes de l'ordre 10 ^ 4, cela n'influence pas le comportement de notre fonction. Mais lorsque la taille d’entrée tombe en dessous, disons, de moins de 40, alors les constantes de l’équation dominent la taille d’entrée « n ». Jusqu'ici, tout va bien. Mais je n’étais pas satisfait d’une telle analyse mathématique. En tant qu'étudiant de premier cycle en informatique, nous devons croire en l'écriture de code. J'ai écrit un programme C pour avoir une idée de la façon dont les algorithmes se font concurrence pour différentes tailles d'entrée. Et aussi pourquoi une analyse mathématique aussi rigoureuse est effectuée pour établir la complexité du temps d'exécution de ces algorithmes de tri.
différence entre programme et script
Mise en œuvre:
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();
J'ai comparé les temps d'exécution des algorithmes suivants :
commutateur dactylographié
- Tri par insertion : L'algorithme traditionnel sans modifications/optimisation. Il fonctionne très bien pour les tailles d'entrée plus petites. Et oui, cela bat le tri par fusion
- Va le destin : Suit l’approche diviser pour régner. Pour des tailles d'entrée de l'ordre 10^5, cet algorithme est le bon choix. Cela rend le tri par insertion peu pratique pour des tailles d'entrée aussi grandes.
- Version combinée du tri par insertion et du tri par fusion : J'ai légèrement modifié la logique du tri par fusion pour obtenir un temps d'exécution considérablement meilleur pour les tailles d'entrée plus petites. Comme nous le savons, le tri par fusion divise son entrée en deux moitiés jusqu'à ce qu'il soit suffisamment trivial pour trier les éléments. Mais ici, lorsque la taille d'entrée tombe en dessous d'un seuil tel que '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.
- Tri rapide : Je n'ai pas mis en œuvre cette procédure. Il s'agit de la fonction de bibliothèque qsort() qui est disponible dans . J'ai considéré cet algorithme afin de connaître l'importance de la mise en œuvre. Cela nécessite une grande expertise en programmation pour minimiser le nombre d'étapes et utiliser au maximum les primitives du langage sous-jacentes pour implémenter un algorithme de la meilleure façon possible. C'est la principale raison pour laquelle il est recommandé d'utiliser les fonctions de la bibliothèque. Ils sont écrits pour gérer tout et n’importe quoi. Ils optimisent au maximum. Et avant que j'oublie de mon analyse, qsort() s'exécute à une vitesse fulgurante sur pratiquement toutes les tailles d'entrée !
L'analyse :
- Saisir: L'utilisateur doit fournir le nombre de fois qu'il souhaite tester l'algorithme correspondant au nombre de cas de test. Pour chaque scénario de test, l'utilisateur doit saisir deux entiers séparés par des espaces indiquant la taille d'entrée « n » et le « num_of_times » indiquant le nombre de fois qu'il souhaite exécuter l'analyse et prendre la moyenne. (Clarification : si « num_of_times » est égal à 10, alors chacun des algorithmes spécifiés ci-dessus s'exécute 10 fois et la moyenne est prise. Ceci est dû au fait que le tableau d'entrée est généré de manière aléatoire, correspondant à la taille d'entrée que vous spécifiez. Le tableau d'entrée peut être entièrement trié. Il pourrait correspondre au pire des cas, c'est-à-dire l'ordre décroissant. Afin d'éviter les temps d'exécution de ces tableaux d'entrée. L'algorithme est exécuté « num_of_times » et la moyenne est prise.) Routine clock() et la macro CLOCKS_PER_SEC de est utilisée pour mesurer le temps pris. Compilation : J'ai écrit le code ci-dessus dans un environnement Linux (Ubuntu 16.04 LTS). Copiez l'extrait de code ci-dessus. Compilez-le en utilisant la clé gcc dans les entrées comme spécifié et admirez la puissance des algorithmes de tri !
- Résultats: Comme vous pouvez le voir pour les petites tailles d'entrée, le tri par insertion bat le tri par fusion de 2 * 10 ^ -6 sec. Mais cette différence de temps n’est pas si significative. D'un autre côté, l'algorithme hybride et la fonction de la bibliothèque qsort() fonctionnent tous deux aussi bien que le tri par insertion.
La taille d’entrée est désormais augmentée d’environ 100 fois, passant de n = 30 à n = 1 000. La différence est désormais tangible. Le tri par fusion est 10 fois plus rapide que le tri par insertion. Il existe encore une fois un lien entre les performances de l'algorithme hybride et celles de la routine qsort(). Cela suggère que qsort() est implémenté d'une manière plus ou moins similaire à notre algorithme hybride, c'est-à-dire en basculant entre différents algorithmes pour en tirer le meilleur parti.
Enfin, la taille d'entrée est augmentée à 10 ^ 5 (1 Lakh !), ce qui est très probablement la taille idéale utilisée dans les scénarios pratiques. Par rapport à l'entrée précédente n = 1000 où le tri par fusion bat le tri par insertion en s'exécutant 10 fois plus vite, ici la différence est encore plus significative. Le tri par fusion bat le tri par insertion de 100 fois ! L'algorithme hybride que nous avons écrit surpasse en fait le tri par fusion traditionnel en s'exécutant 0,01 seconde plus rapidement. Et enfin qsort() la fonction de la bibliothèque nous prouve enfin que l'implémentation joue également un rôle crucial tout en mesurant méticuleusement les temps d'exécution en exécutant 3 millisecondes plus vite ! :D
Remarque : n'exécutez pas le programme ci-dessus avec n >= 10^6 car cela nécessiterait beaucoup de puissance de calcul. Merci et bon codage ! :)
Créer un quiz