Home > Algorithm > シェルソート(Shell Sort)

シェルソート(Shell Sort)

Posted by: WebMaster
2008年6月 6日 06:49
Algorithm

C言語で書かれたシェルソート・アルゴリズムをVBで書きました。改良版のシェルソートはさすがに高速です。考案者のシェル(Donald Shell)が着目したのは、挿入ソートで並び替える場合、配列の中に挿入する要素が近くにあるとき高速で並び替えが行えるという長所でした。そこで、挿入ソートを行う前に、離れたところにある要素を予め近くに寄せておくことを考えたのです。

At this article, I wrote Shell Sort Algorithm which is written by C.

VBAで書いた挿入ソートとシェルソートのソースコードです。1,000,000の順序がランダムな配列の並び替えの時間はヒープソートやコムソートの約倍の時間がかかります。シェルソートが1,000,000の並び替えを行う時間で挿入ソートを行おうとすると、約15,000の並び替えしか出来ません。

It is the source code of "Insertion Sort" and a "Shell Sort" written by VBA. The time of sorting of array with a random order of 1,000,000 requires twice as much time of heap sort or Comb Sort.

''************************************************************************
''----- Test Procedure
''------------------------------------------------------
Sub TestProcedure()
Dim i&
Dim Ar() As Double

ReDim Ar(10000)

For i = 0 To UBound(Ar)
 Ar(i) = Round(Rnd * 12345)
Next
Call ShellSort(Ar)   ''<--------Shell Sort
'Call Insertion(Ar)   ''<--------Insertion Sort
Erase Ar
End Sub

''***************************************************************************
''------Insertion Sort
''------ 5 June, 2008 Samurai-logic.com
''----------------------------------------------------------------------------
Private Sub Insertion(Ar)
Dim i&, j&, Temp#
For i = 1 To UBound(Ar)
  Temp = Ar(i)
  j = i
  Do While (j > 0 And Ar(j - 1) > Temp)
   If (Ar(j - 1) > Temp) Then Ar(j) = Ar(j - 1)
   j = j - 1
   If j <= 0 Then Exit Do
  Loop
   Ar(j) = Temp
Next
End Sub

''*************************************************************************************

Sub ShellSort(Ar)
''***************************************************************************
''------Shell Sort for VBA
''------ 5 June, 2008 Samurai-logic.com
''----------------------------------------------------------------------------

Dim i&, j&, ArraySize&, Dist&, Temp#
Dist = 1
ArraySize = UBound(Ar)

''---find sequence of numbers of "N*3+1" (1,4,13,40,121,364...)
''---the number should not exceed ArraySize / 9
''---and store the number to "Dist"
 Do While (ArraySize / 9 > Dist)
   Dist = Dist * 3 + 1
 Loop
   Dist = IIf(Dist = 1, 1, (Dist - 1) / 3)   ''--- if Dist=1, then Dist=1, else Dist=(Dist-1)/3
   
 Do While (Dist > 0)  ''<----Dist will decrease as sequence of number(3N+1)

For i = Dist To ArraySize
''--- In this loop, store Ar(i) to Temp and compare Temp & Ar(j - Dist) <--- j = i, at first.
''--- if element of Ar(j - Dist) is bigger than Temp, then Ar(j) = Ar(j - Dist) <--- slide
''--- Put Temp to Ar(j) at last.
   Temp = Ar(i)
   j = i
 ''----Insertion sort at the distance of sequence of number --->Dist
   Do While (j > 0 And Ar(j - Dist) > Temp)
    If (Ar(j - Dist) > Temp) Then Ar(j) = Ar(j - Dist) 
    j = j - Dist
    If j <= Dist - 1 Then Exit Do
   Loop
    Ar(j) = Temp
  Next
  
  Dist = (Dist - 1) / 3       ''---- Decrease Dist as sequence of number(3N+1)
 Loop
End Sub

Comments:0

Amazon.co.jp ウィジェット

Home > Algorithm > シェルソート(Shell Sort)

Return to page top