Es ist eine allgemein anerkannte Tatsache, dass die Zusammenführungssortierung schneller abläuft als die Einfügungssortierung. Benutzen asymptotische Analyse . Wir können beweisen, dass die Zusammenführungssortierung in O(nlogn) Zeit ausgeführt wird und die Einfügungssortierung O(n^2) benötigt. Dies ist offensichtlich, da die Zusammenführungssortierung einen Divide-and-Conquer-Ansatz verwendet, indem die Probleme rekursiv gelöst werden, während die Einfügungssortierung einem inkrementellen Ansatz folgt. Wenn wir die Zeitkomplexitätsanalyse noch genauer unter die Lupe nehmen, werden wir feststellen, dass die Einfügungssortierung nicht so schlimm genug ist. Überraschenderweise schlägt die Einfügungssortierung die Zusammenführungssortierung bei kleinerer Eingabegröße. Dies liegt daran, dass es nur wenige Konstanten gibt, die wir bei der Ableitung der Zeitkomplexität ignorieren. Bei größeren Eingabegrößen in der Größenordnung von 10^4 hat dies keinen Einfluss auf das Verhalten unserer Funktion. Wenn die Eingabegrößen jedoch unter beispielsweise weniger als 40 fallen, dominieren die Konstanten in der Gleichung die Eingabegröße „n“. So weit, ist es gut. Aber ich war mit einer solchen mathematischen Analyse nicht zufrieden. Als Informatikstudent müssen wir an das Schreiben von Code glauben. Ich habe ein C-Programm geschrieben, um ein Gefühl dafür zu bekommen, wie die Algorithmen bei verschiedenen Eingabegrößen miteinander konkurrieren. Und auch, warum eine so strenge mathematische Analyse durchgeführt wird, um die Laufzeitkomplexität dieser Sortieralgorithmen zu ermitteln.
Binärer Suchbaum vs. Binärbaum
Durchführung:
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();
Ich habe die Laufzeiten der folgenden Algorithmen verglichen:
E-R-Modelldiagramm
- Einfügungssortierung : Der traditionelle Algorithmus ohne Modifikationen/Optimierung. Es funktioniert sehr gut für kleinere Eingabegrößen. Und ja, es schlägt die Zusammenführungssortierung
- Geht Schicksal : Folgt dem Divide-and-Conquer-Ansatz. Für Eingabegrößen in der Größenordnung von 10^5 ist dieser Algorithmus die richtige Wahl. Es macht die Einfügungssortierung für solch große Eingabegrößen unpraktisch.
- Kombinierte Version von Einfügungssortierung und Zusammenführungssortierung: Ich habe die Logik der Zusammenführungssortierung ein wenig optimiert, um eine deutlich bessere Laufzeit für kleinere Eingabegrößen zu erreichen. Wie wir wissen, teilt die Zusammenführungssortierung ihre Eingabe in zwei Hälften, bis sie trivial genug ist, um die Elemente zu sortieren. Aber hier, wenn die Eingabegröße unter einen Schwellenwert wie „n“ fällt< 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.
- Schnelle Sortierung: Ich habe dieses Verfahren nicht implementiert. Dies ist die Bibliotheksfunktion qsort(), die in verfügbar ist. Ich habe diesen Algorithmus betrachtet, um die Bedeutung der Implementierung zu kennen. Es erfordert viel Programmierwissen, um die Anzahl der Schritte zu minimieren und die zugrunde liegenden Sprachprimitive optimal zu nutzen, um einen Algorithmus bestmöglich zu implementieren. Dies ist der Hauptgrund, warum die Verwendung von Bibliotheksfunktionen empfohlen wird. Sie sind so geschrieben, dass sie mit allem und jedem umgehen können. Sie optimieren so weit wie möglich. Und bevor ich meine Analyse vergesse, läuft qsort() auf praktisch jeder Eingabegröße unglaublich schnell!
Die Analyse:
- Eingang: Der Benutzer muss angeben, wie oft er den Algorithmus entsprechend der Anzahl der Testfälle testen möchte. Für jeden Testfall muss der Benutzer zwei durch Leerzeichen getrennte Ganzzahlen eingeben, die die Eingabegröße „n“ angeben, und „num_of_times“, die angibt, wie oft er die Analyse ausführen und den Durchschnitt ermitteln möchte. (Klarstellung: Wenn „num_of_times“ 10 ist, wird jeder der oben angegebenen Algorithmen 10 Mal ausgeführt und der Durchschnitt gebildet. Dies geschieht, weil das Eingabearray entsprechend der von Ihnen angegebenen Eingabegröße zufällig generiert wird. Das Eingabearray könnte vollständig sortiert sein. Oder es könnte dem schlimmsten Fall entsprechen, d. h. in absteigender Reihenfolge. Um Laufzeiten solcher Eingabearrays zu vermeiden. Der Algorithmus wird „num_of_times“ ausgeführt und der Durchschnitt wird gebildet.) Mit der Routine „clock()“ und dem Makro „CLOCKS_PER_SEC“ wird die benötigte Zeit gemessen. Zusammenstellung: Ich habe den obigen Code in einer Linux-Umgebung (Ubuntu 16.04 LTS) geschrieben. Kopieren Sie den Codeausschnitt oben. Kompilieren Sie es mit dem gcc-Schlüssel in den angegebenen Eingaben und bewundern Sie die Leistungsfähigkeit der Sortieralgorithmen!
- Ergebnisse: Wie Sie sehen können, schlägt die Einfügungssortierung bei kleinen Eingabegrößen die Zusammenführungssortierung um 2 * 10^-6 Sekunden. Aber dieser Zeitunterschied ist nicht so groß. Andererseits funktionieren sowohl der Hybridalgorithmus als auch die Bibliotheksfunktion qsort() genauso gut wie die Einfügungssortierung.
Die Eingabegröße wird nun von n = 30 um etwa das Hundertfache auf n = 1000 erhöht. Der Unterschied ist jetzt spürbar. Die Zusammenführungssortierung läuft zehnmal schneller als die Einfügungssortierung. Auch hier besteht ein Zusammenhang zwischen der Leistung des Hybridalgorithmus und der qsort()-Routine. Dies deutet darauf hin, dass qsort() auf eine Weise implementiert ist, die mehr oder weniger unserem Hybridalgorithmus ähnelt, d. h. zwischen verschiedenen Algorithmen wechselt, um das Beste aus ihnen herauszuholen.
Schließlich wird die Eingabegröße auf 10^5 (1 Lakh!) erhöht, was höchstwahrscheinlich die ideale Größe ist, die in praktischen Szenarien verwendet wird. Im Vergleich zur vorherigen Eingabe n = 1000, bei der die Zusammenführungssortierung die Einfügungssortierung übertrifft und zehnmal schneller ausgeführt wird, ist der Unterschied hier noch deutlicher. Zusammenführungssortierung übertrifft Einfügungssortierung um das Hundertfache! Der von uns geschriebene Hybridalgorithmus übertrifft tatsächlich die herkömmliche Zusammenführungssortierung, indem er 0,01 Sekunden schneller läuft. Und schließlich beweist uns die Bibliotheksfunktion qsort() endlich, dass auch die Implementierung eine entscheidende Rolle bei der akribischen Messung der Laufzeiten spielt, indem sie 3 Millisekunden schneller läuft! :D
Hinweis: Führen Sie das obige Programm nicht mit n >= 10^6 aus, da dies viel Rechenleistung erfordert. Vielen Dank und viel Spaß beim Codieren! :) :)
Quiz erstellen