Asymptotisk analys och jämförelse av sorteringsalgoritmer
Det är ett välkänt faktum att sammanslagningssortering går snabbare än infogningssortering. Använder asymptotisk analys . vi kan bevisa att merge sort körs i O(nlogn) tid och insertion sort tar O(n^2). Det är uppenbart eftersom merge sort använder en dela-och-härska tillvägagångssätt genom att rekursivt lösa problemen där insättningssortering följer en inkrementell metod. Om vi granskar tidskomplexitetsanalysen ytterligare kommer vi att få veta att insättningssorteringen inte är så illa nog. Överraskande nog slår insättningssorteringsslag samman sortering på mindre indatastorlek. Detta beror på att det finns få konstanter som vi ignorerar när vi härleder tidskomplexiteten. På större inmatningsstorlekar i storleksordningen 10^4 påverkar detta inte vår funktions beteende. Men när indatastorlekar faller under säg mindre än 40 så dominerar konstanterna i ekvationen ingångsstorleken 'n'. Så långt så bra. Men jag var inte nöjd med en sådan matematisk analys. Som en datavetenskaplig kandidat måste vi tro på att skriva kod. Jag har skrivit ett C-program för att få en känsla av hur algoritmerna tävlar mot varandra för olika inmatningsstorlekar. Och även varför en så rigorös matematisk analys görs för att fastställa driftstidskomplexiteter för dessa sorteringsalgoritmer.
Genomförande:
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 ();
Jag har jämfört körtiderna för följande algoritmer:
- Insättningssort : Den traditionella algoritmen utan modifieringar/optimering. Den fungerar mycket bra för mindre inmatningsstorlekar. Och ja, det slår merge sort
- Går ödet : Följer dela-och-härska-metoden. För inmatningsstorlekar i storleksordningen 10^5 är denna algoritm det rätta valet. Det gör insättningssorteringen opraktisk för så stora inmatningsstorlekar.
- Kombinerad version av infogningssortering och sammanfogningssortering: Jag har finjusterat logiken i sammanslagningssorteringen lite för att uppnå en betydligt bättre körtid för mindre inmatningsstorlekar. Som vi vet delar sort upp sin input i två halvor tills den är trivial nog att sortera elementen. Men här när indatastorleken faller under ett tröskelvärde som '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.
- Snabb sortering: Jag har inte implementerat denna procedur. Detta är biblioteksfunktionen qsort() som är tillgänglig i . Jag har övervägt denna algoritm för att veta betydelsen av implementering. Det krävs en hel del programmeringsexpertis för att minimera antalet steg och som mest använda de underliggande språkprimitiven för att implementera en algoritm på bästa möjliga sätt. Detta är den främsta anledningen till att det rekommenderas att använda biblioteksfunktioner. De är skrivna för att hantera allt och allt. De optimerar så mycket som möjligt. Och innan jag glömmer av min analys går qsort() blixtrande snabbt på praktiskt taget alla inmatningsstorlekar!
Analysen:
- Input: Användaren måste ange hur många gånger han/hon vill testa algoritmen motsvarande antalet testfall. För varje testfall måste användaren ange två mellanrumsseparerade heltal som anger indatastorleken 'n' och 'antal_of_times' som anger antalet gånger han/hon vill köra analysen och ta medelvärde. (Förtydligande: Om 'antal_of_times' är 10 så körs var och en av algoritmerna som anges ovan 10 gånger och medelvärdet tas. Detta görs eftersom inmatningsmatrisen genereras slumpmässigt motsvarande den inmatningsstorlek som du anger. Inmatningsmatrisen kan vara all sorterad. Vår den kan motsvara det värsta fallet, dvs. algoritmen körs 'antal_of_times' och genomsnittet tas.) clock()-rutinen och CLOCKS_PER_SEC-makro från används för att mäta tiden det tar. Kompilering: Jag har skrivit ovanstående kod i Linux-miljö (Ubuntu 16.04 LTS). Kopiera kodavsnittet ovan. Kompilera den med hjälp av gcc-tangenten i ingångarna som specificerats och beundra kraften i sorteringsalgoritmer!
- Resultat: Som du kan se för små inmatningsstorlekar infogning av slag slå samman sortera med 2 * 10^-6 sek. Men denna skillnad i tid är inte så stor. Å andra sidan fungerar både hybridalgoritmen och biblioteksfunktionen qsort() lika bra som insertion sort.
Inmatningsstorleken ökas nu med cirka 100 gånger till n = 1000 från n = 30. Skillnaden är nu påtaglig. Merge sortering går 10 gånger snabbare än infogningssortering. Det finns återigen ett samband mellan prestandan för hybridalgoritmen och qsort()-rutinen. Detta tyder på att qsort() implementeras på ett sätt som är mer eller mindre likt vår hybridalgoritm, dvs att växla mellan olika algoritmer för att göra det bästa av dem. 
Slutligen ökas inmatningsstorleken till 10^5 (1 Lakh!), vilket troligen är den idealiska storleken som används i praktiska scenarier. Jämfört med den tidigare ingången n = 1000 där sammanslagna sorteringsslag infogningssortering genom att köra 10 gånger snabbare här är skillnaden ännu mer signifikant. Slå samman sorteringsslag infogning sortera med 100 gånger! Hybridalgoritmen som vi har skrivit utför faktiskt inte den traditionella sammanslagningssorteringen genom att köra 0,01 sek snabbare. Och slutligen qsort() biblioteksfunktionen bevisar oss äntligen att implementering också spelar en avgörande roll samtidigt som man mäter körtiderna noggrant genom att köra 3 millisekunder snabbare! :D
Obs: Kör inte ovanstående program med n >= 10^6 eftersom det kommer att kräva mycket datorkraft. Tack och trevlig kodning! :)
Skapa frågesport
