abwiki @ ウィキ　(ActiveBasic非公式wiki)

abwiki @ ウィキ　(ActiveBasic非公式wiki)内検索 / 「安定」で検索した結果

• 安定
  ...としよう。 安定なソートを使えば2回ソートするだけで上記を達成できるが安定でないソートを使うと 残念な結果になる。
• 安定版
  安定版(あんていばん、あんじょうばん)とは、正式版やベータ版、新旧は問わず、そのプログラムでもっとも目立ったバグが無く安定しているバージョンのこと。 ABはバージョンアップごとにバグフィックス、機能追加とそれによるエンバグ、デグレードが多々発生した経緯があり一概にバージョンアップを推奨できなかった。 しかしそれももうおしまい。5年という月日は長すぎた。
• ラディックス・ソート
  ... と高速であり、また安定でもある。 入力データは、数字の桁数や文字列の文字数などキーの形式が定まっていることを前提とし、また各桁の処理に実行時間 O(n) である整列法（分布数えソートなど）を使用することから有限かつ最大・最小値の定まったものを必要とする。 そのアルゴリズムは以下のとおり。 入力データは、桁数ごとのキーに分類する。3桁の数字であれば、1の位・10の位・100の位など。 それぞれのキーについて、下位のキーから整列する。ここでの整列法の実行時間および安定性がラディックス・ソートのそれに影響する。 ここでは最速かつ安定であることを目指すことから、分布数えソートを使用する。 桁数が多いときでも、数桁をラディックス・ソートで整列し、仕上げを挿入ソートにするなどできる。 下記プログラムでは、原著に近い形のデータ構造として、Byte型配列（数値ないし文字...
• マージソート
  ...ogn)程度であり、安定な整列法である。また、クイックソートと異なり、どのようなデータに対しても高速であるが、データと同程度の作業用記憶領域を必要とする。 下記プログラムでは、マージソートが安定であることを示すために整列データに整列に使用するキー欄（key）以外に情報欄（info）を持たせている。さらに高速にするには、11行目を if If first - last 10 Then とし、44行目で Else simplesort などと挿入ソートなどに切り替えればよい。 プログラミング掲示板「ソートロジック大会」なども参照のこと マージ 整列したデータをまとめてひとつの整列したデータにすることをマージ（併合）という。整列した大きなデータを更新する際は、追加分のデータを整列した後に整列済みのデータにマージするほうが圧倒的に速い。 Type SORTkey...
• 2ch過去ログ
  ...【冬眠中】 【安定版】ActiveBasicその12【4.24】
• バブルソート
  整列アルゴリズムのひとつ。 安定な整列法である。実行時間はO(n^2)である。 配列の先頭から隣通しを比較して逆順であれば交換する。これを交換できなくなるまで続ける。 プログラミング掲示板「ソートロジック大会」なども参照のこと TypeDef keytype = IntegerSub bubblesort(n As Integer, a As *keytype)Dim i As Integer, j As Integer, k As IntegerDim x As keytypek = n - 1While k = 0j = -1'番兵のセットFor i = 1 To k + 1'隣通しの比較と交換If a[i - 1] a[i] Thenj = i - 1x = a[j]a[j] = a[i]a[i] = xEnd IfNext ik = jW...
• 挿入ソート
  整列アルゴリズムのひとつ。 単純挿入法とも呼ばれ、安定な整列法である。実行時間はO(n^2)であるが、ほぼ整列しているデータに対しては非常に早い。 プログラミング掲示板「ソートロジック大会」なども参照のこと TypeDef keytype = IntegerSub insertsort(n As Integer, a As *keytype)Dim i As Integer, j As IntegerDim x As keytypeFor i = 1 To n'整列の比較要素を定めるx = a[i]'xよりも大きいものを右に寄せるj = i - 1While j = 0 And a[j] xa[j + 1] = a[j]j = j - 1Wenda[j + 1] = xNext iEnd Sub
• 選択ソート
  整列アルゴリズムのひとつ。 単純選択法とも呼ばれ、安定な整列法である。実行時間はO(n^2)である。 昇順に並び替える場合の手順は以下のとおり。 配列の最小値を探し出し先頭の値と交換する 上記交換した先頭を除いた部分配列より最小値を探し出し、2番目と交換する 以降、同様にして3番目、4番目･･･を求めていく プログラミング掲示板「ソートロジック大会」なども参照のこと TypeDef keytype = IntegerSub selectsort(n As Integer, a As *keytype)Dim i As Integer, j As Integer, k As IntegerDim min As keytypeFor i = 0 To n - 1min = a[i]k = i'未整列範囲の最小値を求めるFor j = i + 1 To...
• Shellソート
  ...る整列法。高速だが、安定ではない。 挿入ソートは、ほとんど整列されたデータに関しては高速である。しかし、隣通しの交換しかしないため、あまり整列されていないデータでは低速であった。そこで、適当な間隔をあけて大雑把な整列を行うことで高速化させている。 大雑把な整列をするための間隔はいくつか考えられるが、下記の例ではh(1)=1, h(n)=3×h(n-1)+1で定義される数列を用いており、このときの実行時間はO(n^1.25)であることが知られている。 プログラミング掲示板「ソートロジック大会」なども参照のこと TypeDef keytype = IntegerSub shelsort(n As Integer, a As *keytype)Dim h As Integer, i As Integer, j As IntegerDim x As keytypeh...
• コムソート
  ...年4月に発表された。安定ではないが、実行速度は、ほぼO(n log n)になる。アルゴリズム的にはShellソートと同じように適当な間隔をあけて大雑把な整列をし、順次その間隔をつめていくことで高速化している。その間隔の数列は、データ総数を1.3で順次割った数列を使用する。また、間隔gap=9またはgap=10である時に強制的にgap=11とすることで、11以下の数列を11→8→6→4→3→2→1として効率を良くしたものをCombsort11と呼ぶ。 プログラミング掲示板「ソートロジック大会」なども参照のこと TypeDef keytype = IntegerConst SHRINKFACTOR = 13Sub combsort(n As Integer, a As *keytype)Dim i As Integer, flg As Integer, gap As In...
• 分布数えソート
  ...)と高速であり、また安定である。アルゴリズムは以下のとおり。 データを通読してキーの度数分布を数える 度数分布を累積して順位に変換する 順位の場所にデータを入れなおす データは一定の範囲の整数値で無ければならないが、そうでない場合もキー値を整数に丸めた上で大まかに整列し、最後に挿入ソートで仕上げることもできる。 配列の参照が順を追って行われないため、仮想記憶上で大量のデータを整列しようとするとクイックソートより遅くなる場合がある。 プログラミング掲示板「ソートロジック大会」なども参照のこと Const MAX = 100'分布の上限値Const MIN = 0'分布の下限値Sub distsort(n As Integer, a As *Integer, b As *Integer)Dim i As Integer, x As Integ...
• 逆写像ソート
  ...は O(n) であり安定であるが、分布数えソートよりも若干遅いようである。整列に使用するキー値は一定の範囲の整数でなければならない。アルゴリズムは以下のとおり。 x = a[i] ⇔ i = index[x] となる index[x] を作成する もし x = a[i] となる i がなければ index[x] = -1とする キー値が重複する場合、別配列 next[i] を用いてその並びを記述する（ex：a[i] = a[j] = a[k] ⇒ next[i] = j, next[j] = k, next[k] = -1） index[x] -1のとき、a[index[x]] を書き出す プログラミング掲示板「ソートロジック大会」なども参照のこと Const MAX = 100Const MIN = 0Sub mapsort(n As Integer,...
• トップページ
  ... 当wikiでは安定版と思われるVersion 4.24.00を使用しよう！　とおもひます。。。 テスト←wiki練習用。好きに使ってくださいね！雑談、悩み告白、暴れたい人もどうぞ。 ※注意 当wikiの記述は信頼性を保証するものではありません。 ActiveBasicはバージョンごとの互換性に問題があります。 コーディングスタイルは人それぞれです。ABのような始まってもいないものでは議論するだけムダです。だからといって IOCCC のようなスタイルは控えた方が無難です。 個人情報の書き込みはおやめください。 目次 基本←基本的な使い方 応用←実践的用法 リファレンス←関数、命令のリファレンス AB以外の開発環境←ABなんて使ってられるか！！！って人はこちら 便利ツール←お役立ち ABによる生成物集積所←ABでできること FAQ←ABでよくある質問と答え N88BAS...
• 投票
  (4.24と比べて)4.23の方が安定度高いんじゃないかなと思うけどどう思う？ 選択肢 投票 はい (47) いいえ (58) 再試行 (49) 好きなAKB48メンバー 選択肢 投票 倉持明日香 (17) 小嶋陽菜 (12) 高橋みなみ (5) 中田ちさと (10) 板野友美 (15) 仁藤萌乃 (32) 藤江れいな (10) 宮澤佐江 (5) 柏木由紀 (11) ...
• ヒープソート
  整列アルゴリズムのひとつ。 安定ではなく、平均的にはクイックソートよりもやや遅いが、最悪の場合でもO(nlogn)である。 ヒープソートは、未整列データをヒープ構造に構成し、その"根"を順次取り出すことで整列を行う。ヒープ構造は、"親"に対して2つの"子"を持ち、昇順の場合a[i] a[2i]かつa[i] a[2i+1]を満たす構造であるため、その"根"は未整列データの最大値となる（降順の場合は"根"が最小になるようにヒープ構造を構築する）。昇順整列におけるヒープ構造の構築は下記方法で行うが、親子関係はたかだかlog2(n)程度しか続かない。 ある値a[i]に着目し、その"子"a[2i]とa[2i+1]を比較して大きいほうをa[j]とする a[i]とa[...
• クイックソート
  ...^2)にまで落ちる。安定ではない。 クイックソートのアルゴリズムは、以下のとおり。 適当な値xを選ぶ（この時、x未満の要素数とx以下の要素数を同程度にする） x未満の要素を前半に、x以上の要素を後半に集める 前半の要素数が2以上であれば前半をクイックソートする 後半の要素数が2以上であれば後半をクイックソートする このように配列を約二分割して、自分自身を再帰的に整列する（分割統治）。しかしながら、うまく二分割できない場合（例えば、一方に1個、もう一方に残り全て）は実行時間がn^2に比例する。よって、実行速度は入力データに対する分け目の値xの選び方に左右される。a[first]やa[last]などはほとんど整列したデータに弱い。下で示した中央の値をとる方法以外に、 a[first]、a[last]、a[(first+last)/2]の中央値をとる a[...
• @wiki全体から「安定」で調べる

更新順にページ一覧表示 | 作成順にページ一覧表示 | ページ名順にページ一覧表示 | wiki内検索