Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


Tip of the Day
Language: Visual Basic
Expertise: Intermediate
Feb 3, 1999

Improve on the Bubble Sort

A bubble sort's execution time is a multiple of the square of the number of elements. Because of this, the bubble sort is said to be an n-squared algorithm. You can easily make improvements to a bubble sort to speed it up.

One way is to reverse the direction of passes reading the array, instead of always reading the array in the same direction. This makes out-of-place elements travel quickly to their correct position. This version of a bubble sort is called the shaker sort, because it imparts a shaking motion to the array:

 
Public Sub Shaker(Item() As Variant)
	Dim Exchange As Boolean
	Dim Temp As Variant
	Dim x As Integer

	Do
		Exchange = False
		For x = (UBound(Item)) To (LBound(Item) + 1) Step -1
			If Item(x - 1) > Item(x) Then
				Temp = Item(x - 1)
				Item(x - 1) = Item(x)
				Item(x) = Temp
				Exchange = True
			End If
		Next x

		For x = (LBound(Item) + 1) To (UBound(Item))
			If Item(x - 1) > Item(x) Then
				Temp = Item(x - 1)
				Item(x - 1) = Item(x)
				Item(x) = Temp
				Exchange = True
			End If
		Next x
	Loop While Exchange
End Sub
Although the shaker sort improves the bubble sort, it still executes as an n-squared algorithm. However, because most programmers can code a bubble sort with their eyes closed, this is a nice way to shave 25 to 33 percent off the required execution time without having to dig out the algorithm books. Still, you don't want to use either a bubble or shaker sort for extremely large data sets.
Tan Shing
 
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap
Thanks for your registration, follow us on our social networks to keep up-to-date