クイックソートの昇順と降順について

ぺんぺんぺん 2005-03-25 20:16:46 No: 120437

2次元配列のクイックソートを行う場合にソートされた配列が
おかしいのです。
どうおかしいかと言うと以下のソースで取り出しを行いますが、
昇順のときは要素が１からで降順の場合は要素が０からになって
しまいます。

取り出しのときに昇順と降順で変えれば問題は解決できるのでしょうが
ソートの中で修正を行いたいと思っています。

何方かお願いいたします。

<環境>
Win-Xp VB6

'** 取り出し

For j = 1 To UBound(itmX())
Set itmY = SearchList.ListItems.Add(, , CStr(itmX(j, 0)))
itmY.SubItems(1) = itmX(j, 1)
Next j

'** クイックソート昇順
Public Sub QuickSortA(d() As String, StartNum As Variant, EndNum As Variant)

  Dim i As Long
  Dim j As Long
  Dim strBase() As String
  Dim strTemp() As String

  ReDim strArray(EndNum, 2)
  ReDim strBase(1, 2)
  strArray(0, 1) = d((StartNum + EndNum) \ 2, 1)
  i = StartNum
  j = EndNum
  Do
    Do While d(i, 1) < strArray(0, 1)
      i = i + 1
    Loop
    Do While d(j, 1) > strArray(0, 1)
      j = j - 1
    Loop
    If i >= j Then Exit Do
    strBase(0, 0) = d(i, 0)
    strBase(0, 1) = d(i, 1)
    d(i, 0) = d(j, 0)
    d(i, 1) = d(j, 1)
    d(j, 0) = strBase(0, 0)
    d(j, 1) = strBase(0, 1)
    i = i + 1
    j = j - 1
  Loop
  If (StartNum < i - 1) Then QuickSortA d(), StartNum, i - 1
  If (EndNum > j + 1) Then QuickSortA d(), j + 1, EndNum

End Sub

'** クイックソート降順
Public Sub QuickSortD(d() As String, StartNum As Variant, EndNum As Variant)

  Dim i As Long
  Dim j As Long
  Dim strArray() As String
  Dim strBase() As String

  ReDim strArray(EndNum, 2)
  ReDim strBase(1, 2)
  strArray(0, 1) = d((StartNum + EndNum) \ 2, 1)
  i = StartNum
  j = EndNum
  Do
    Do While d(i, 1) > strArray(0, 1)
      i = i + 1
    Loop
    Do While d(j, 1) < strArray(0, 1)
      j = j - 1
    Loop
    If i >= j Then Exit Do
    strBase(0, 0) = d(i, 0)
    strBase(0, 1) = d(i, 1)
    d(i, 0) = d(j, 0)
    d(i, 1) = d(j, 1)
    d(j, 0) = strBase(0, 0)
    d(j, 1) = strBase(0, 1)
    i = i + 1
    j = j - 1
  Loop
  If (StartNum < i - 1) Then QuickSortD d(), StartNum, i - 1
  If (EndNum > j + 1) Then QuickSortD d(), j + 1, EndNum

End Sub

日記好き URL 2005-03-25 22:58:50 No: 120438

リリカちゃんが日記更新してる！

http://eid.jp/2163

ガッ 2005-03-25 23:49:19 No: 120439

[ノ＜日記風に]
> 日記好きさん(根釜？)
巡回して足跡つけていくソフトって、どーやってオブジェクトを解析してるのか、
なぜか凄く気になった今日一日でした。

> ぺんぺんぺんさん
もしかしたら、配列の下限が0だからでは？
ちなみに修正するには、デバッグ料と厚いチップを(ぉ
QuickSortそのものが成功しているのなら、呼び出す側で気をつける、というテもありますねぇ。

ねろ 2005-03-26 02:20:15 No: 120440

質問の回答では無いのですが、Hoareのquicksortアルゴリズムというものがある。
void quicksort(int a[],int first,int last)
{
  int i , j;
  int x , t;
  x = a[(first + last) / 2];
  i = first ; j = last ;
  for (;;){
    while ( a[i] <  x ) i++;
    while ( x < a[j] ) j++;
    if (i >=j) break;
    t= a[i] ; a[i] = a[j] ; a[j] = t;
    i++; j--;
  }
      if ( first < i - 1) quicksort( a, first , i - 1);
  if (j + 1 < last) quicksort( a , j + 1 , last);
}
こんなの。
これはまさにこのＶＢ版ですね。
良く見ると、VBとＣの配列の要素の違いがかなりあやふやかな。

特攻隊長まるるう 2005-03-29 02:11:07 No: 120441

回答じゃないけど不等号しか違わないなら１つの関数にしちゃうなぁ。
※注デバッグして動作確認してるワケではありません。質問のコードを
正しいものと仮定して適当にまとめただけです。参考にする方は考え方
のみ盗んで下さい。
[VB6.0]
'** クイックソート昇順
Public Sub QuickSortA(d() As String, StartNum As Variant, EndNum As Variant)
    Call QuickSortByKeyCol(d, 1, False, CLng(StartNum), CLng(EndNum))
End Sub
'** クイックソート降順
Public Sub QuickSortD(d() As String, StartNum As Variant, EndNum As Variant)
    Call QuickSortByKeyCol(d, 1, True, CLng(StartNum), CLng(EndNum))
End Sub
'** 列指定クイックソート
Public Sub QuickSortByKeyCol(ByRef d() As String, _
                            ByVal ColX As Long, ByVal OrderDescend As Boolean, _
                            ByVal StartNum As Long, ByVal EndNum As Long)
    Dim i As Long
    Dim j As Long
    Dim n As Long
    Dim strBoundary As String
    Dim strTemp As String
    If StartNum >= EndNum Then Exit Sub

    strBoundary = d((StartNum + EndNum) \ 2, ColX)
    i = StartNum
    j = EndNum
    Do
        Do
            If OrderDescend Then
                If Not (d(i, ColX) > strBoundary) Then Exit Do
            Else
                If Not (d(i, ColX) < strBoundary) Then Exit Do
            End If
            i = i + 1
        Loop
        Do
            If OrderDescend Then
                If Not (strBoundary > d(j, ColX)) Then Exit Do
            Else
                If Not (strBoundary < d(j, ColX)) Then Exit Do
            End If
            j = j - 1
        Loop
        If i >= j Then Exit Do
        For n = LBound(d, 2) To UBound(d, 2)
            strTemp = d(i, n)
            d(i, n) = d(j, n)
            d(j, n) = strTemp
        Next
        i = i + 1
        j = j - 1
    Loop
    If (StartNum < i - 1) Then QuickSortByKeyCol d(), ColX, OrderDescend, StartNum, i - 1
    If (EndNum > j + 1) Then QuickSortByKeyCol d(), ColX, OrderDescend, j + 1, EndNum
End Sub

ねろ 2005-03-29 18:05:54 No: 120442

間違った！
× while ( x < a[j] ) j++;
○ while ( x < a[j] ) j--;
orz

問題は、
ReDim strArray(EndNum, 2)
ReDim strBase(1, 2)
等の配列の宣言で、
VBの場合は
strBase(1, 2)と宣言すると、
strBase(0, 0),strBase(0, 1),strBase(0, 2)
strBase(1, 0),strBase(1, 1),strBase(1, 2)
の６個の要素が用意されるけれど、実際このコードでは、
strBase(0, 0),strBase(0, 1)の２つしか使用されていない
つまりReDim strBase(1, 2)はReDim strBase(0, 1)で良いわけで
Cの場合の
strBase[1][2]と宣言すると
strBase[0][0],strBase[0][1]
の要素が用意される場合と混同しているのでは。
この配列に対する知識のあいまいさが、多分呼び出し側のコードのバグを作っている、
ここで一度しっかり配列に対する確認をした方が『吉』では。
ついでに、推測ですが、私が書いたＣのコードからＶＢのコードに直した人は多分きちんと
理解している人、その後誰かが配列に直した、その人はもうちょっと、特に配列が。
たとえば、Dim strBase() As String 、 ReDim strBase(1, 2)は意味の
無いコード、始めから Dim strBase(1,2) As Stringとやれば良いだけ。

ぺんぺんぺん 2005-03-29 18:35:12 No: 120443

皆様ありがとうざいます。

ねろさんの仰る通り配列の宣言についてはあやふやでした。
その辺りを見直してみます。

また、特攻隊長まるるうさんの通り関数にした方が良いですね。
ことらも試してみます。

がんばります！