Bubble Sort in VBScript

Bubble sort is a very simple sorting technique that has the average and worst-case complexity . It swaps each time neighbouring two elements if it is not in order. After n times at most, the list will be sorted. e.g. Suppose the left-most element at the beginning is the largest, and it takes n times for it to swapped to the right-most position. The following gives the basic idea, quick implementation of Bubble sorting in VBScript (i.e. VBScript syntax is simple and elegant).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

' Sort Data with Bubble Sort
arr = Array(4, 6, 2, 7, 3, 5, 1, 8, 10, 22, 33, 15, 11, 8)
 
For i = LBound(arr) to UBound(arr)
  For j = LBound(arr) to UBound(arr) - 1
      If arr(j) > arr(j + 1) Then
         TempValue = arr(j + 1)
         arr(j + 1) = arr(j)
         arr(j) = TempValue
      End If
  Next
Next
 
s = ""
For i = LBound(arr) To UBound(arr)
    s = s & arr(i) & ","
Next    
 
WScript.Echo s

' Sort Data with Bubble Sort
arr = Array(4, 6, 2, 7, 3, 5, 1, 8, 10, 22, 33, 15, 11, 8)

For i = LBound(arr) to UBound(arr)
  For j = LBound(arr) to UBound(arr) - 1
      If arr(j) > arr(j + 1) Then
         TempValue = arr(j + 1)
         arr(j + 1) = arr(j)
         arr(j) = TempValue
      End If
  Next
Next

s = ""
For i = LBound(arr) To UBound(arr)
	s = s & arr(i) & ","
Next	

WScript.Echo s

The following is the GIF animation (from wiki) that shows the process of Bubble sort.

It is not difficult to find that once the list becomes sorted, there is no need to continue the outer loop. So in best cases, it only takes for bubble sort to finish. We just need to use a variable to check if there is any swaps in one pass. If there isn’t any swaps, then the list is sorted. So we can write a much clearer code using DO-Loop-Until

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

' Sort Data with Bubble Sort
 
arr = Array(4, 6, 2, 7, 3, 5, 1, 8, 10, 22, 33, 15, 11, 8)
 
Do
  Swap = False
  For j = LBound(arr) to UBound(arr) - 1
      If arr(j) > arr(j + 1) Then
         TempValue = arr(j + 1)
         arr(j + 1) = arr(j)
         arr(j) = TempValue
         Swap = True
      End If
  Next
Loop Until Not Swap
 
s = ""
For i = LBound(arr) To UBound(arr)
    s = s & arr(i) & ","
Next    
 
WScript.Echo s

' Sort Data with Bubble Sort

arr = Array(4, 6, 2, 7, 3, 5, 1, 8, 10, 22, 33, 15, 11, 8)

Do
  Swap = False
  For j = LBound(arr) to UBound(arr) - 1
      If arr(j) > arr(j + 1) Then
         TempValue = arr(j + 1)
         arr(j + 1) = arr(j)
         arr(j) = TempValue
         Swap = True
      End If
  Next
Loop Until Not Swap

s = ""
For i = LBound(arr) To UBound(arr)
	s = s & arr(i) & ","
Next	

WScript.Echo s

The bubble sort can be optimized. One quick observation is that each loop, a n-th largest element will be put at its final position. Therefore, it is no need to check for the last n-1 items when running n-th loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

' Sort Data with Bubble Sort
 
arr = Array(4, 6, 2, 7, 3, 5, 1, 8, 10, 22, 33, 15, 11, 8)
 
n = UBound(arr)
Do
  Swap = False
  For j = LBound(arr) to n - 1
      If arr(j) > arr(j + 1) Then
         TempValue = arr(j + 1)
         arr(j + 1) = arr(j)
         arr(j) = TempValue
         Swap = True
      End If
  Next
  n = n - 1  ' skip an in-place element each time
Loop Until Not Swap
 
s = ""
For i = LBound(arr) To UBound(arr)
    s = s & arr(i) & ","
Next    
 
WScript.Echo s

' Sort Data with Bubble Sort

arr = Array(4, 6, 2, 7, 3, 5, 1, 8, 10, 22, 33, 15, 11, 8)

n = UBound(arr)
Do
  Swap = False
  For j = LBound(arr) to n - 1
      If arr(j) > arr(j + 1) Then
         TempValue = arr(j + 1)
         arr(j + 1) = arr(j)
         arr(j) = TempValue
         Swap = True
      End If
  Next
  n = n - 1  ' skip an in-place element each time
Loop Until Not Swap

s = ""
For i = LBound(arr) To UBound(arr)
	s = s & arr(i) & ","
Next	

WScript.Echo s

Further, we can notice that it can happen that more than one elements are in place after a single pass, and therefore we can skip these, which improves the bubble sort. And it doesn’t add too much complexity to the algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

' Sort Data with Bubble Sort
 
arr = Array(4, 6, 2, 7, 3, 5, 1, 8, 10, 22, 33, 15, 11, 8)
 
n = UBound(arr)
Do
  nn = -1
  For j = LBound(arr) to n - 1
      If arr(j) > arr(j + 1) Then
         TempValue = arr(j + 1)
         arr(j + 1) = arr(j)
         arr(j) = TempValue
         nn = j
      End If
  Next
  n = nn
Loop Until nn = -1
 
s = ""
For i = LBound(arr) To UBound(arr)
    s = s & arr(i) & ","
Next    
 
WScript.Echo s

' Sort Data with Bubble Sort

arr = Array(4, 6, 2, 7, 3, 5, 1, 8, 10, 22, 33, 15, 11, 8)

n = UBound(arr)
Do
  nn = -1
  For j = LBound(arr) to n - 1
      If arr(j) > arr(j + 1) Then
         TempValue = arr(j + 1)
         arr(j + 1) = arr(j)
         arr(j) = TempValue
         nn = j
      End If
  Next
  n = nn
Loop Until nn = -1

s = ""
For i = LBound(arr) To UBound(arr)
	s = s & arr(i) & ","
Next	

WScript.Echo s

The following (also from wiki) is a GIF animation that shows how the numbers are sorted using bubble sort.

Despite its simplicity, the bubble sort is generally considered less performed (efficient) than other sorting algorithm, even the simple sorting such as selection sort and insertion sort. When n is large, the running time complexity grows quickly and this makes bubble sort not in practical use. Other algorithms such as quick-sort are generally considered more efficient. The bubble sort, however, is often used in class for teaching data structure & algorithms purposes.

References:

http://en.wikipedia.org/wiki/Bubble_sort

–EOF (The Ultimate Computing & Technology Blog) —