АСИМПТОТИЧЕН АНАЛИЗ И СРАВНЕНИЕ НА АЛГОРИТМИ ЗА СОРТИРАНЕ

Добре установен факт е, че сортирането чрез сливане работи по-бързо от сортирането чрез вмъкване. Използване асимптотичен анализ . можем да докажем, че сортирането чрез сливане се изпълнява за O(nlogn) време, а сортирането чрез вмъкване отнема O(n^2). Очевидно е, защото сортирането чрез сливане използва подход "разделяй и владей" чрез рекурсивно решаване на проблемите, където сортирането чрез вмъкване следва постепенен подход. Ако разгледаме още повече анализа на времевата сложност, ще разберем, че сортирането на вмъкване не е толкова лошо. Изненадващо сортирането чрез вмъкване побеждава сортирането чрез сливане при по-малък входен размер. Това е така, защото има няколко константи, които пренебрегваме, докато извеждаме времевата сложност. При по-големи входни размери от порядъка на 10^4 това не влияе на поведението на нашата функция. Но когато входните размери паднат под да речем по-малко от 40, тогава константите в уравнението доминират над входния размер „n“. Дотук добре. Но не бях доволен от такъв математически анализ. Като студент по компютърни науки трябва да вярваме в писането на код. Написах програма на C, за да усетя как алгоритмите се конкурират един срещу друг за различни входни размери. А също и защо се прави толкова строг математически анализ за установяване на сложността на времето за изпълнение на тези алгоритми за сортиране.

Изпълнение:

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  ();

Сравних времената на изпълнение на следните алгоритми:

Сортиране на вмъкване : Традиционният алгоритъм без модификации/оптимизация. Той се представя много добре за по-малки входни размери. И да, побеждава сортирането чрез сливане
Отива съдбата : Следва подхода "разделяй и владей". За входни размери от порядъка на 10^5 този алгоритъм е правилният избор. Това прави сортирането чрез вмъкване непрактично за такива големи входни размери.
Комбинирана версия на сортиране чрез вмъкване и сортиране чрез сливане: Промених малко логиката на сортиране чрез сливане, за да постигна значително по-добро време за работа за по-малки входни размери. Както знаем, merge sort разделя своя вход на две половини, докато стане достатъчно тривиален, за да сортира елементите. Но тук, когато размерът на входа падне под праг като „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.
Бързо сортиране: Не съм прилагал тази процедура. Това е библиотечната функция qsort(), която е налична в . Разгледах този алгоритъм, за да разбера значението на внедряването. Изисква се голям опит в програмирането, за да се сведе до минимум броят на стъпките и да се използват максимално базовите езикови примитиви, за да се приложи алгоритъм по възможно най-добрия начин. Това е основната причина, поради която се препоръчва използването на библиотечни функции. Те са написани да се справят с всичко и всичко. Те оптимизират до максималната възможна степен. И преди да забравя от моя анализ, qsort() работи светкавично бързо на почти всеки входен размер!

Анализът:

вход: Потребителят трябва да посочи колко пъти иска да тества алгоритъма, съответстващ на броя тестови случаи. За всеки тестов случай потребителят трябва да въведе две цели числа, разделени с интервали, обозначаващи размера на входа „n“ и „num_of_times“, обозначаващи броя пъти, които той/тя иска да изпълни анализа и да вземе средна стойност. (Пояснение: Ако „num_of_times“ е 10, тогава всеки алгоритъм, посочен по-горе, се изпълнява 10 пъти и се взема средната стойност. Това се прави, защото входният масив се генерира на случаен принцип, съответстващ на входния размер, който посочите. Входящият масив може да бъде сортиран. Нашият може да съответства на най-лошия случай, т.е. в низходящ ред. За да се избегнат времена на изпълнение на такива входни масиви. алгоритъмът се изпълнява „num_of_times“ и се взема средната стойност.) clock() рутина и CLOCKS_PER_SEC макрос от се използва за измерване на времето, което отнема. Компилация: Написах горния код в Linux среда (Ubuntu 16.04 LTS). Копирайте кодовия фрагмент по-горе. Компилирайте го, като използвате gcc ключ във входовете, както е посочено, и се възхищавайте на силата на алгоритмите за сортиране!
Резултати: Както можете да видите за малки входни размери, сортирането при вмъкване бие сортирането чрез сливане с 2 * 10^-6 сек. Но тази разлика във времето не е толкова значителна. От друга страна, хибридният алгоритъм и библиотечната функция qsort() се представят толкова добре, колкото сортирането чрез вмъкване. Размерът на входа вече е увеличен приблизително 100 пъти до n = 1000 от n = 30. Разликата вече е осезаема. Сортирането чрез сливане работи 10 пъти по-бързо от сортирането чрез вмъкване. Отново има връзка между производителността на хибридния алгоритъм и рутината qsort(). Това предполага, че qsort() е внедрен по начин, който е повече или по-малко подобен на нашия хибриден алгоритъм, т.е. превключване между различни алгоритми, за да се извлече най-доброто от тях. Накрая входният размер се увеличава до 10^5 (1 Lakh!), което най-вероятно е идеалният размер, използван в практическите сценарии. В сравнение с предишния вход n = 1000, където сортирането чрез сливане изпреварва сортирането с вмъкване, като работи 10 пъти по-бързо, тук разликата е още по-значима. Сортирането чрез сливане побеждава сортирането с вмъкване 100 пъти! Хибридният алгоритъм, който написахме, всъщност изпълнява традиционното сортиране чрез сливане, като работи с 0,01 секунди по-бързо. И накрая, qsort() библиотечната функция най-накрая ни доказва, че внедряването също играе решаваща роля, докато измерва щателно времето за изпълнение, като работи с 3 милисекунди по-бързо! :D