BubleSort1

***********************************
Listing 1. Bubblesort.
 Bubblesort is a specialized algorithm designed for sorting 
items that are already mostly in sorted order.

If only one or two items in your list are out of order, 
bubblesort is very fast.

If the items in your list are initially arranged randomly, 
bubblesort is extremely slow.

For this reason you should be careful when you use bubblesort

The idea behind the algorithm is to scan through the list 
looking for two adjacent items that are out of order. 
When you find two such items, you swap them and continue 
down the list. You repeat this process until all of the items
are in order.
Table 1 shows a small list where the item 1 is out of order. 
During the first pass through the list, the algorithm will 
find that items 4 and 1 are out of order so it swaps them. 
During the next pass it finds that items 3 and 1 are out of 
order so it swaps them. During the third pass it swaps items
2 and 1 and the list is in its final order. 
The way in which the item 1 seems to bubble towards the top 
of the list is what gives bubblesort its name.

2 2 2 1
3 3 1 2
4 1 3 3
1 4 4 4

Table 1. In a bubblesort, item 1 slowly "bubbles" to the top.
You can improve the algorithm if you alternate upward and 
downward passes through the list. During downward passes an 
item that is too far down in the list, like the item 1 in the
previous example, can move up only one position. An item that
is too far up in the list might move many positions. 
If you add upward passes through the list, you will be able 
to move items many positions up through the list as well.
During each pass through the list, at least one new item 
reaches its final position. If the items in your list begin 
mostly in sorted order, the algorithm will need only one or 
two passes through the list to finish the ordering. 
If you have a list of 1,000 items with only one out of order,
the algorithm would require only 2,000 steps to put the list
in its proper order.
If the items begin arranged randomly, the algorithm may need
one pass per item in the list. The algorithm would need up 
to 1 million steps to arrange a list of 1,000 items.
Listing 1 shows the VB code for the improved bubblesort 
algorithm.

'min and max are the minimum and maximum indexes

'of the items that might still be out of order.

Sub BubbleSort (List() As Long, ByVal min As Integer, _
ByVal max As Integer)
Dim last_swap As Integer
Dim i As Integer
Dim j As Integer
Dim tmp As Long
' Repeat until we are done.

Do While min < max
' Bubble up.

last_swap = min - 1
' For i = min + 1 To max

i = min + 1
Do While i <= max
' Find a bubble.

If List(i - 1) > List(i) Then
' See where to drop the bubble.

tmp = List(i - 1)
j = i
Do
List(j - 1) = List(j)
j = j + 1
If j > max Then Exit Do
Loop While List(j) < tmp
List(j - 1) = tmp
last_swap = j - 1
i = j + 1
Else
i = i + 1
End If
Loop
' Update max.

max = last_swap - 1
' Bubble down.

last_swap = max + 1
' For i = max - 1 To min Step -1

i = max - 1
Do While i >= min
' Find a bubble.

If List(i + 1) < List(i) Then
' See where to drop the bubble.

tmp = List(i + 1)
j = i
Do
List(j + 1) = List(j)
j = j - 1
If j < min Then Exit Do
Loop While List(j) > tmp
List(j + 1) = tmp
last_swap = j + 1
i = j - 1
Else
i = i - 1
End If
Loop
' Update min.

min = last_swap + 1
Loop
End Sub

***********************************
Listing 1. Bubblesort.
Bubblesort is a specialized algorithm designed for sorting
items that are already mostly in sorted order.

If only one or two items in your list are out of order,
bubblesort is very fast.

If the items in your list are initially arranged randomly,
bubblesort is extremely slow.

For this reason you should be careful when you use bubblesort

The idea behind the algorithm is to scan through the list
looking for two adjacent items that are out of order.
When you find two such items, you swap them and continue
down the list. You repeat this process until all of the items
are in order.
Table 1 shows a small list where the item 1 is out of order.
During the first pass through the list, the algorithm will
find that items 4 and 1 are out of order so it swaps them.
During the next pass it finds that items 3 and 1 are out of
order so it swaps them. During the third pass it swaps items
2 and 1 and the list is in its final order.
The way in which the item 1 seems to bubble towards the top
of the list is what gives bubblesort its name.

2 2 2 1
3 3 1 2
4 1 3 3
1 4 4 4

Table 1. In a bubblesort, item 1 slowly "bubbles" to the top.
You can improve the algorithm if you alternate upward and
downward passes through the list. During downward passes an
item that is too far down in the list, like the item 1 in the
previous example, can move up only one position. An item that
is too far up in the list might move many positions.
If you add upward passes through the list, you will be able
to move items many positions up through the list as well.
During each pass through the list, at least one new item
reaches its final position. If the items in your list begin
mostly in sorted order, the algorithm will need only one or
two passes through the list to finish the ordering.
If you have a list of 1,000 items with only one out of order,
the algorithm would require only 2,000 steps to put the list
in its proper order.
If the items begin arranged randomly, the algorithm may need
one pass per item in the list. The algorithm would need up
to 1 million steps to arrange a list of 1,000 items.
Listing 1 shows the VB code for the improved bubblesort
algorithm.