АСИМПТОТСКА АНАЛИЗА И ПОРЕЂЕЊЕ АЛГОРИТАМА СОРТИРАЊА

Добро је утврђена чињеница да сортирање спајањем ради брже од сортирања уметањем. Коришћење асимптотска анализа . можемо доказати да сортирање спајањем ради за О(нлогн) времена, а сортирање уметањем траје О(н^2). Очигледно је зато што сортирање спајањем користи приступ завади па владај рекурзивним решавањем проблема где сортирање уметањем прати инкрементални приступ. Ако анализирамо временску сложеност још више, сазнаћемо да сортирање уметањем није толико лоше. Изненађујуће сортирање уметањем надмашује сортирање спајањем на мањој величини уноса. То је зато што постоји неколико константи које игноришемо док изводимо временску сложеност. На већим величинама улаза реда 10^4 ово не утиче на понашање наше функције. Али када улазне величине падну испод, рецимо мање од 40, тада константе у једначини доминирају улазном величином 'н'. До сада је добро. Али нисам био задовољан таквом математичком анализом. Као студент рачунарства, морамо веровати у писање кода. Написао сам Ц програм да добијем осећај како се алгоритми такмиче једни против других за различите величине улаза. И такође зашто се ради тако ригорозна математичка анализа на утврђивању сложености времена рада ових алгоритама за сортирање.

Имплементација:

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 овај алгоритам је прави избор. То чини сортирање уметања непрактичним за тако велике улазне величине.
Комбинована верзија сортирања уметањем и сортирања спајањем: Мало сам подесио логику сортирања спајањем да бих постигао знатно боље време рада за мање величине уноса. Као што знамо, сортирање спајањем дели свој унос на две половине док не буде довољно тривијално за сортирање елемената. Али овде када величина улаза падне испод прага као што је 'н' < 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.
Брзо сортирање: Нисам спровео ову процедуру. Ово је библиотечка функција ксорт() која је доступна у . Размотрио сам овај алгоритам да бих знао значај имплементације. Потребна је велика експертиза у програмирању да би се минимизирао број корака и максимално искористили основни језички примитиви да би се алгоритам имплементирао на најбољи могући начин. Ово је главни разлог зашто се препоручује коришћење библиотечких функција. Они су написани да обрађују све и свашта. Оптимизирају у највећој могућој мјери. И пре него што заборавим из своје анализе, ксорт() ради невероватно брзо на практично било којој улазној величини!

Анализа:

Улаз: Корисник мора да наведе колико пута жели да тестира алгоритам који одговара броју тест случајева. За сваки тест случај корисник мора да унесе два цела броја раздвојена размаком који означавају улазну величину 'н' и 'нум_оф_тимес' који означава колико пута жели да покрене анализу и узме просек. (Појашњење: Ако је 'нум_оф_тимес' 10 онда се сваки од алгоритама наведених изнад покреће 10 пута и узима се просек. Ово је учињено зато што се улазни низ генерише насумично у складу са улазном величином коју наведете. Улазни низ би могао да буде сортиран. Наш би могао да одговара најгорем случају десцендирања .тј. у редоследу извођења низа у таквом редоследу рада. Алгоритам се покреће 'број_времена' и узима се просек.) цлоцк() рутина и ЦЛОЦКС_ПЕР_СЕЦ макро од се користе за мерење потребног времена. Компилација: Написао сам горњи код у Линук окружењу (Убунту 16.04 ЛТС). Копирајте горњи исечак кода. Саставите га користећи гцц кључ у улазима како је наведено и дивите се моћи алгоритама за сортирање!
Резултати: Као што можете видети за мале улазне величине сортирање уметањем побеђује сортирање спајањем за 2 * 10^-6 сек. Али ова разлика у времену није толико значајна. С друге стране, и хибридни алгоритам и ксорт() библиотечка функција раде подједнако добро као сортирање уметањем. Величина улаза је сада повећана за приближно 100 пута на н = 1000 са н = 30. Разлика је сада опипљива. Сортирање спајањем ради 10 пута брже од сортирања уметањем. Поново постоји веза између перформанси хибридног алгоритма и ксорт() рутине. Ово сугерише да је ксорт() имплементиран на начин који је мање-више сличан нашем хибридном алгоритму, тј. пребацивање између различитих алгоритама како би се из њих извукло најбоље. Коначно, величина улаза је повећана на 10^5 (1 Лакх!) што је највероватније идеална величина која се користи у практичним сценаријима. У поређењу са претходним уносом н = 1000 где је сортирање спајањем победило сортирање уметањем тако што се ради 10 пута брже, разлика је још значајнија. Сортирање спајањем превазилази сортирање уметањем за 100 пута! Хибридни алгоритам који смо написали у ствари изводи традиционално сортирање спајањем тако што ради 0,01 секунду брже. И на крају ксорт() библиотечка функција нам коначно доказује да имплементација такође игра кључну улогу док пажљиво мери време рада тако што ради 3 милисекунди брже! :Д