Shellsort

デジタル大辞泉

シェル‐ソート【shell sort】

読み方：しぇるそーと

コンピューターでデータをある基準によって並べかえるソートで使われるアルゴリズムの一。挿入ソートを改良し、隣り合った要素だけを比較するのではなく、ある適当な間隔で取り出した要素列に対し、挿入ソートを行い、徐々にその間隔を詰めて同じ走査を繰り返す。

IT用語辞典バイナリ

シェルソート

【英】shell sort

シェルソートとは、ソート（整列）のアルゴリズムの一種で、挿入ソートを改良したアルゴリズムのことである。アメリカのコンピュータ科学者ドナルド・シェル（Donald Shell）によって考案された。

シェルソートの原型となっている挿入ソートは、もっとも単純なアルゴリズムの一つで、原理上ランダムな並びのデータを整列させるには効率が悪いという欠点がある。シェルソートでは、初めに大きなデータと小さなデータとを大まかに分け、その後に挿入ソートを行う、という手順を踏むことで、挿入ソートの効率化を図ろうとするものである。

シェルソートでは、まず一定間隔の全てのデータの組み合わせに対して小さなデータが前にくるよう交換処理を行う。これを、間隔を小さくしながら隣同士の交換になるまで同じことを繰り返し、最後には挿入ソートを行う。

なお、同じデータの順番がソート前後によって変化しないソート手法を「安定なソート」と言うが、挿入ソートとは違い、シェルソートは安定なソートではない。

情報処理のほかの用語一覧

アルゴリズム：

整列  セレクションソート  選択ソート  シェルソート  識別子  巡回セールスマン問題  昇順

>>アルゴリズムカテゴリの他の用語

ウィキペディア

シェルソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/06 14:29 UTC 版)

シェルソート

間隔 23, 10, 4, 1 でのシェルソートの実行
クラス	ソート
データ構造	配列
最悪計算時間	間隔に依存
最良計算時間	$\mathrm {O} (n\log n)$ 間隔5, 3, 1のシェルソートにおける要素の交換を示した図 シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、1959年にドナルド・シェルが開発したソートのアルゴリズム。挿入ソートの一般化であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。 アルゴリズム アルゴリズムの基本は挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という長所を持つが、隣接した要素同士しか比較・交換を行わないため、あまり整列されていないデータに対しては低速であった。 シェルソートは、「飛び飛びの列を繰り返しソートして、配列を大まかに整列された状態に近づけていく」ことにより、挿入ソートの長所を活かしたものである。 アルゴリズムの概略は次のとおりである。 適当な間隔 $h$ を決める（hの決め方については後述） 間隔 $h$ をあけて取り出したデータ列に挿入ソートを適用する 間隔 $h$ を狭めて、2.を適用する操作を繰り返す $h=1$ になったら、最後に挿入ソートを適用して終了 動作例 初期データ: 8 3 1 2 7 5 6 4 この例では、間隔hを4→2→1（2の累乗）とする。 まず、h=4とする。色の同じ部分は、同じグループのデータ列である。 8 3 1 2 7 5 6 4 同じグループ内で挿入ソートし、h=2にする。 7 3 1 2 8 5 6 4 同じグループ内で挿入ソートし、h=1にする。 1 2 6 3 7 4 8 5 間隔が1ということは、全体が同じ1つのグループということである。これを挿入ソートする。 1 2 3 4 5 6 7 8 間隔の決め方 シェルソートの実行時間（時間計算量）は、比較時に選ぶ間隔hによって大きく異なる。 前節の例ではhを2の累乗としたが、この場合、最悪計算量が$\mathrm {O} (n^{2})$となってしまう。各周回で同じ位置の要素ばかりが比較交換されるため、h=1となった段階で「全体が大まかに整列されている」という仮定が成り立たなくなるためである。 より効率の良い（計算量の少ない）ソートを行うために、様々な間隔が提案されてきた。以下の表は、間隔を決定するための数列の例である。（$n$は要素数） 数列の一般項 (k ≥ 1) 実際の数列 最悪計算時間 備考 $\left\lfloor {\frac {n}{2^{k}}}\right\rfloor$ $\left\lfloor {\frac {n}{2}}\right\rfloor ,\left\lfloor {\frac {n}{4}}\right\rfloor ,\ldots ,1$ $\mathrm {O} (n^{2})$ ドナルド・シェルが最初に考案した数列。 $n$が2の累乗の時、上記動作例と同一。 ${\frac {3^{k}-1}{2}}$　（$\left\lceil {\frac {n}{3}}\right\rceil$以下） $1,4,13,40,121,\ldots$ $\mathrm {O} \left(n^{\frac {3}{2}}\right){=}\mathrm {O} (n^{1.5})$ ドナルド・クヌース、 1973 Pratt, 1971に基づく。 平均計算時間は $\mathrm {O} (n^{1.25})$。 $A_{0}{=}1,A_{k}{=}4^{k}+3\cdot 2^{k-1}+1$ $1,8,23,77,281,\ldots$ $\mathrm {O} \left(n^{\frac {4}{3}}\right){=}\mathrm {O} (n^{1.33\ldots })$ Sedgewick, 1982 $2^{p}3^{q}$ ($p\geq 0,q\geq 0$) $1,2,3,4,6,8,9,12,\ldots$ $\mathrm {O} \left(n\log ^{2}n\right)$ Pratt, 1971 既知の数列で最悪計算時間が最小となるもの。 間隔の狭め方が細かすぎるため、実用性は低い。 これらの数列をソートの間隔として利用する際は、（要素数以内で）大きな数字から狭めていく。${\frac {3^{k}-1}{2}}$を使う場合、間隔hを121→40→13→4→1とする（hを3で整数除算していけばよい）。 様々な間隔の計算量について理論的に考察されているが、現状、どのような間隔が最適か（例えば、平均$\mathrm {O} (n\log n)$時間となる数列があるか）は未解決問題である。 C++による実装例 template <typename RandomAccessIterator, typename Compare> void shellsort(RandomAccessIterator first, RandomAccessIterator last, Compare comp, const double sk = 3.14159265358979323846264338327950, const short m = 5) { if(first == last) return; double gap = distance(first, last); std::ptrdiff_t h; do { gap /= sk; h = (std::ptrdiff_t)(gap + 0.5); if(h < m) h = 1; RandomAccessIterator H = first + h; for(RandomAccessIterator i = H; i < last; ++i) { if(comp(*i, *(i - h))) { auto t = std::move(*i); RandomAccessIterator j = i; do { *j = std::move(*(j - h)); j -= h; }while(H <= j && comp(t, *(j - h))); *j = std::move(t); } } }while(1 < h); } 脚注 英和和英テキスト翻訳 >> Weblio翻訳 英語⇒日本語日本語⇒英語    >> 「Shellsort」を含む用語の索引  Shellsortのページへのリンク 辞書ショートカット 1 デジタル大辞泉 2 IT用語辞典バイナリ 3 ウィキペディア カテゴリ一覧 全て ＋ ビジネス ＋ 業界用語 ＋ コンピュータ ＋ 電車 ＋ 自動車・バイク ＋ 船 ＋ 工学 ＋ 建築・不動産 ＋ 学問 ＋ 文化 ＋ 生活 ＋ ヘルスケア ＋ 趣味 ＋ スポーツ ＋ 生物 ＋ 食品 ＋ 人名 ＋ 方言 ＋ 辞書・百科事典 すべての辞書の索引 あいうえお かきくけこ さしすせそ たちつてと なにぬねの はひふへほ まみむめも やゆよ らりるれろ わをん がぎぐげご ざじずぜぞ だぢづでど ばびぶべぼ ぱぴぷぺぽ ＡＢＣＤＥ ＦＧＨＩＪ ＫＬＭＮＯ ＰＱＲＳＴ ＵＶＷＸＹ Ｚ １２３４５ ６７８９０ 記号 Weblioのサービス 英会話コラム Weblio英会話 英語の質問箱 語彙力診断 スピーキングテスト 1 シェルソート 百科事典 16% ||||| 2 コムソート 百科事典 8% ||||| Shellsortのお隣キーワード Shelfari Shell EasyPay Shell Ocean Discovery XPRIZE Shell Sound Ignition Shell WindEnergy Shellshock 2: Blood Trails Shellsort Shelly (SHOKICHIの楽曲) Shen Sheng-yen Lu Sherbet Snow and the Airplane e.p. SherbetNEOの＃ねおらじ Sherlock 検索ランキング 英和和英テキスト翻訳 >> Weblio翻訳     英語⇒日本語 日本語⇒英語     Shellsortのページの著作権 Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。     (C)Shogakukan Inc. 株式会社 小学館 Copyright © 2005-2025 Weblio 辞書 IT用語辞典バイナリさくいん。 この記事は、IT用語辞典バイナリの【シェルソート】の記事を利用しております。 All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアのシェルソート (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。 ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問 文化｜生活｜ヘルスケア｜趣味｜スポーツ｜生物｜食品｜人名｜方言｜辞書・百科事典 ご利用にあたって ・Weblio辞書とは ・検索の仕方 ・ヘルプ ・利用規約 ・プライバシーポリシー ・サイトマップ 便利な機能 ・ウェブリオのアプリ ・画像から探す お問合せ・ご要望 ・お問い合わせ 会社概要 ・公式企業ページ ・会社情報 ・採用情報 ウェブリオのサービス ・Weblio 辞書 ・類語・対義語辞典 ・英和辞典・和英辞典 ・Weblio翻訳 ・日中中日辞典 ・日韓韓日辞典 ・フランス語辞典 ・インドネシア語辞典 ・タイ語辞典 ・ベトナム語辞典 ・古語辞典 ・おすすめのプログラミングスクール情報「Livifun」 ©2025 GRAS Group, Inc.RSS      ログイン ※半角英数字、6文字以上、32文字以内で入力してください ログイン パスワードを忘れた方はこちらから 別サービスのアカウントで登録・ログイン アカウントをお持ちでない方 新規会員登録（無料）