{"id":317,"date":"2025-08-09T22:23:05","date_gmt":"2025-08-09T13:23:05","guid":{"rendered":"https:\/\/www.iso-g.com\/?p=317"},"modified":"2026-02-26T20:49:01","modified_gmt":"2026-02-26T11:49:01","slug":"shellsort%e7%a0%94%e7%a9%b6%e3%80%81%e6%9c%80%e9%81%a9%e3%82%ae%e3%83%a3%e3%83%83%e3%83%97%e3%81%af%e6%9c%aa%e8%a7%a3%e6%b1%ba","status":"publish","type":"post","link":"https:\/\/www.iso-g.com\/index.php\/2025\/08\/09\/shellsort%e7%a0%94%e7%a9%b6%e3%80%81%e6%9c%80%e9%81%a9%e3%82%ae%e3%83%a3%e3%83%83%e3%83%97%e3%81%af%e6%9c%aa%e8%a7%a3%e6%b1%ba\/","title":{"rendered":"Shellsort\u7814\u7a76\u3001\u6700\u9069\u30ae\u30e3\u30c3\u30d7\u306f\u672a\u89e3\u6c7a"},"content":{"rendered":"<p>\u300c\u633f\u5165\u30bd\u30fc\u30c8\u306f\u9045\u3044\u3001\u3067\u3082\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u306f\u91cd\u3044\u2026\u300d\u305d\u3093\u306a\u5834\u9762\u3067\u3088\u304f\u52e7\u3081\u3089\u308c\u308b\u306e\u304c\u30b7\u30a7\u30eb\u30bd\u30fc\u30c8\u3002<\/p>\n<p>\u3068\u306f\u3044\u3048\u201c\u30ae\u30e3\u30c3\u30d7\u6570\u5217\u306f\u4f55\u3092\u9078\u3076\uff1f\u8a08\u7b97\u91cf\u306f\uff1f\u201d\u3067\u624b\u304c\u6b62\u307e\u308a\u304c\u3061\u3002<\/p>\n<p>\u3053\u306e\u8a18\u4e8b\u306f\u3001\u56f3\u89e3\u30fb\u5b9f\u88c5\u30fb\u6570\u5217\u306e\u9078\u3073\u65b9\u307e\u3067\u3092\u4e00\u672c\u9053\u3067\u6574\u7406\u3002\u5b66\u7fd2\u7528\u306b\u3082\u5b9f\u52d9\u306e\u5c0f\u914d\u5217\u30c1\u30e5\u30fc\u30cb\u30f3\u30b0\u306b\u3082\u52b9\u304f\u3001\u6301\u3061\u5e30\u308c\u308b\u77e5\u8b58\u306b\u3057\u307e\u3057\u305f\u3002<span class=\"\" data-state=\"closed\"><span class=\"ms-1 inline-flex max-w-full items-center relative top-[-0.094rem] animate-[show_150ms_ease-in]\"><a class=\"flex h-4.5 overflow-hidden rounded-xl px-2 text-[9px] font-medium text-token-text-secondary! bg-[#F4F4F4]! dark:bg-[#303030]! transition-colors duration-150 ease-in-out\" href=\"https:\/\/en.wikipedia.org\/wiki\/Shellsort\" target=\"_blank\" rel=\"noopener\"><span class=\"relative start-0 bottom-0 flex h-full w-full items-center\"><span class=\"flex h-4 w-full items-center justify-between overflow-hidden\"><span class=\"max-w-full grow truncate overflow-hidden text-center\">\u30a6\u30a3\u30ad\u30da\u30c7\u30a3\u30a2<\/span><\/span><\/span><\/a><\/span><\/span><\/p>\n<p><img decoding=\"async\" class=\"alignnone size-medium wp-image-318\" src=\"https:\/\/www.iso-g.com\/wp-content\/uploads\/2025\/08\/android-8129781_640-300x300.jpg\" alt=\"\" width=\"300\" height=\"300\" srcset=\"https:\/\/www.iso-g.com\/wp-content\/uploads\/2025\/08\/android-8129781_640-300x300.jpg 300w, https:\/\/www.iso-g.com\/wp-content\/uploads\/2025\/08\/android-8129781_640-150x150.jpg 150w, https:\/\/www.iso-g.com\/wp-content\/uploads\/2025\/08\/android-8129781_640.jpg 640w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p>\n<hr \/>\n<p><script async src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js?client=ca-pub-5641494373062258\" crossorigin=\"anonymous\"><\/script><br \/>\n<!-- \u8a18\u4e8b\u5185\u5e83\u544a\u30b9\u30af\u30a8\u30a2 --><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block;\" data-ad-client=\"ca-pub-5641494373062258\" data-ad-slot=\"6864483099\" data-ad-format=\"auto\" data-full-width-responsive=\"true\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<h2>1. \u30b7\u30a7\u30eb\u30bd\u30fc\u30c8\u3068\u306f<\/h2>\n<h3>1-1. \u57fa\u672c\u306e\u8003\u3048\u65b9<\/h3>\n<h4>1-1-1. h-\u30bd\u30fc\u30c8\uff08\u9593\u9694\u30bd\u30fc\u30c8\uff09\u306e\u76f4\u611f<\/h4>\n<p>\u30b7\u30a7\u30eb\u30bd\u30fc\u30c8\u306e\u30b3\u30a2\u767a\u60f3\u306f\u3001\u300c<strong>\u96e2\u308c\u305f\u8981\u7d20\u540c\u58eb\u306e\u633f\u5165\u30bd\u30fc\u30c8\u3092\u6bb5\u968e\u7684\u306b\u884c\u3044\u3001\u6700\u5f8c\u306b h=1 \u306e\u633f\u5165\u30bd\u30fc\u30c8\u3067\u4ed5\u4e0a\u3052\u308b<\/strong>\u300d\u3068\u3044\u3046\u3082\u306e\u3067\u3059\u3002<\/p>\n<p>\u914d\u5217\u3092 h \u3054\u3068\u306b\u533a\u5207\u3063\u3066\u201c\u98db\u3073\u98db\u3073\u306e\u5217\uff08h \u9593\u9694\u306e\u90e8\u5206\u5217\uff09\u201d\u3092\u4f5c\u308a\u3001\u305d\u308c\u305e\u308c\u3092\u633f\u5165\u30bd\u30fc\u30c8\u3067\u6574\u5e8f\u3057\u307e\u3059\u3002<\/p>\n<p>\u3059\u308b\u3068\u3001\u9060\u8ddd\u96e2\u306b\u3042\u308b\u8981\u7d20\u3092\u5927\u304d\u304f\u79fb\u52d5\u3067\u304d\u308b\u305f\u3081\u3001\u5e8f\u76e4\u3067\u4e71\u96d1\u3055\uff08\u9006\u8ee2\uff09\u304c\u4e00\u6c17\u306b\u6e1b\u308a\u3001\u6700\u7d42\u30d1\u30b9\uff08h=1\uff09\u306f\u201c\u307b\u307c\u6574\u3063\u305f\u914d\u5217\u201d\u306b\u5bfe\u3059\u308b\u8efd\u3044\u4ed5\u4e0a\u3052\u306b\u306a\u308a\u307e\u3059\u3002<\/p>\n<p><strong>\u6027\u80fd\u3092\u307b\u307c\u6c7a\u3081\u308b\u306e\u304c\u30ae\u30e3\u30c3\u30d7\uff08h \u5024\uff09\u306e\u8a2d\u8a08<\/strong>\u3067\u3059\u3002\u30ae\u30e3\u30c3\u30d7\u306e\u4e26\u3079\u65b9\u30fb\u523b\u307f\u30fb\u6bd4\u7387\u304c\u60aa\u3044\u3068\u3001\u7121\u99c4\u306a\u30d1\u30b9\u3084\u6bd4\u8f03\u304c\u5897\u3048\u3001\u305b\u3063\u304b\u304f\u306e\u6bb5\u968e\u6574\u5e8f\u304c\u76ee\u6e1b\u308a\u3057\u307e\u3059\u3002<\/p>\n<p>\u9006\u306b\u3001\u7de9\u3084\u304b\u306b\u7e2e\u3080\u826f\u3044\u5217\u3092\u4f7f\u3048\u3070\u3001\u6bd4\u8f03\u56de\u6570\u30fb\u79fb\u52d5\u56de\u6570\u3092\u6291\u3048\u3064\u3064\u6700\u7d42\u30d1\u30b9\u306e\u8ca0\u8377\u3092\u6700\u5c0f\u5316\u3067\u304d\u307e\u3059\u3002<\/p>\n<p>\u5b9f\u88c5\u9762\u3067\u306f\u3001<strong>\u201c\u6700\u5f8c\u306e\u30ae\u30e3\u30c3\u30d7\u306f\u5fc5\u305a 1\u201d\u3067\u3042\u308b\u3053\u3068\u304c\u6b63\u3057\u3055\u306e\u524d\u63d0\uff08\u6700\u7d42\u30d1\u30b9\u304c\u901a\u5e38\u306e\u633f\u5165\u30bd\u30fc\u30c8\u306b\u306a\u308b\uff09\u3067\u3001\u30bd\u30fc\u30c8\u306e\u5b89\u5b9a\u6027\u306f\u201c\u306a\u3044\uff08\u4e0d\u5b89\u5b9a\uff09\u201d\u3053\u3068\u306b\u3082\u6ce8\u610f\u304c\u8981\u308a\u307e\u3059\u3002<\/strong><\/p>\n<p><strong>\u30e6\u30fc\u30b9\u30b1\u30fc\u30b9\u306f\u3001\u5c0f\u301c\u4e2d\u898f\u6a21\u914d\u5217\u306e\u4ed5\u4e0a\u3052\u3001\u518d\u5e30\u3084\u8ffd\u52a0\u30e1\u30e2\u30ea\u3092\u907f\u3051\u305f\u3044\u74b0\u5883\u3001\u3042\u308b\u3044\u306f\u4ed6\u306e\u9ad8\u901f\u30bd\u30fc\u30c8\uff08\u30af\u30a4\u30c3\u30af\u7b49\uff09\u306e\u30b5\u30d6\u624b\u9806<\/strong>\u306a\u3069\u3002<\/p>\n<p>\u306a\u304a\u3001\u73fe\u4ee3\u7684\u306a\u89b3\u70b9\u3067\u3082\u300c\u30ae\u30e3\u30c3\u30d7\u6b21\u7b2c\u3067\u8a08\u7b97\u91cf\u306e\u7406\u8ad6\u8a55\u4fa1\u3084\u5b9f\u6e2c\u304c\u5927\u304d\u304f\u63fa\u308c\u308b\u300d\u3053\u3068\u306f\u5e83\u304f\u8a8d\u8b58\u3055\u308c\u3066\u304a\u308a\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u81ea\u4f53\u306e\u7406\u89e3\u3068\u540c\u3058\u304f\u3089\u3044\u30ae\u30e3\u30c3\u30d7\u8a2d\u8a08\u304c\u91cd\u8981\u3067\u3059\u3002<\/p>\n<hr \/>\n<h2>2. \u52d5\u4f5c\u30a4\u30e1\u30fc\u30b8\u3068\u624b\u9806<\/h2>\n<h3>2-1. \u4f8b\u3067\u7406\u89e3\u3059\u308b<\/h3>\n<h4>2-1-1. \u30b9\u30c6\u30c3\u30d7\u56f3\u89e3\u3067\u8ffd\u3046<\/h4>\n<p>\u5177\u4f53\u4f8b\u3067\u6d41\u308c\u3092\u56fa\u3081\u307e\u3059\u3002\u305f\u3068\u3048\u3070\u30ae\u30e3\u30c3\u30d7\u5217\u3092 <strong>5\u21923\u21921<\/strong> \u3068\u3059\u308b\u5834\u5408\u3001\u6700\u521d\u306b\u914d\u5217\u3092 5 \u9593\u9694\u306e 5 \u672c\u306e\u5217\u306b\u5206\u3051\u3001\u305d\u308c\u305e\u308c\u3092\u633f\u5165\u30bd\u30fc\u30c8\u3057\u307e\u3059\uff08\u4f8b\uff1a\u30a4\u30f3\u30c7\u30c3\u30af\u30b9 0,5,10\u2026\uff0f1,6,11\u2026 \u306a\u3069\u306e\u90e8\u5206\u5217\uff09\u3002<\/p>\n<p>\u6b21\u306b\u30ae\u30e3\u30c3\u30d7\u3092 3 \u306b\u7e2e\u3081\u308b\u3068 3 \u672c\u306e\u5217\u306b\u518d\u7de8\u3055\u308c\u3001\u518d\u3073\u5404\u5217\u3092\u633f\u5165\u30bd\u30fc\u30c8\u3002\u6700\u5f8c\u306b <strong>h=1<\/strong> \u3067\u5168\u4f53\u3092\u901a\u5e38\u306e\u633f\u5165\u30bd\u30fc\u30c8\u3068\u3057\u3066\u6574\u5e8f\u3059\u308c\u3070\u5b8c\u4e86\u3067\u3059\u3002<\/p>\n<p>\u3053\u3053\u3067\u5927\u4e8b\u306a\u306e\u306f\u3001**\u300c\u7c97\u3044\u4e26\u3073\u66ff\u3048\u2192\u4e2d\u304f\u3089\u3044\u2192\u7d30\u304b\u3044\u4ed5\u4e0a\u3052\u300d<strong>\u3068\u3044\u3046\u4e09\u6bb5\u306e\u30ea\u30ba\u30e0\u3067\u3059\u3002\u6700\u521d\u306e\u7c97\u3044\u30d1\u30b9\u3067\u5927\u304d\u306a\u30ba\u30ec\u3092\u4e00\u6383\u3057\u3001\u5f8c\u6bb5\u306e\u30d1\u30b9\u3067\u5fae\u7d30\u306a\u30ba\u30ec\u3092\u524a\u3063\u3066\u3044\u304f\u305f\u3081\u3001\u6700\u7d42\u30d1\u30b9\u306e\u30b3\u30b9\u30c8\u304c\u5287\u7684\u306b\u4e0b\u304c\u308b\u306e\u304c\u76f4\u611f\u7684\u306b\u3082\u5206\u304b\u308a\u307e\u3059\u3002<\/strong><\/p>\n<p><strong>\u5404\u30d1\u30b9\u306f\u201c\u305d\u306e\u30ae\u30e3\u30c3\u30d7\u3054\u3068\u306e\u633f\u5165\u30bd\u30fc\u30c8\u201d\u3067\u3042\u308a\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u5358\u7d14\u3067\u3059\u3002<\/strong><\/p>\n<p><strong>\u5b9f\u88c5\u3067\u306f\u3001\u30ae\u30e3\u30c3\u30d7\u5217\u3092\u5927\u304d\u3044\u9806\u306b\u53d6\u308a\u51fa\u3057\u3066\u30eb\u30fc\u30d7\u3057\u3001\u5404\u30ae\u30e3\u30c3\u30d7\u3054\u3068\u306b <code>i=gap..n-1<\/code> \u3067\u8d70\u67fb\u3057\u3066\u201c\u30ae\u30e3\u30c3\u30d7\u5e45\u306e\u633f\u5165\u6cd5\u201d\u3092\u9069\u7528\u3057\u307e\u3059\u3002<\/strong><\/p>\n<p><strong>\u30b9\u30c6\u30c3\u30d7\u5b9f\u4f8b\u306f\u6559\u79d1\u66f8\u7684\u306b\u3082\u3088\u304f\u793a\u3055\u308c\u3001<\/strong>\u300c\u6700\u5f8c\u306e\u30ae\u30e3\u30c3\u30d7\u306f 1\u300d**\u3068\u3044\u3046\u8981\u4ef6\u304c\u4f8b\u793a\u3068\u3068\u3082\u306b\u5f37\u8abf\u3055\u308c\u307e\u3059\u3002<\/p>\n<p>\u3053\u306e\u6d41\u308c\u3092\u982d\u306b\u3044\u308c\u3066\u304a\u304f\u3068\u3001\u5f8c\u6bb5\u306e\u30ae\u30e3\u30c3\u30d7\u8a2d\u8a08\u306e\u8a71\uff08\u306a\u305c 2.25 \u500d\u524d\u5f8c\u304c\u52b9\u304f\u306e\u304b\u3001\u306a\u3069\uff09\u3082\u8179\u843d\u3061\u3057\u3084\u3059\u304f\u306a\u308a\u307e\u3059\u3002<\/p>\n<hr \/>\n<h2>3. \u30ae\u30e3\u30c3\u30d7\uff08\u9593\u9694\uff09\u6570\u5217\u306e\u9078\u3073\u65b9<\/h2>\n<h3>3-1. \u53e4\u5178\u3068\u7406\u8ad6<\/h3>\n<h4>3-1-1. Shell\uff0fKnuth\uff0fHibbard\uff0fPratt<\/h4>\n<p><strong>Shell \u306e\u539f\u6848<\/strong>\u306f\u300c\u230aN\/2\u230b, \u230aN\/4\u230b, \u2026, 1\u300d\u306e\u3088\u3046\u306b\u914d\u5217\u9577\u306b\u4f9d\u5b58\u3057\u3066\u534a\u5206\u305a\u3064\u7e2e\u3081\u308b\u30b7\u30f3\u30d7\u30eb\u306a\u5217\u3067\u3059\u304c\u3001\u6700\u60aa\u8a08\u7b97\u91cf\u306f <strong>\u0398(N\u00b2)<\/strong> \u306b\u53ca\u3073\u307e\u3059\u3002<\/p>\n<p><strong>Hibbard\uff082^k\u22121\uff09\u3084 Papernov\u2013Stasevich \u306a\u3069\u5947\u6570\u4e2d\u5fc3\u30fb\u5e7e\u4f55\u5b66\u7684\u306b\u5897\u3048\u308b\u5217\u306f\u3001\u53e4\u5178\u7684\u7406\u8ad6\u3067O(N^{3\/2})<\/strong> \u7a0b\u5ea6\u306e\u4e0a\u754c\u304c\u77e5\u3089\u308c\u3001\u5b9f\u6e2c\u3067\u3082\u539f\u6848\u3088\u308a\u826f\u3044\u3053\u3068\u304c\u591a\u3044\u3067\u3059\u3002<\/p>\n<p>**Knuth\uff08(3^k\u22121)\/2\uff09**\u306f\u5b9f\u88c5\u3057\u3084\u3059\u304f\u3001\u5b9f\u52d9\u3067\u3082\u3088\u304f\u4f7f\u308f\u308c\u308b\u5b9a\u756a\u3002\u7406\u8ad6\u9762\u3067\u306f **Pratt\uff083-smooth \u6570\uff1a2^p3^q\uff09<strong>\u306e\u5217\u3092\u4f7f\u3046\u3068\u3001\u65e2\u77e5\u306e\u4e2d\u3067\u6700\u826f\u306e\u6700\u60aa\u8a08\u7b97\u91cf O(N log\u00b2N) \u3092\u9054\u6210\u3057\u307e\u3059\uff08\u305f\u3060\u3057\u523b\u307f\u304c\u7d30\u304b\u3059\u304e\u3066\u30d1\u30b9\u6570\u304c\u5897\u3048\u304c\u3061\u3067\u3001\u5b9f\u7528\u4e0a\u306f\u91cd\u304f\u306a\u308a\u3084\u3059\u3044\uff09\u3002<\/strong><\/p>\n<p><strong>\u7dcf\u3058\u3066\u3001<\/strong>\u300c1 \u3092\u5fc5\u305a\u542b\u3080\u964d\u9806\u5217\u300d<strong>\u3067\u3042\u308b\u3053\u3068\u306f\u6b63\u3057\u3055\u306e\u6761\u4ef6\u3067\u3001\u5e73\u5747\u6027\u80fd\u306f<\/strong>\u201c\u5217\u306e\u5f62\u72b6\uff08\u6bd4\u7387\u306e\u6ed1\u3089\u304b\u3055\u30fb\u4e92\u3044\u306e\u516c\u7d04\u6570\u306e\u5c0f\u3055\u3055\u30fb\u5947\u5076\u69cb\u6210\uff09\u201d**\u306b\u5f37\u304f\u4f9d\u5b58\u3057\u307e\u3059\u3002<\/p>\n<p>\u7406\u8ad6\u6700\u9069\u3084\u5e73\u5747\u8a08\u7b97\u91cf\u306f\u4eca\u306a\u304a\u7814\u7a76\u7d99\u7d9a\u4e2d\u3067\u3001<strong>\u5b9f\u52d9\u3067\u306f\u6027\u80fd\u3068\u5b9f\u88c5\u5bb9\u6613\u6027\u306e\u6298\u308a\u5408\u3044<\/strong>\u3067\u5217\u3092\u9078\u3076\u306e\u304c\u73fe\u5b9f\u89e3\u3067\u3059\u3002<\/p>\n<hr \/>\n<p><script async src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js?client=ca-pub-5641494373062258\" crossorigin=\"anonymous\"><\/script><br \/>\n<!-- \u8a18\u4e8b\u5185\u5e83\u544a\u30b9\u30af\u30a8\u30a2 --><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block;\" data-ad-client=\"ca-pub-5641494373062258\" data-ad-slot=\"6864483099\" data-ad-format=\"auto\" data-full-width-responsive=\"true\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<h2>4. \u5b9f\u52d9\u3067\u4f7f\u308f\u308c\u308b\u6570\u5217<\/h2>\n<h3>4-1. \u5b9f\u8df5\u6d3e\u306e\u5b9a\u756a<\/h3>\n<h4>4-1-1. Tokuda\u30fbCiura\u30fb\u6700\u65b0\u03b3\u306e\u6bd4\u8f03<\/h4>\n<p>\u73fe\u5834\u3067\u4eba\u6c17\u304c\u9ad8\u3044\u306e\u306f <strong>Tokuda \u5217<\/strong>\u3068 <strong>Ciura \u5217<\/strong>\u3067\u3059\u3002<strong>Ciura\uff081,4,10,23,57,132,301,701\u2026\uff09\u306f\u4e71\u629e\u914d\u5217\u306b\u5bfe\u3059\u308b\u5e73\u5747\u6bd4\u8f03\u56de\u6570\u304c\u826f\u597d<\/strong>\u3068\u3044\u3046\u7d4c\u9a13\u7684\u8a55\u4fa1\u304c\u5e83\u304f\u5171\u6709\u3055\u308c\u3001<strong>701 \u4ee5\u964d\u306f\u6982\u306d \u00d72.25 \u500d\u3067\u62e1\u5f35<\/strong>\u3059\u308b\u306e\u304c\u5b9f\u7528\u4e0a\u306e\u5b9a\u756a\u3067\u3059\u3002<\/p>\n<p><strong>Tokuda<\/strong> \u306f\u518d\u5e30\u5f0f <strong>h\u2019\u2081=1, h\u2019\u2096=2.25\u00b7h\u2019\u2096\u208b\u2081+1, h\u2096=\u2308h\u2019\u2096\u2309<\/strong> \u3067\u751f\u6210\u3067\u304d\u3001**\u201c\u5b9f\u88c5\u304c\u7c21\u5358\u3067\u5b9f\u52d9\u5411\u3051\u306b\u63a8\u5968\u201d**\u3068\u3055\u308c\u307e\u3059\u3002<\/p>\n<p>\u3055\u3089\u306b\u8fd1\u5e74\u306f\u3001Tokuda \u3092\u9023\u7d9a\u5316\u3057\u305f **\u03b3-sequence\uff08Lee, 2021\uff09<strong>\u306e\u3088\u3046\u306b\u3001\u5b9f\u9a13\u7684\u306b Tokuda \u3092\u4e0a\u56de\u308b\u6bd4\u8f03\u56de\u6570\u3092\u793a\u3059\u5831\u544a\u3082\u3042\u308a\u307e\u3059\uff08\u914d\u5217\u30b5\u30a4\u30ba\u3084\u8a55\u4fa1\u95a2\u6570\u306b\u4f9d\u5b58\uff09\u3002<\/strong><\/p>\n<p><strong>\u7d50\u8ad6\u3068\u3057\u3066\u3001<\/strong>\u300c\u307e\u305a Ciura or Tokuda \u3092\u63a1\u7528\u3057\u3001\u30d7\u30ed\u30d5\u30a1\u30a4\u30eb\u3067 \u03b3 \u306a\u3069\u3092\u5f53\u3066\u3066\u307f\u308b\u300d**\u306e\u304c\u7121\u96e3\u306a\u5c0e\u5165\u624b\u9806\u3067\u3059\u3002<\/p>\n<p>\u8981\u4ef6\uff08\u6700\u5927 N\u3001\u5b89\u5b9a\u6027\u4e0d\u8981\u3001\u30b3\u30fc\u30c9\u9577\u3001\u53ef\u642c\u6027\u306a\u3069\uff09\u306b\u3088\u3063\u3066\u4f7f\u3044\u5206\u3051\u307e\u3057\u3087\u3046\u3002<\/p>\n<p>\u7279\u306b\u7d44\u307f\u8fbc\u307f\u3084\u5c0f\u914d\u5217\u3067\u306f\u3001<strong>\u77ed\u3044\u5217\u3067\u30aa\u30fc\u30d0\u30fc\u30d8\u30c3\u30c9\u3092\u6291\u3048\u3084\u3059\u3044 Ciura\/Tokuda<\/strong>\u304c\u5805\u5b9f\u3067\u3059\u3002<\/p>\n<blockquote><p>\u53c2\u8003\uff08\u4e00\u6b21\u60c5\u5831\u30fb\u6700\u65b0\u52d5\u5411\uff09<br \/>\n\u30fbCiura\uff082001\uff09\u5e73\u5747\u30b1\u30fc\u30b9\u6700\u826f\u30af\u30e9\u30b9\u306e\u5b9f\u9a13\u7684\u7d50\u679c\u3002<br \/>\n\u30fbLee\uff082021\uff09Tokuda \u6539\u826f\u306e <strong>\u03b3-sequence<\/strong> \u63d0\u6848\uff08\u5e73\u5747\u6bd4\u8f03\u56de\u6570\u6539\u5584\u306e\u5831\u544a\uff09\u3002<\/p><\/blockquote>\n<hr \/>\n<h2>5. \u8a08\u7b97\u91cf\u306e\u73fe\u5728\u5730<\/h2>\n<h3>5-1. \u3069\u3053\u307e\u3067\u901f\u3044\u306e\u304b<\/h3>\n<h4>5-1-1. \u6700\u60aa\u30fb\u5e73\u5747\u30fb\u672a\u89e3\u6c7a\u306e\u6574\u7406<\/h4>\n<p><strong>\u8a08\u7b97\u91cf\u306f\u30ae\u30e3\u30c3\u30d7\u306b\u4f9d\u5b58<\/strong>\u3057\u307e\u3059\u3002\u53e4\u5178\u5217\uff08Shell \u306a\u3069\uff09\u3067\u306f\u6700\u60aa <strong>\u0398(N\u00b2)<\/strong> \u304c\u907f\u3051\u3089\u308c\u307e\u305b\u3093\u3002<\/p>\n<p>\u4e00\u65b9\u3067 <strong>Pratt \u306e 3-smooth \u5217<\/strong>\u306f\u7406\u8ad6\u4e0a<strong>\u6700\u60aa O(N log\u00b2N)<\/strong> \u3092\u9054\u6210\u3057\u3001\u73fe\u6642\u70b9\u306e<strong>\u65e2\u77e5\u306e\u6700\u826f\u4e0a\u754c<\/strong>\u3067\u3059\u3002<\/p>\n<p>\u305f\u3060\u3057\u30d1\u30b9\u6570\u304c\u5897\u3048\u5b9f\u7528\u4e0a\u306f\u9045\u304f\u306a\u308a\u304c\u3061\u3002<strong>Hibbard \u306a\u3069\u591a\u304f\u306e\u5e7e\u4f55\u5217\u3067\u306f O(N^{3\/2})<\/strong> \u7a0b\u5ea6\u306e\u4e0a\u754c\u304c\u793a\u3055\u308c\u3001\u53e4\u5178\u7814\u7a76\u3067\u3082\u652f\u6301\u3055\u308c\u3066\u3044\u307e\u3059\u3002<\/p>\n<p><strong>\u5e73\u5747\u8a08\u7b97\u91cf\uff08\u4e71\u629e\u914d\u5217\u3067\u306e\u6bd4\u8f03\u56de\u6570\u306e\u671f\u5f85\u5024\uff09\u306f\u5217\u3054\u3068\u306b\u6319\u52d5\u304c\u5909\u308f\u308a\u3001\u6700\u9069\u5217\u306e\u5b58\u5728\u30fb\u4e00\u822c\u5f62\u306e\u5e73\u5747\u30aa\u30fc\u30c0\u30fc\u306f\u4eca\u3082\u30aa\u30fc\u30d7\u30f3\u306a\u5074\u9762\u304c\u3042\u308a\u307e\u3059\u3002<\/strong><\/p>\n<p><strong>\u5b9f\u52d9\u7684\u306b\u306f\u3001\u300c\u9023\u7d9a\u6bd4\u304c\u7d04 2.2\u301c2.3\u300d\u3067\u6ed1\u3089\u304b\u306b\u7e2e\u3080\u5217\uff08Tokuda\uff0fCiura \u62e1\u5f35\u306a\u3069\uff09\u304c\u6bd4\u8f03\u56de\u6570\u30fb\u79fb\u52d5\u56de\u6570\u306e\u30d0\u30e9\u30f3\u30b9\u304c\u826f\u597d<\/strong>\u3068\u3044\u3046\u7d4c\u9a13\u5247\u304c\u591a\u304f\u306e\u5b9f\u9a13\u3067\u89b3\u5bdf\u3055\u308c\u3066\u3044\u307e\u3059\u3002<\/p>\n<p>\u91cd\u8981\u306a\u306e\u306f\u3001<strong>\u30aa\u30fc\u30c0\u30fc\u306e\u7406\u8ad6\u6700\u826f\uff1d\u5e38\u306b\u5b9f\u6e2c\u6700\u901f\u3067\u306f\u306a\u3044<\/strong>\u70b9\u3067\u3059\u3002<\/p>\n<p>\u30e1\u30e2\u30ea\u968e\u5c64\u30fb\u5206\u5c90\u4e88\u6e2c\u30fb\u30ad\u30e3\u30c3\u30b7\u30e5\u5c40\u6240\u6027\u30fb\u8a00\u8a9e\u5b9f\u88c5\u306e\u30b3\u30b9\u30c8\u3092\u8e0f\u307e\u3048\u3001<strong>\u30d7\u30ed\u30d5\u30a1\u30a4\u30eb\u3067\u201c\u81ea\u5206\u306e\u30c7\u30fc\u30bf\u201d\u306b\u6700\u9069\u5316\u3059\u308b<\/strong>\u306e\u304c\u6700\u77ed\u8def\u306b\u306a\u308a\u307e\u3059\u3002<\/p>\n<hr \/>\n<h2>6. \u5b9f\u88c5\u3068\u30c1\u30e5\u30fc\u30cb\u30f3\u30b0<\/h2>\n<h3>6-1. Python\u3067\u62bc\u3055\u3048\u308b<\/h3>\n<h4>6-1-1. \u5b9f\u52d9\u5411\u3051\u306e\u5b9f\u88c5\u30fb\u6ce8\u610f\u70b9<\/h4>\n<p>\u5b9f\u88c5\u306f<strong>\u30ae\u30e3\u30c3\u30d7\u5217\u306e\u30eb\u30fc\u30d7\u5185\u3067\u201c\u30ae\u30e3\u30c3\u30d7\u5e45\u306e\u633f\u5165\u30bd\u30fc\u30c8\u201d\u3092\u9069\u7528\u3059\u308b\u3060\u3051\u3067\u3059\u3002<\/strong><\/p>\n<p><strong>\u5178\u578b\u4f8b\u306f Ciura\uff1a<code>[701,301,132,57,23,10,4,1]<\/code> \u3092\u964d\u9806<\/strong>\u306b\u56de\u3057\u3001\u5404 <code>gap<\/code> \u306b\u5bfe\u3057\u3066 <code>for i in range(gap, n)<\/code> \u3068\u3057\u3001<code>temp=a[i]<\/code> \u3092\u4fdd\u6301\u2192 <code>j<\/code> \u3092 <code>gap<\/code> \u305a\u3064\u623b\u3057\u306a\u304c\u3089 <code>a[j-gap] &gt; temp<\/code> \u306e\u9593\u30b7\u30d5\u30c8\u2192\u6700\u5f8c\u306b <code>a[j]=temp<\/code>\u3002<\/p>\n<p><strong>\u6ce8\u610f\u70b9<\/strong>\u306f\u3001(1) <strong><code>gap=1<\/code> \u3092\u5fc5\u305a\u542b\u3081\u308b<\/strong>\uff08\u6574\u5217\u306e\u4fdd\u8a3c\uff09\u3001<\/p>\n<p>(2) <strong>\u5b89\u5b9a\u3067\u306f\u306a\u3044<\/strong>\u305f\u3081\u7b49\u5024\u306e\u76f8\u5bfe\u9806\u5e8f\u306f\u4fdd\u6301\u3055\u308c\u306a\u3044\u3001<\/p>\n<p>(3) <strong>\u30ae\u30e3\u30c3\u30d7\u306f\u964d\u9806<\/strong>\uff08\u5c0f\u2192\u5927\u306b\u3059\u308b\u3068\u524d\u6bb5\u306e\u52b9\u679c\u304c\u76f8\u6bba\u3055\u308c\u3084\u3059\u3044\uff09\u3001<\/p>\n<p>(4) <strong>\u30c6\u30b9\u30c8\u306f4\u7a2e<\/strong>\uff08\u4e71\u629e\u30fb\u9006\u9806\u30fb\u7b49\u5024\u591a\u3081\u30fb\u307b\u307c\u6574\u5217\uff09\u3067\u6700\u4f4e\u9650\u56de\u3059\u3001<\/p>\n<p>(5) <strong>\u30d7\u30ed\u30d5\u30a1\u30a4\u30eb\u524d\u63d0<\/strong>\u3067\u30ae\u30e3\u30c3\u30d7\u5217\u3092\u5dee\u3057\u66ff\u3048\u53ef\u80fd\u306b\u4f5c\u308b\u3001\u306e5\u70b9\u3002<\/p>\n<p>\u3055\u3089\u306b\u5b9f\u52d9\u3067\u306f\u3001<strong>\u3042\u308b\u95be\u5024\u4ee5\u4e0b\u306e\u5c0f\u914d\u5217<\/strong>\u306f\u30b7\u30a7\u30eb\u30bd\u30fc\u30c8\u3067\u4ed5\u4e0a\u3052\u3001<strong>\u305d\u308c\u4ee5\u4e0a\u306f\u5225\u30bd\u30fc\u30c8<\/strong>\uff08\u30af\u30a4\u30c3\u30af\/\u30d2\u30fc\u30d7\/\u30c6\u30a3\u30e0\u30bd\u30fc\u30c8\u7b49\uff09\u3068\u3044\u3046<strong>\u30cf\u30a4\u30d6\u30ea\u30c3\u30c9<\/strong>\u304c\u5b9a\u756a\u3002<\/p>\n<p><strong>qsort \u306e\u7d44\u307f\u8fbc\u307f\u5b9f\u88c5\uff08uClibc \u306a\u3069\uff09\u3067\u63a1\u7528\u4f8b<\/strong>\u304c\u3042\u308b\u306e\u306f\u3001\u201c<strong>\u30b3\u30fc\u30c9\u304c\u77ed\u3044\u3001\u30b9\u30bf\u30c3\u30af\u3092\u4f7f\u308f\u306a\u3044\u3001\u8ffd\u52a0\u30e1\u30e2\u30ea O(1)<\/strong>\u201d\u3068\u3044\u3046\u7279\u6027\u304c\u7406\u7531\u3067\u3059\u3002<\/p>\n<p>\u307e\u305a\u306f <strong>Ciura<\/strong> \u304b <strong>Tokuda<\/strong> \u3092\u5b9f\u88c5\u3057\u3066\u30d9\u30fc\u30b9\u30e9\u30a4\u30f3\u3092\u4f5c\u308a\u3001\u5bfe\u8c61\u30c7\u30fc\u30bf\u3067 <strong>\u03b3-sequence \u7b49\u3092 AB \u30c6\u30b9\u30c8<\/strong>\u3059\u308b\u6d41\u308c\u3092\u63a8\u5968\u3057\u307e\u3059\u3002<\/p>\n<hr \/>\n<h2>7. \u4f7f\u3044\u3069\u3053\u308d\u3068FAQ<\/h2>\n<h3>7-1. \u3044\u3064\u9078\u3076\uff1f<\/h3>\n<h4>7-1-1. \u5b89\u5b9a\u6027\uff0f\u5c0f\u914d\u5217\uff0f\u30cf\u30a4\u30d6\u30ea\u30c3\u30c9\u6d3b\u7528<\/h4>\n<p><strong>Q1\uff1a\u5b89\u5b9a\u3067\u3059\u304b\uff1f<\/strong>\u2015<strong>\u4e0d\u5b89\u5b9a<\/strong>\u3067\u3059\u3002\u7b49\u5024\u306e\u76f8\u5bfe\u9806\u5e8f\u304c\u91cd\u8981\u306a\u3089\u5b89\u5b9a\u30bd\u30fc\u30c8\uff08\u30de\u30fc\u30b8\/TimSort \u306a\u3069\uff09\u3092\u9078\u3073\u307e\u3057\u3087\u3046\u3002<\/p>\n<p><strong>Q2\uff1a\u3069\u3093\u306a\u5834\u9762\u3067\u5f37\u3044\uff1f<\/strong>\u2015<strong>\u5c0f\u914d\u5217\u306e\u4ed5\u4e0a\u3052<\/strong>\u3001<strong>\u518d\u5e30\u3084\u4f8b\u5916\u30b3\u30b9\u30c8\u3092\u907f\u3051\u305f\u3044\u7d44\u307f\u8fbc\u307f<\/strong>\u3001<strong>\u5272\u308a\u8fbc\u307f\u304c\u5165\u308a\u3084\u3059\u3044\u74b0\u5883<\/strong>\u3001<strong>qsort \u306e\u5b9f\u88c5\u5dee\u3057\u66ff\u3048<\/strong>\u306a\u3069\u3067\u4f7f\u308f\u308c\u307e\u3059\u3002\u5927\u898f\u6a21\u30fb\u53b3\u5bc6\u306a\u6700\u60aa\u4fdd\u8a3c\u304c\u5fc5\u8981\u306a\u3089\u5225\u624b\u6bb5\u304c\u7121\u96e3\u3002<\/p>\n<p><strong>Q3\uff1a\u30ae\u30e3\u30c3\u30d7\u306f\u591a\u3044\u307b\u3069\u901f\u3044\uff1f<\/strong>\u2015\u3084\u307f\u304f\u3082\u306b\u5897\u3084\u3059\u3068<strong>\u30d1\u30b9\u306e\u30aa\u30fc\u30d0\u30fc\u30d8\u30c3\u30c9<\/strong>\u304c\u652f\u914d\u3057\u3066\u9006\u52b9\u679c\u3002<strong>\u201c\u7de9\u3084\u304b\u306b\u7e2e\u3080\u6bd4\u7387\uff08\u22482.2\u301c2.3\uff09\u201d\u3068\u4e92\u3044\u306b\u5c0f\u3055\u306a\u516c\u7d04\u6570<\/strong>\u3092\u6301\u3064\u5217\u304c\u7d4c\u9a13\u7684\u306b\u597d\u6210\u7e3e\u3067\u3059\u3002<\/p>\n<p><strong>Q4\uff1a\u3069\u306e\u5217\u304c\u6700\u9069\uff1f<\/strong>\u2015<strong>\u672a\u89e3\u6c7a\u9818\u57df<\/strong>\u3067\u3059\u3002<strong>Ciura\uff0fTokuda\uff0fPratt\uff0f\u03b3<\/strong> \u306a\u3069\u5019\u88dc\u3092<strong>\u30d7\u30ed\u30d5\u30a1\u30a4\u30eb\u3067\u6bd4\u8f03<\/strong>\u3059\u308b\u306e\u304c\u5b9f\u52d9\u7684\u6700\u9069\u5316\u3002<\/p>\n<p><strong>Q5\uff1a\u4ed6\u30bd\u30fc\u30c8\u3068\u306e\u95a2\u4fc2\u306f\uff1f<\/strong>\u2015<strong>\u30cf\u30a4\u30d6\u30ea\u30c3\u30c9<\/strong>\u304c\u738b\u9053\u3002\u5927\u67a0\u3067\u9ad8\u901f\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u4f7f\u3044\u3001<strong>\u95be\u5024\u4ee5\u4e0b\u3067\u30b7\u30a7\u30eb\u30bd\u30fc\u30c8\u306b\u5207\u66ff<\/strong>\u3048\u308b\u3068\u3001\u5206\u5c90\u4e88\u6e2c\u30fb\u30ad\u30e3\u30c3\u30b7\u30e5\u30fb\u95a2\u6570\u547c\u3073\u51fa\u3057\u306e\u30b3\u30b9\u30c8\u3092\u6291\u3048\u3089\u308c\u307e\u3059\u3002<\/p>\n<p>\u30ad\u30e2\u306f\u300c<strong>\u81ea\u5206\u306e\u30c7\u30fc\u30bf\u3067\u6e2c\u308b<\/strong>\u300d\u3002\u6559\u79d1\u66f8\u7684\u306a\u6700\u60aa\u30aa\u30fc\u30c0\u30fc\u3084\u4e00\u822c\u8ad6\u3060\u3051\u3067\u306f\u6700\u901f\u69cb\u6210\u306f\u6c7a\u307e\u308a\u307e\u305b\u3093\u3002<\/p>\n<hr \/>\n<p class=\"spacer\">&nbsp;<\/p>\n<p><script async src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js?client=ca-pub-5641494373062258\" crossorigin=\"anonymous\"><\/script><br \/>\n<!-- \u8a18\u4e8b\u5185\u5e83\u544a\u30b9\u30af\u30a8\u30a2 --><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block;\" data-ad-client=\"ca-pub-5641494373062258\" data-ad-slot=\"6864483099\" data-ad-format=\"auto\" data-full-width-responsive=\"true\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n","protected":false},"excerpt":{"rendered":"\u300c\u633f\u5165\u30bd\u30fc\u30c8\u306f\u9045\u3044\u3001\u3067\u3082\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\u306f\u91cd\u3044\u2026\u300d\u305d\u3093\u306a\u5834\u9762\u3067\u3088\u304f\u52e7\u3081\u3089\u308c\u308b\u306e\u304c\u30b7\u30a7\u30eb\u30bd\u30fc\u30c8\u3002 \u3068\u306f\u3044\u3048\u201c\u30ae\u30e3\u30c3\u30d7\u6570\u5217\u306f\u4f55\u3092\u9078\u3076\uff1f\u8a08\u7b97\u91cf\u306f\uff1f\u201d\u3067\u624b\u304c\u6b62\u307e\u308a\u304c\u3061\u3002 \u3053\u306e\u8a18\u4e8b\u306f\u3001\u56f3\u89e3\u30fb\u5b9f\u88c5\u30fb\u6570\u5217\u306e\u9078\u3073\u65b9\u307e\u3067\u3092\u4e00\u672c\u9053\u3067\u6574\u7406\u3002\u5b66\u7fd2 [&hellip;]","protected":false},"author":1,"featured_media":318,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-317","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-3"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/posts\/317","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/comments?post=317"}],"version-history":[{"count":3,"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/posts\/317\/revisions"}],"predecessor-version":[{"id":744,"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/posts\/317\/revisions\/744"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/media\/318"}],"wp:attachment":[{"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/media?parent=317"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/categories?post=317"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.iso-g.com\/index.php\/wp-json\/wp\/v2\/tags?post=317"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}