hinekure.net が http://hspdev-wiki.net/ から自動クローリングした結果を表示しています。画像やリソースなどのリンクが切れています。予めご了承ください。
Sort/Quick - HSP開発wiki
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS

クイックソート †

[編集]
↑

概要 †

[編集]

ソート対象の配列変数から基準となる値（ピボットと呼ぶ）を選んで

  • 基準値よりも小さい数値
  • 基準値よりも大きい数値

の2つのグループに分けることを繰り返すソート方法。
実行速度は速いが、ソート対象の状態によって大きく変化する。また不安定なソートでもある。

↑

実装例 †

[編集]
fileQuickSortSample.hsp
Everything is expanded.Everything is shortened. 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
-
|
|
!
 
 
-
|
|
|
-
|
|
!
!
-
|
|
!
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

// Quick Sort for HSP3 ... 数値型配列変数を昇順でソート
#module QuickSortSample
 
// 配列変数の入れ替え target(i1) ⇔ target(i2)
#deffunc qsExchange array target, int i1, int i2, local tmp
    tmp = target(i1) : target(i1) = target(i2) : target(i2) = tmp
    return
 
// 再帰用命令（内部利用）
#deffunc qsArgo array target, int startIndex, int endIndex, local std, local lastExchangedIndex
    std = target(startIndex)                                // 基準値（簡単のために一番端の要素を選択）
    lastExchangedIndex = startIndex                         // 最後に基準値より小さい値を格納した要素
 
    // 基準値よりも小さい値をひとまとまりにする
    repeat endIndex - startIndex, startIndex + 1
        if target(cnt) < std {                              // 降順にしたい場合はここを変更する
            lastExchangedIndex++
            qsExchange target, lastExchangedIndex, cnt
        }
    loop
 
    if startIndex < lastExchangedIndex {
        // 基準値よりも小さい数値を格納した要素があった
        qsExchange target, startIndex, lastExchangedIndex   // 基準値を正しい位置に移動
 
        if startIndex < lastExchangedIndex - 1 {
            // 基準値よりも小さい値が複数ある場合、それらに対して再帰的にソートを実行
            qsArgo target, startIndex, lastExchangedIndex - 1
        }
    }
    if lastExchangedIndex < length(target) - 2 {
        // 基準値よりも大きい値が複数ある場合、それらに対して再帰的にソートを実行
        qsArgo target, lastExchangedIndex + 1, length(target) - 1
    }
    return
 
#deffunc qSort array target
    qsArgo target, 0, length(target) - 1
    return
 
#global
 
// 以下 動作確認用サンプル
    randomize
 
    s = "ソート前："
    dim test, 15
    repeat length(test)
        test(cnt) = rnd(100)
        s += str(test(cnt)) + ", "
    loop
    mes s
 
    qSort test
 
    s = "ソート後："
    repeat length(test)
        s += str(test(cnt)) + ", "
    loop
    mes s
 
    stop
↑

実装例２(独自スタック使用による非再帰版) †

[編集]

独自にスタックを用意してループで処理を行っています.
そのため再帰で処理を行った場合と異なりシステムスタックの限界によるエラーは起きません。

  • ちょっと更新。
    • 処理方法に 再帰 + ループ を追加。
    • 基準値と等価の要素をまとめて処理するようにした。

      -- 2008-01-06 (日) 01:58:22

filemod_qsort_20080105.hsp
+  本体モジュール

上のモジュールを使ったサンプルプログラムです。
(モジュールファイル名を mod_qsort.hsp にリネームしてください。)

filemod_qsort_sample.hsp
+  サンプルプログラム
↑

参考文献 †

[編集]
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS
Last-modified: 2010-03-22 (月) 17:24:33 (1357d)