« クイックソートを用いてアルファベットの文字列を並び替え | トップページ | ユーザーフォームのテキストボックス内で改行文字列を取り出す(その4)最終回 »

2009年11月28日 (土)

【改良】クイックソートを用いてアルファベットの文字列を並び替え

さらなる改良版はこちら(2010/01/17)。

今回は、先週紹介した並び替えのマクロを進化させました。

「words_ascending.dot」をダウンロード

先週紹介したサイトを読んでみたら、あれは、正式には
クイックソートではないらしいですね。

全ての文字列と順序を比較しているので、正式なクイックソート
よりも処理スピードが遅いと思います。

失礼いたしました。

僕も、他のクイックソートのプログラムに較べてあまりにも
シンプルで思考方法が違うので、少し不思議だなと思って
いたのですが、改良をしやすいので使わせてもらってました。

▼前回からの改善点
今回は、前回やりきれなかった以下の2点を改良しました。

①英単語(複数の単語の組み合わせ含む)の完全な並び替え
②大文字・小文字関係なく大小を比較

ついでに、用いる文字列を現在開いているワード文書から
読み込むようにしました。

記事の後半に記載されている「並び替え前後のサンプル」をご覧ください。

全角の文字列も含めて並び替えました。

おおよその並び替えのルールが見えると思います。

▼処理速度の例
ちなみに、2300ほどの英単語で並び替えをした場合に
私のパソコン(CPU: AMD Athlone 64 Processor 3000+ 2GHz,
メモリー: 1G, WinXP + Word2003) で55秒くらいかかりました。

同じことを、ワードの並び替え機能を使うと、1秒もかからずに
一瞬で並び替えてくれます。。。

もともと、このプログラムは、ユーザーフォーム中のリストボックスに
記載された80~100個の文字列の並び替えを目的としたものなので、
その程度の処理であれば、ストレスなく動くと思います。

多くの文字列の並び替えをする場合には、いちどワードの新規文書を開いて、
そこに全ての文字列をコピーしてからワードの機能の並べ替えを実行した方が
速いですね。

あんまりクイックではないソート(並び替え)です。

▼使い方
①インストールします。方法はこちら
②インストールしてアドインをオンにすると、[並び替え]という
 ボタンがツールバーに表示されます。
③開いている文書に、並び替えの対象となる文字列を記入します。
 (1行に1つの文字列を記入)
④[並び替え]ボタンをクリック

▼サンプル
【並び替え前】
300
情報
便利
お役立ち
販売
通販
blog
通信販売
Shopping
Shop
50
ヤフー
通信 販売
通信 販売
ブログ
1500
150
お気に入り

お買い物
検索
お得
デパート
web
Free
web2.0
tool
無料
book
free book
ニュース
進学塾
design
Search
中学受験
アニメ
ショッピング
SNS
映画
FC2
ホテル
DVD
予備校

【並び替え後】
1500
お気に入り
お得
お買い物
お役立ち
アニメ
ショッピング
デパート
ニュース
ブログ
ホテル
ヤフー
映画
検索

情報
進学塾
中学受験
通信 販売
通信販売
通信 販売
通販
販売
便利
無料
予備校
150
300
50
blog
book
design
DVD
FC2
Free
free book
Search
Shop
Shopping
SNS
tool
web
web2.0

▼プログラムの説明
(50行~90行)
開かれている文書に記載されている文字列を読み込みます。
案外、これも時間がかかります。

2300の文字列の場合に、31秒かかりました。
これって、時間かかりすぎ?

(200行~290行)
前回のプログラムでは、大文字のAと小文字のaとでは
別の文字として認識されていることがわかりました。

よって、今回は、Asc関数を用いて、文字コードを拾い出して、
それを変換して大文字と小文字とを比較するようにしました。

そういうわけで、処理がやたら面倒なことになっています。
たぶん、もっと簡単な方法があるんでしょうねぇ。

(10行、590行~610行)
Timer関数を使って時間を計測してみました。

▼プログラム
Sub QuickSortの例()

      Dim pCnt As Integer '段落数用の数値
      Dim pCntMax As Integer '段落の最大値
      Dim i As Long    '並び替え用の数値
      Dim j As Long    '並び替え用の数値
      Dim swap As String  '並び替え時の仮置き用変数
      Dim Chara() As String  '文字列
      Dim nMax As Integer '最大文字数
      Dim n As Integer    '比較する文字の序数
      Dim Chara_J As Integer '大文字を小文字の文字コードに変換
      Dim Chara_I As Integer '大文字を小文字の文字コードに変換
      Dim BlnSwap As Boolean '変更するか否かを示す
      Dim actDoc As Document '文書
      Dim StartT, FinishT, TotalT As Long  '時間計測用

10    StartT = Timer

20    Set actDoc = ActiveDocument

      '参照符号一覧の段落数
30    pCntMax = actDoc.Paragraphs.Count
40    ReDim Chara(1 To pCntMax)

      '文字列の読み込み
50    For pCnt = 1 To pCntMax
60        With actDoc.Paragraphs(pCnt).Range
70            Chara(pCnt) = Left(.Text, .Characters.Count - 1)
80        End With
90    Next pCnt

      'ソート開始
100   For i = 1 To pCntMax

110       For j = pCntMax To i Step -1
         
              '文字の大小の比較の最大回数を算出
              '少ない文字数を最大回数とする
             
120           If Len(Chara(i)) > Len(Chara(j)) Then
130               nMax = Len(Chara(j))
140               BlnSwap = True
150           Else
160               nMax = Len(Chara(i))
170               BlnSwap = False
180           End If
             
              'n番目の文字同士を文字コードを用いて大小を比較
             
190           For n = 1 To nMax
             
                  'アルファベットの文字コードを取得し、
                  '大文字の場合、対応する小文字の文字コードに変換
                  
                  'Chara(i)の場合
200               If Asc(Mid(Chara(i), n)) >= 65 And _
                     Asc(Mid(Chara(i), n)) <= 90 Then
210                   Chara_I = Asc(Mid(Chara(i), n)) + 32
220               Else
230                   Chara_I = Asc(Mid(Chara(i), n))
240               End If
                  
                  'Chara(j)の場合
250               If Asc(Mid(Chara(j), n)) >= 65 And _
                     Asc(Mid(Chara(j), n)) <= 90 Then
260                   Chara_J = Asc(Mid(Chara(j), n)) + 32
270               Else
280                   Chara_J = Asc(Mid(Chara(j), n))
290               End If
                  
                  'n文字目のアルファベットの比較
                  
                  'Chara(i)がChara(j)より大きい場合
300               If Chara_I > Chara_J Then
                  '順番を入れ替える
310                   swap = Chara(i)
320                   Chara(i) = Chara(j)
330                   Chara(j) = swap
340                   Exit For
                  
                  'Chara(i)がChara(j)より小さい場合
350               ElseIf Chara_I < Chara_J Then
                  '順番を入れ替えない
360                   Exit For
                  
                  'Chara(i)とChara(j)が同じ場合 かつ
                  'nが比較を繰り返す最大回数nMaxになっても
                  '文字の大小の比較が終わっていない場合
370               ElseIf n = nMax Then
                  
                      'Chara(i)の文字数がChara(j)の文字数より多い場合
380                   If BlnSwap = True Then
390                       swap = Chara(i)
400                       Chara(i) = Chara(j)
410                       Chara(j) = swap
420                       Exit For
                  
                      'Chara(i)の文字数がChara(j)の文字数以下の場合
430                   Else
440                       Exit For
450                   End If
                  
460               End If
             
470           Next n
             
480       Next j

490   Next i

      '並び替え後を表示

500   With actDoc
510       .Range(.Range.End - 1, .Range.End - 1).InsertParagraphAfter
520       .Range(.Range.End - 1, .Range.End - 1).Text = "【並び替え後】"
530       .Range(.Range.End - 1, .Range.End - 1).InsertParagraphAfter

540       For i = 1 To pCntMax
550           .Range(.Range.End - 1, .Range.End - 1).Text = Chara(i)
560           .Range(.Range.End - 1, .Range.End - 1).InsertParagraphAfter
570       Next i
580   End With

590   FinishT = Timer
600   TotalT = FinishT - StartT

610   MSGBOX TotalT & "秒かかりました。"

End Sub

|

« クイックソートを用いてアルファベットの文字列を並び替え | トップページ | ユーザーフォームのテキストボックス内で改行文字列を取り出す(その4)最終回 »

マクロテンプレート」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/519619/46878691

この記事へのトラックバック一覧です: 【改良】クイックソートを用いてアルファベットの文字列を並び替え:

« クイックソートを用いてアルファベットの文字列を並び替え | トップページ | ユーザーフォームのテキストボックス内で改行文字列を取り出す(その4)最終回 »