BVB Source Codes

Algorithm-Implementations Show shell_sort.hpp Source code

Return Download Algorithm-Implementations: download shell_sort.hpp Source code - Download Algorithm-Implementations Source code - Type:.hpp
  1. #pragma once
  2.  
  3. #include <iostream>
  4.  
  5. struct knuth_gap_generator_t {
  6.     template<typename T>
  7.     static int next_gap_value(T gap) {
  8.         return 3 * gap + 1;
  9.     }
  10.  
  11.     template<typename T>
  12.     static int prev_gap_value(T gap) {
  13.         return (gap - 1) / 3;
  14.     }
  15. };
  16.  
  17. template<class GapGenerator, class RandomAccessIterator>
  18. inline int init_gap(RandomAccessIterator begin, RandomAccessIterator end) {
  19.     typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
  20.  
  21.     difference_type gap = 0;
  22.     const difference_type size = std::distance(begin, end);
  23.     while (true) {
  24.         const difference_type next = GapGenerator::next_gap_value(gap);
  25.         if (next > size) {
  26.             break;
  27.         }
  28.  
  29.         gap = next;
  30.     }
  31.  
  32.     return gap;
  33. }
  34.  
  35. template<class RandomAccessIterator>
  36. void insertion_sort(RandomAccessIterator begin, RandomAccessIterator end, typename std::iterator_traits<RandomAccessIterator>::difference_type gap = 1) {
  37.     for (RandomAccessIterator i = begin + gap; i != end; ++i) {
  38.         for (RandomAccessIterator j = i; j >= begin + gap; j -= gap) {
  39.             if (*j < *(j - gap)) {
  40.                 std::iter_swap(j, j - gap);
  41.             } else {
  42.                 break;
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. template<class RandomAccessIterator, class GapGenerator = knuth_gap_generator_t>
  49. void shell_sort(RandomAccessIterator begin, RandomAccessIterator end) {
  50.     int gap = init_gap<GapGenerator>(begin, end);
  51.  
  52.     while (gap >= 1) {
  53.         insertion_sort(begin, end, gap);
  54.         gap = GapGenerator::prev_gap_value(gap);
  55.     }
  56. }
  57.  
downloadshell_sort.hpp Source code - Download Algorithm-Implementations Source code
Related Source Codes/Software:
raty - 2017-04-22
RDVTabBarController - Highly customizable tabBar and tabBarController fo... 2017-04-22
material-icon-lib - Library containing over 1500 material vector icons... 2017-04-21
httpdiff - Perform the same request against two HTTP servers ... 2017-04-21
jquerytools - The missing UI library for the Web ... 2017-04-21
mcrouter - Mcrouter is a memcached protocol router for scalin... 2017-04-22
dynomite - A generic dynamo implementation for different k-v ... 2017-04-22
kityminder - Baidu brain figure 2017-04-22
llvm - Mirror of official llvm git repository located at ... 2017-04-22
RBBAnimation - Block-based animations made easy, comes with easin... 2017-04-22
ied - 2017-04-29
Nimble - A Matcher Framework for Swift and Objective-C 2017-04-29
MHVideoPhotoGallery - A Photo and Video Gallery 2017-04-29
shoulda-matchers - Collection of testing matchers extracted from Shou... 2017-04-29
Android-SlideExpandableListView - A better ExpandableListView, with animated expanda... 2017-04-29
AppSales-Mobile - App Sales allows iPhone and Mac App Store develope... 2017-04-29
react-templates - Light weight templates for react ... 2017-04-28
afterglow-theme - A minimal dark Theme for Sublime Text 2 and 3 2017-04-28
jwt-go - Golang implementation of JSON Web Tokens (JWT) 2017-04-28
DeerResume - Tool MarkDown online resume, online preview, edit,... 2017-04-28

 Back to top