Asimptotička analiza i usporedba algoritama sortiranja
Dobro je poznata činjenica da sortiranje spajanjem radi brže od sortiranja umetanjem. Korištenje asimptotska analiza . možemo dokazati da sortiranje spajanjem traje O(nlogn) vremena, a sortiranje umetanjem O(n^2). To je očito jer sortiranje spajanjem koristi pristup podijeli i vladaj rekurzivnim rješavanjem problema gdje sortiranje umetanjem slijedi inkrementalni pristup. Ako još dublje proučimo analizu vremenske složenosti, vidjet ćemo da vrsta umetanja nije toliko loša. Iznenađujuće sortiranje umetanjem je bolje od sortiranja spajanjem na manjoj veličini unosa. To je zato što postoji nekoliko konstanti koje ignoriramo dok deduciramo vremensku složenost. Na većim ulaznim veličinama reda 10^4 to ne utječe na ponašanje naše funkcije. Ali kada ulazne veličine padnu ispod, recimo manje od 40, tada konstante u jednadžbi dominiraju ulaznom veličinom 'n'. Zasada je dobro. Ali nisam bio zadovoljan takvom matematičkom analizom. Kao apsolvent informatike moramo vjerovati u pisanje koda. Napisao sam C program kako bih stekao osjećaj kako se algoritmi međusobno natječu za različite veličine ulaza. Također i zašto se provodi takva rigorozna matematička analiza za utvrđivanje složenosti vremena izvođenja ovih algoritama sortiranja.
Implementacija:
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 ();
Usporedio sam vremena rada sljedećih algoritama:
- Sortiranje umetanjem : Tradicionalni algoritam bez izmjena/optimizacije. Vrlo se dobro ponaša za manje ulazne veličine. I da, pobjeđuje sortiranje spajanjem
- Ide sudbina : Slijedi pristup podijeli pa vladaj. Za ulazne veličine reda 10^5 ovaj algoritam je pravi izbor. To sortiranje umetanjem čini nepraktičnim za tako velike ulazne veličine.
- Kombinirana verzija sortiranja umetanjem i sortiranja spajanjem: Malo sam prilagodio logiku sortiranja spajanjem kako bih postigao znatno bolje vrijeme rada za manje veličine unosa. Kao što znamo sortiranje spajanjem dijeli svoj unos na dvije polovice dok ne postane dovoljno trivijalan za sortiranje elemenata. Ali ovdje kada veličina unosa padne ispod praga kao što je '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.
- Brzo sortiranje: Nisam proveo ovaj postupak. Ovo je funkcija biblioteke qsort() koja je dostupna u . Razmotrio sam ovaj algoritam kako bih znao važnost implementacije. Zahtijeva veliku programsku stručnost kako bi se broj koraka sveo na najmanju moguću mjeru i maksimalno iskoristili temeljni jezični primitivi za implementaciju algoritma na najbolji mogući način. To je glavni razlog zašto se preporučuje korištenje funkcija knjižnice. Napisani su da se nose sa svime i svačim. Optimiziraju u najvećoj mogućoj mjeri. I prije nego što zaboravim iz moje analize, qsort() radi munjevito brzo na gotovo bilo kojoj veličini ulaza!
Analiza:
- Ulazni: Korisnik mora navesti koliko puta želi testirati algoritam koji odgovara broju testnih slučajeva. Za svaki testni slučaj korisnik mora unijeti dva cijela broja odvojena razmakom koji označavaju veličinu unosa 'n' i 'num_of_times' koji označavaju koliko puta on/ona želi pokrenuti analizu i uzeti prosjek. (Pojašnjenje: ako je 'num_of_times' 10, tada se svaki gore navedeni algoritam izvodi 10 puta i uzima se prosjek. To je učinjeno jer se ulazni niz generira nasumično u skladu s veličinom unosa koju navedete. Ulazni niz može biti sav sortiran. Naš bi mogao odgovarati najgorem slučaju, tj. silaznom redoslijedu. Kako bi se izbjegla vremena izvođenja takvih ulaznih nizova. algoritam se izvodi 'num_of_times' i uzima se prosjek.) clock() rutina i CLOCKS_PER_SEC makro iz se koristi za mjerenje vremena. Kompilacija: Napisao sam gornji kod u Linux okruženju (Ubuntu 16.04 LTS). Kopirajte gornji isječak koda. Prevedite ga korištenjem gcc ključa u unosima kako je navedeno i divite se snazi algoritama za sortiranje!
- Rezultati: Kao što možete vidjeti za male veličine unosa sortiranje umetanjem je bolje od sortiranja spajanjem 2 * 10^-6 sek. Ali ta razlika u vremenu nije toliko značajna. S druge strane, hibridni algoritam i funkcija knjižnice qsort() rade jednako dobro kao sortiranje umetanjem.
Veličina unosa sada je povećana za približno 100 puta na n = 1000 s n = 30. Razlika je sada opipljiva. Sortiranje spajanjem radi 10 puta brže od sortiranja umetanjem. Opet postoji veza između performansi hibridnog algoritma i qsort() rutine. Ovo sugerira da je qsort() implementiran na način koji je više-manje sličan našem hibridnom algoritmu, tj. prebacivanje između različitih algoritama kako bi se iz njih izvuklo najbolje. 
Na kraju se veličina unosa povećava na 10^5 (1 lakh!) što je najvjerojatnije idealna veličina koja se koristi u praktičnim scenarijima. U usporedbi s prethodnim unosom n = 1000 gdje sortiranje spajanjem pobjeđuje sortiranje umetanjem pokretanjem 10 puta brže, ovdje je razlika još značajnija. Sortiranje spajanjem bolje od sortiranja umetanjem 100 puta! Hibridni algoritam koji smo napisali zapravo ne izvodi tradicionalno sortiranje spajanjem radeći 0,01 sekundu brže. I na kraju, funkcija biblioteke qsort() konačno nam dokazuje da implementacija također igra ključnu ulogu pri preciznom mjerenju vremena rada jer radi 3 milisekunde brže! :D
Napomena: Nemojte pokretati gornji program s n >= 10^6 jer će oduzeti puno računalne snage. Hvala i sretno kodiranje! :)
Napravi kviz
