Asymptotische analyse en vergelijking van sorteeralgoritmen
Het is een algemeen bekend feit dat het samenvoegen sneller verloopt dan het invoegen. Gebruiken asymptotische analyse . we kunnen bewijzen dat het samenvoegen van sorteringen in O(nlogn) tijd verloopt en dat het invoegen van sorteringen O(n^2) duurt. Het ligt voor de hand omdat merge sort een verdeel-en-heers-benadering gebruikt door de problemen recursief op te lossen, terwijl invoegsortering een incrementele benadering volgt. Als we de analyse van de tijdscomplexiteit nog verder onderzoeken, zullen we ontdekken dat het invoegen niet zo erg genoeg is. Verrassend genoeg voegen sorteerbeats de sortering op een kleiner invoerformaat samen. Dit komt omdat er weinig constanten zijn die we negeren bij het afleiden van de tijdscomplexiteit. Bij grotere invoergroottes van de orde 10^4 heeft dit geen invloed op het gedrag van onze functie. Maar wanneer de invoergrootte onder de 40 komt, domineren de constanten in de vergelijking de invoergrootte ‘n’. Tot nu toe gaat het goed. Maar ik was niet tevreden met zo’n wiskundige analyse. Als student informatica moeten we geloven in het schrijven van code. Ik heb een C-programma geschreven om een idee te krijgen van hoe de algoritmen met elkaar concurreren om verschillende invoergroottes. En ook waarom er zo’n rigoureuze wiskundige analyse wordt uitgevoerd om de looptijdcomplexiteit van deze sorteeralgoritmen vast te stellen.
Uitvoering:
CPP #include #include #include #include #define MAX_ELEMENT_IN_ARRAY 1000000001 int cmpfunc ( const void * a const void * b ) { // Compare function used by qsort return ( * ( int * ) a - * ( int * ) b ); } int * generate_random_array ( int n ) { srand ( time ( NULL )); int * a = malloc ( sizeof ( int ) * n ); int i ; for ( i = 0 ; i < n ; ++ i ) a [ i ] = rand () % MAX_ELEMENT_IN_ARRAY ; return a ; } int * copy_array ( int a [] int n ) { int * arr = malloc ( sizeof ( int ) * n ); int i ; for ( i = 0 ; i < n ; ++ i ) arr [ i ] = a [ i ]; return arr ; } // Code for Insertion Sort void insertion_sort_asc ( int a [] int start int end ) { int i ; for ( 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 ; } } // Code for Merge Sort void merge ( int a [] int start int end int mid ) { int i = start j = mid + 1 k = 0 ; int * aux = malloc ( sizeof ( int ) * ( end - start + 1 )); 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 ++ ]; j = 0 ; for ( i = start ; i <= end ; ++ i ) a [ i ] = aux [ j ++ ]; free ( aux ); } void _merge_sort ( int a [] int start int end ) { if ( start < end ) { int mid = start + ( end - start ) / 2 ; _merge_sort ( a start mid ); _merge_sort ( a mid + 1 end ); merge ( a start end mid ); } } void merge_sort ( int a [] int n ) { return _merge_sort ( a 0 n - 1 ); } void insertion_and_merge_sort_combine ( int a [] int start int end int k ) { // Performs insertion sort if size of array is less than or equal to k // Otherwise uses mergesort if ( start < end ) { int size = end - start + 1 ; if ( size <= k ) { return insertion_sort_asc ( a start end ); } int 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 ); } } void test_sorting_runtimes ( int size int num_of_times ) { // Measuring the runtime of the sorting algorithms int number_of_times = num_of_times ; int t = number_of_times ; int n = size ; double insertion_sort_time = 0 merge_sort_time = 0 ; double merge_sort_and_insertion_sort_mix_time = 0 qsort_time = 0 ; while ( t -- ) { clock_t start end ; int * a = generate_random_array ( n ); int * b = copy_array ( a n ); start = clock (); insertion_sort_asc ( b 0 n - 1 ); end = clock (); insertion_sort_time += (( double )( end - start )) / CLOCKS_PER_SEC ; free ( b ); int * c = copy_array ( a n ); start = clock (); merge_sort ( c n ); end = clock (); merge_sort_time += (( double )( end - start )) / CLOCKS_PER_SEC ; free ( c ); int * d = copy_array ( a n ); start = clock (); insertion_and_merge_sort_combine ( d 0 n - 1 40 ); end = clock (); merge_sort_and_insertion_sort_mix_time += (( double )( end - start )) / CLOCKS_PER_SEC ; free ( d ); start = clock (); qsort ( a n sizeof ( int ) cmpfunc ); end = clock (); qsort_time += (( double )( end - start )) / CLOCKS_PER_SEC ; free ( a ); } insertion_sort_time /= number_of_times ; merge_sort_time /= number_of_times ; merge_sort_and_insertion_sort_mix_time /= number_of_times ; qsort_time /= number_of_times ; printf ( ' n Time taken to sort: n ' '%-35s %f n ' '%-35s %f n ' '%-35s %f n ' '%-35s %f nn ' '(i)Insertion sort: ' insertion_sort_time '(ii)Merge sort: ' merge_sort_time '(iii)Insertion-mergesort-hybrid: ' merge_sort_and_insertion_sort_mix_time '(iv)Qsort library function: ' qsort_time ); } int main ( int argc char const * argv []) { int t ; scanf ( '%d' & t ); while ( t -- ) { int size num_of_times ; scanf ( '%d %d' & size & num_of_times ); test_sorting_runtimes ( size num_of_times ); } return 0 ; }
Java 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' ); } }
Python3 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 ' n Time 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 ()
JavaScript // 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 ();
Ik heb de looptijden van de volgende algoritmen vergeleken:
- Invoegsoort : Het traditionele algoritme zonder aanpassingen/optimalisatie. Het presteert zeer goed voor kleinere invoerformaten. En ja, het verslaat het samenvoegen
- Gaat het lot : Volgt de verdeel-en-heers-aanpak. Voor invoergroottes van de orde 10^5 is dit algoritme de juiste keuze. Het maakt invoegsortering onpraktisch voor zulke grote invoergroottes.
- Gecombineerde versie van invoeg- en samenvoegsortering: Ik heb de logica van het samenvoegen een beetje aangepast om een aanzienlijk betere looptijd te bereiken voor kleinere invoergroottes. Zoals we weten splitst merge sort de invoer in twee helften totdat het triviaal genoeg is om de elementen te sorteren. Maar hier, wanneer de invoergrootte onder een drempelwaarde zoals 'n' valt < 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.
- Snel sorteren: Ik heb deze procedure niet geïmplementeerd. Dit is de bibliotheekfunctie qsort() die beschikbaar is in . Ik heb dit algoritme overwogen om de betekenis van de implementatie te kennen. Het vergt veel programmeerkennis om het aantal stappen te minimaliseren en maximaal gebruik te maken van de onderliggende taalprimitieven om een algoritme op de best mogelijke manier te implementeren. Dit is de belangrijkste reden waarom het wordt aanbevolen om bibliotheekfuncties te gebruiken. Ze zijn geschreven om van alles en nog wat aan te kunnen. Ze optimaliseren maximaal. En voordat ik het uit mijn analyse vergeet, werkt qsort() razendsnel op vrijwel elke invoergrootte!
De analyse:
- Invoer: De gebruiker moet het aantal keren opgeven dat hij/zij het algoritme wil testen, overeenkomend met het aantal testgevallen. Voor elk testgeval moet de gebruiker twee door spaties gescheiden gehele getallen invoeren die de invoergrootte ‘n’ aangeven en ‘num_of_times’ dat het aantal keren aangeeft dat hij/zij de analyse wil uitvoeren en het gemiddelde wil nemen. (Verduidelijking: als ‘num_of_times’ 10 is, wordt elk hierboven gespecificeerd algoritme 10 keer uitgevoerd en wordt het gemiddelde genomen. Dit wordt gedaan omdat de invoerarray willekeurig wordt gegenereerd in overeenstemming met de invoergrootte die u opgeeft. De invoerarray kan allemaal worden gesorteerd. Dit kan overeenkomen met het slechtste geval, dat wil zeggen in aflopende volgorde. Om de looptijd van dergelijke invoerarrays te voorkomen. Het algoritme wordt ‘num_of_times’ uitgevoerd en het gemiddelde wordt genomen.) clock() routine en CLOCKS_PER_SEC macro van wordt gebruikt om de benodigde tijd te meten. Compilatie: Ik heb bovenstaande code geschreven in een Linux-omgeving (Ubuntu 16.04 LTS). Kopieer het bovenstaande codefragment. Compileer het met behulp van de gcc-sleutel in de invoer zoals gespecificeerd en bewonder de kracht van sorteeralgoritmen!
- Resultaten: Zoals je kunt zien, worden voor kleine invoerformaten invoeg- en sorteerbeats samengevoegd en gesorteerd op 2 * 10^-6 sec. Maar dit tijdsverschil is niet zo groot. Aan de andere kant presteren het hybride algoritme en de bibliotheekfunctie qsort() beide net zo goed als invoegsortering.
De invoergrootte is nu ongeveer 100 keer vergroot van n = 30 naar n = 1000. Het verschil is nu voelbaar. Samenvoegsortering werkt 10 keer sneller dan invoegsortering. Er is opnieuw een verband tussen de prestaties van het hybride algoritme en de qsort()-routine. Dit suggereert dat qsort() is geïmplementeerd op een manier die min of meer vergelijkbaar is met ons hybride algoritme, d.w.z. schakelen tussen verschillende algoritmen om er het beste uit te halen. 
Ten slotte wordt de invoergrootte vergroot tot 10^5 (1 Lakh!) wat hoogstwaarschijnlijk de ideale grootte is die in praktische scenario’s wordt gebruikt. Vergeleken met de vorige invoer n = 1000, waarbij samenvoegsortering en invoegsortering 10 keer sneller worden uitgevoerd, is het verschil hier zelfs nog groter. Sorteren samenvoegen verslaat invoegen en sorteren 100 keer! Het hybride algoritme dat we hebben geschreven voert feitelijk de traditionele samenvoegbewerking uit door 0,01 seconde sneller te werken. En ten slotte bewijst de bibliotheekfunctie qsort() ons eindelijk dat implementatie ook een cruciale rol speelt bij het nauwkeurig meten van de looptijden door 3 milliseconden sneller te draaien! :D
Let op: voer het bovenstaande programma niet uit met n >= 10^6, omdat dit veel rekenkracht vergt. Bedankt en veel codeerplezier! :)
Quiz maken
