Print   Add To Favorites     Email To Friend   Rate This Article Sorting an Array Using Combsort
Published: 02 Nov 2003
Unedited - Community Contributed
Abstract
Using Combsort in VBScript to sort an array, with performance analysis.
by
Feedback
Average Rating: This article has not yet been rated.
Views (Total / Last 10 Days): 18527/ 21
Article Contents:

Introduction

The other day I had to sort a rather large array. I could have used the wellknown quicksort-method, but then I remembered the combsort-method. (Unfortunately I can not remember, who has made this exellent sorting algorithm). Combsorting is very simple to implement and it is comparable in speed to quicksort, but is is not known by very many programmers.

Below is a VBscript-program where you can compare combsort to bobblesort. On my Thinkpad 570 I got the folowing results:

Number of elements to sort: Combsort Bubblesort
1000 0.25 sec 5.6 sec
1500 0.4 sec 12.0 sec
10000 3.4 sec n/a
20000 7 sec n/a
40000 17 sec n/a
60000 26 sec n/a

It is only the procedure CombSort, which is interesting. The rest is just to make it possible to measure the performance.

Code

```Option Explicit
Dim M, t1, t2
Dim A()
Dim B()

Sub initB()
Dim i
Randomize
for i=0 to M
B(i)= Rnd
next
End Sub

Sub A_equal_B()
Dim i
for i=0 to M
A(i) = B(i)
next
End Sub

Sub CombSort()
'This procedure will sort the array A
'using the CombSort-methode
Dim i,j,gap,x,OK
gap = M
OK = True
While OK
'You can try other values, but 1.33 seems to be the best
gap= Int(gap/1.33)
If gap < 1 Then gap = 1
OK = (gap <> 1)
For i = 0 To M - gap
j = i + gap
If A(i) > A(j) Then
x = A(i)
A(i) = A(j)
A(j) = x
OK = True
End If
Next
Wend
End Sub

Sub Bobblesort()
'This procedure will sort the array A
'using the Bobblesort-methode
Dim i,j,x
For i = 0 To M-1
For j = 0 To M-1 - i
If A(j) > A(j + 1) Then
x = A(j)
A(j) = A(j + 1)
A(j + 1) = x
End If
Next
Next
End Sub

Private Sub showA(txt)
Dim s
s= txt & VBCrLf
s= s & "Time: " & t2-t1 & VBCrLf
'Show the sorted array for small values of M
if M<100 then s= s & join(A," * ")
MsgBox s
End Sub

M=Clng(InputBox("Number of elements to sort: "))
ReDim A(M)
ReDim B(M)
initB()

'Combsort:
'M=1500: sorttime about 0.4 sec
A_equal_B()
t1=Timer
Combsort()
t2=Timer
showA("CombSort:")

'Bobblesort
'M=1500: sorttime about 12 sec
'so be careful not to use Bobblesort for large values of M
if M<=1500 then
A_equal_B
t1=Timer
Bobblesort
t2=Timer
showA("BobbleSort")
end if
```