配列を並び変え

example(VB.net)

Private MyArray() As Integer = {2, 8, 3, 6, 5, 4, 7, 1, 9, 9, 12, 21, 13, 14, 14, 16, 15, 67, 16, 26, 17, 3, 18, 20, 19, 0, 1}

Sub Main()
  Array.Sort(Myarray)

  For index As Integer = 0 To Myarray.Count - 1
    Console.WriteLine(Myarray(index))
  Next
End Sub

クイックソート

example(VB.net)

Private MyArray() As Integer = {2, 8, 3, 6, 5, 4, 7, 1, 9, 9, 12, 21, 13, 14, 14, 16, 15, 67, 16, 26, 17, 3, 18, 20, 19, 0, 1}

  Sub Main()
    QuickSort(0, MyArray.Count - 1) '*a
    '----結果の表示----
    For index As Integer = 0 To MyArray.Count - 1
      Console.WriteLine(MyArray(index))
    Next
    Console.ReadLine()
  End Sub

  Private Sub QuickSort(ByVal Start As Integer, ByVal Fine As Integer)
    Dim Base, swap As Integer
    Dim i As Integer, l As Integer
    If Fine <= Start Then Exit Sub '*b
    Base = MyArray((Start + Fine) / 2)	'*c
    i = Start
    l = Fine
    Do
      Do While MyArray(i) < Base
        i = i + 1
      Loop
      Do While Base < MyArray(l)
        l = l - 1
      Loop
      If l <= i Then Exit Do
      swap = MyArray(i)
      MyArray(i) = MyArray(l)
      MyArray(l) = swap
      '*d
      i = i + 1
      l = l - 1
    Loop
    '再帰処理*e
    Call QuickSort(Start, i - 1)
    Call QuickSort(l + 1, Fine)

  End Sub

クイックソートは、バイナリサーチの応用版といった感じです。基準値未満および基準値以上の値を検索しそれぞれを入れ替えていくといった流れです。

*a

クイックソートを使用する場合長々と処理を書いても、どのくらいの処理が必要になるのか不明なので、完遂することはできません。

そこで同じ処理を何度も繰り返すように再帰還元処理を使用します。関数に渡す引数は並び変える配列の範囲を指定します。ここは再帰処理の入り口なので配列の全体の範囲を渡すことになります。もし、配列の前半分を並び変えたいという場合には、ここの引数を変化させます。

*b

ここは再帰還元を終了させるための処理です。スタートポイントとエンドポイントが同一若しくは逆転している場合は、指定された範囲は並び変わっているはずなので、処理を中止します。

*c

ここで配列の中から入れ替える基準となる値を決定します。それは実際に並び変える際には、ほとんど並び変わっている配列から、その並びを崩している一部分を並び変える場合が多いから、配列の中央の値を基準にすることが多いようです。

*d

値の入れ替えが終わっている場合は、それぞれの位置まではすべて基準より上または下の値のみとなっているため、それぞれのポインタを一つ進めます。

*e

再起還元処理を呼び出します。