|
|
|
| Title | Sort a list using quicksort and remove duplicates in VB .NET |
|---|
| Description | This example shows how to sort a list using quicksort and remove duplicates in VB .NET. |
|---|
| Keywords | sorting, quicksort, algorithms, duplicates, remove duplicates |
|---|
| Categories | Algorithms |
|---|
|
|
|
The quicksort subroutine takes as parameters a list to sort and the minimum and maximum index of the elements it should sort. It randomly selects a value within the items to sort and uses it as a dividing item. It then moves all of the items that are smaller than this item to the front of the list and all of those larger than the dividing item to the end of the list. It then recursively calls itself to sort the two sublists.
|
|
Public Sub Quicksort(ByVal list() As Integer, ByVal min As _
Integer, ByVal max As Integer)
Dim random_number As New Random
Dim med_value As Integer
Dim hi As Integer
Dim lo As Integer
Dim i As Integer
' If min >= max, the list contains 0 or 1 items so
' it is sorted.
If min >= max Then Exit Sub
' Pick the dividing value.
i = random_number.Next(min, max + 1)
med_value = list(i)
' Swap it to the front.
list(i) = list(min)
lo = min
hi = max
Do
' Look down from hi for a value < med_value.
Do While list(hi) >= med_value
hi = hi - 1
If hi <= lo Then Exit Do
Loop
If hi <= lo Then
list(lo) = med_value
Exit Do
End If
' Swap the lo and hi values.
list(lo) = list(hi)
' Look up from lo for a value >= med_value.
lo = lo + 1
Do While list(lo) < med_value
lo = lo + 1
If lo >= hi Then Exit Do
Loop
If lo >= hi Then
lo = hi
list(hi) = med_value
Exit Do
End If
' Swap the lo and hi values.
list(hi) = list(lo)
Loop
' Sort the two sublists.
Quicksort(list, min, lo - 1)
Quicksort(list, lo + 1, max)
End Sub
|
|
|
To remove duplicates, the program scans through the sorted array, comparing each item to the one before it. If the item is different, it copies the item into a new array.
|
|
' Remove duplicates from a sorted list.
Public Function RemoveDuplicates(ByVal list() As Integer) _
As Integer()
Dim result() As Integer
Dim max_i As Integer = list.Length - 1
Dim new_i As Integer
' Copy the non-duplicates into the result array.
ReDim result(max_i)
result(0) = list(0)
new_i = 0
For old_i As Integer = 1 To max_i
If list(old_i) <> result(new_i) Then
new_i += 1
result(new_i) = list(old_i)
End If
Next old_i
' Remove unused entries in the result array.
ReDim Preserve result(new_i)
' Return the result.
Return result
End Function
|
|
|
See my book Ready-to-Run Visual Basic Algorithms for more information on this and other sorting algorithms. Note that quicksort works very well with lists that are initially randomly arranged and that do not contain too many duplicate values. Under other circumstances, see the book for better sorting algorithms.
|
| |
|
| |
|
|
