Download code

Jump to: navigation, search

Back to Quicksort_(Visual_Basic_.NET)

Download for Windows: single file, zip

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

quicksort.vb

  1 ' The authors of this work have released all rights to it and placed it
  2 ' in the public domain under the Creative Commons CC0 1.0 waiver
  3 ' (http://creativecommons.org/publicdomain/zero/1.0/).
  4 ' 
  5 ' THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 ' EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 ' MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 ' IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 ' CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 ' TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 ' SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 ' 
 13 ' Retrieved from: http://en.literateprograms.org/Quicksort_(Visual_Basic_.NET)?oldid=17894
 14 
 15 
 16 Module Quicksort
 17     Sub swap(ByRef v1, ByRef v2)
 18         Dim tmp
 19         tmp = v1
 20         v1 = v2
 21         v2 = tmp
 22     End Sub
 23     Function partition(ByRef a() As Object, ByVal left As Integer, _
 24     ByVal right As Integer, ByRef pivot As Integer)
 25         Dim i
 26         Dim piv
 27         Dim store
 28 
 29         piv = a(pivot)
 30 
 31         swap(a(right - 1), a(pivot))
 32 
 33         store = left
 34         For i = left To right - 2
 35             If a(i) <= piv Then
 36                 swap(a(store), a(i))
 37                 store = store + 1
 38             End If
 39         Next
 40         swap(a(right - 1), a(store))
 41 
 42         Return store
 43     End Function
 44     Function getpivot(ByRef a() As Object, ByVal left As Integer, ByVal right As Integer)
 45         return New System.Random().Next(left, right - 1)
 46     End Function
 47     Sub quicksort(ByRef a() As Object, ByVal left As Integer, ByVal right As Integer)
 48         Dim pivot As Integer
 49         If right - left > 1 Then
 50             pivot = getpivot(a, left, right)
 51             pivot = partition(a, left, right, pivot)
 52             quicksort(a, left, pivot)
 53             quicksort(a, pivot + 1, right)
 54         End If
 55     End Sub
 56 
 57     Sub qsort(ByRef a() As Object)
 58         Dim i
 59         Dim ii
 60         For i=0 to a.Length()-1
 61             ii=New System.Random().Next(0, a.Length()-1)
 62             If i<>ii Then
 63                 swap(a(i), a(ii))
 64             End If
 65         Next
 66 
 67         quicksort(a, 0, a.Length())
 68     End Sub
 69     Sub print(ByRef a() As Object)
 70         Dim i
 71         For i = 0 To a.Length() - 1
 72             System.Console.Write("  " & a(i))
 73         Next
 74         System.Console.WriteLine()
 75     End Sub
 76 
 77     Sub main()
 78         Dim towns() As Object = {"Paris", "London", "Stockholm", "Berlin", "Oslo", "Rome", _
 79         "Madrid", "Tallinn", "Amsterdam", "Dublin"}
 80 
 81         System.Console.Write("towns before qsort: ")
 82         print(towns)
 83 
 84         qsort(towns)
 85 
 86         System.Console.Write("towns after qsort: ")
 87         print(towns)
 88 
 89         Dim numbers() As Object = {5, 7, 5, 2, 8, 4, 6, 2, 3, 5, 1, 8, 5, 7, 3}
 90 
 91         System.Console.Write("numbers before qsort: ")
 92         print(numbers)
 93 
 94         qsort(numbers)
 95 
 96         System.Console.Write("numbers after qsort: ")
 97         print(numbers)
 98     End Sub
 99 End Module
100 


hijacker
hijacker
hijacker
hijacker