ソートアルゴリズムの漸近分析と比較

マージソートは挿入ソートよりも高速に実行されることは周知の事実です。使用する漸近分析。マージソートの実行時間は 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 程度の入力サイズの場合、このアルゴリズムは正しい選択です。このような大きな入力サイズでは、挿入ソートは非実用的になります。
挿入ソートとマージソートを組み合わせたバージョン: マージソートのロジックを少し調整して、入力サイズが小さい場合の実行時間を大幅に改善しました。ご存知のとおり、マージソートは、要素の並べ替えが十分に簡単になるまで、入力を 2 つの半分に分割します。ただし、入力サイズが「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」を示す 2 つのスペースで区切られた整数と、分析を実行して平均を取得する回数を示す「num_of_times」を入力する必要があります。 (明確化: 「num_of_times」が 10 の場合、上記で指定された各アルゴリズムは 10 回実行され、平均がとられます。これは、指定した入力サイズに対応して入力配列がランダムに生成されるためです。入力配列はすべてソートされる可能性があります。最悪の場合、つまり降順に対応する可能性があります。そのような入力配列の実行時間を回避するため。アルゴリズムは「num_of_times」で実行され、平均がとられます。) CLOCKS_PER_SEC マクロは、所要時間を測定するために使用されます。コンパイル: 上記のコードは Linux 環境 (Ubuntu 16.04 LTS) で作成しました。上記のコードスニペットをコピーします。指定どおりに入力で gcc キーを使用してコンパイルし、ソートアルゴリズムのパワーに感心してください。
結果： ご覧のとおり、入力サイズが小さい場合、挿入ソートはマージソートよりも 2 * 10^-6 秒速くなります。しかし、この時間の差はそれほど重要ではありません。一方、ハイブリッドアルゴリズムと qsort() ライブラリ関数はどちらも挿入ソートと同等のパフォーマンスを発揮します。入力サイズは、n = 30 から n = 1000 まで約 100 倍に増加しました。その違いは明らかです。マージソートは挿入ソートより 10 倍高速に実行されます。ここでも、ハイブリッドアルゴリズムのパフォーマンスと qsort() ルーチンの間には関係があります。これは、qsort() がハイブリッドアルゴリズムと多かれ少なかれ似た方法で実装されていること、つまり、異なるアルゴリズムを切り替えて最大限に活用していることを示唆しています。最後に、入力サイズが 10^5 (100 万!) に増加しました。これは、おそらく実際のシナリオで使用される理想的なサイズです。前の入力 n = 1000 と比較すると、マージソートが挿入ソートよりも 10 倍高速に実行されるため、この違いはさらに顕著になります。マージソートは挿入ソートよりも 100 倍も優れています。実際、私たちが作成したハイブリッドアルゴリズムは、従来のマージソートよりも 0.01 秒速く実行されます。そして最後の qsort() ライブラリ関数は、実行時間を 3 ミリ秒高速化することで実行時間を綿密に測定しながら、実装も重要な役割を果たしていることをついに証明しました。 :D