Download code

From LiteratePrograms

Back to Quicksort_(Visual_Basic_.NET)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

quicksort.vb

 ' Copyright (c) 2010 the authors listed at the following URL, and/or
 ' the authors of referenced articles or incorporated external code:
 ' http://en.literateprograms.org/Quicksort_(Visual_Basic_.NET)?action=history&offset=20070726234304
 ' 
 ' Permission is hereby granted, free of charge, to any person obtaining
 ' a copy of this software and associated documentation files (the
 ' "Software"), to deal in the Software without restriction, including
 ' without limitation the rights to use, copy, modify, merge, publish,
 ' distribute, sublicense, and/or sell copies of the Software, and to
 ' permit persons to whom the Software is furnished to do so, subject to
 ' the following conditions:
 ' 
 ' The above copyright notice and this permission notice shall be
 ' included in all copies or substantial portions of the Software.
 ' 
 ' THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 ' EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 ' MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 ' IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 ' CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 ' TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 ' SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 ' 
 ' Retrieved from: http://en.literateprograms.org/Quicksort_(Visual_Basic_.NET)?oldid=10766
 
 
 Module Quicksort
     Sub swap(ByRef v1, ByRef v2)
         Dim tmp
         tmp = v1
         v1 = v2
         v2 = tmp
     End Sub
 
     Function partition(ByRef a() As Object, ByVal left As Integer, _
     ByVal right As Integer, ByRef pivot As Integer)
         Dim i
         Dim piv
         Dim store
 
         piv = a(pivot)
 
         swap(a(right - 1), a(pivot))
 
         store = left
         For i = left To right - 2
             If a(i) <= piv Then
                 swap(a(store), a(i))
                 store = store + 1
             End If
         Next
         swap(a(right - 1), a(store))
 
         Return store
     End Function
 
     Function getpivot(ByRef a() As Object, ByVal left As Integer, ByVal right As Integer)
         return New System.Random().Next(left, right - 1)
     End Function
 
     Sub quicksort(ByRef a() As Object, ByVal left As Integer, ByVal right As Integer)
         Dim pivot As Integer
         If right - left > 1 Then
             pivot = getpivot(a, left, right)
             pivot = partition(a, left, right, pivot)
             quicksort(a, left, pivot)
             quicksort(a, pivot + 1, right)
         End If
     End Sub
 
     Sub qsort(ByRef a() As Object)
         Dim i
         Dim ii
         For i=0 to a.Length()-1
             ii=New System.Random().Next(0, a.Length()-1)
             If i<>ii Then
                 swap(a(i), a(ii))
             End If
         Next
 
         quicksort(a, 0, a.Length())
     End Sub
 
     Sub print(ByRef a() As Object)
         Dim i
         For i = 0 To a.Length() - 1
             System.Console.Write("  " & a(i))
         Next
         System.Console.WriteLine()
     End Sub
 
     Sub main()
         Dim towns() As Object = {"Paris", "London", "Stockholm", "Berlin", "Oslo", "Rome", _
         "Madrid", "Tallinn", "Amsterdam", "Dublin"}
 
         System.Console.Write("towns before qsort: ")
         print(towns)
 
         qsort(towns)
 
         System.Console.Write("towns after qsort: ")
         print(towns)
 
         Dim numbers() As Object = {5, 7, 5, 2, 8, 4, 6, 2, 3, 5, 1, 8, 5, 7, 3}
 
         System.Console.Write("numbers before qsort: ")
         print(numbers)
 
         qsort(numbers)
 
         System.Console.Write("numbers after qsort: ")
         print(numbers)
     End Sub
 End Module