Appunti di Programmazione
Sort: routine di riordinamento in VB .Net
Talvolta mi è capitato di dovere riordinare un insieme di dati, e nonostante vi siano degli strumenti adatti allo scopo, mi sono incuriosito per capire quali algoritmi si celano dietro queste routine.
Riguardando alcuni vecchi manuali di programmazione ne ho trovate qualcune, le ho "tradotte" in VB.Net, e le ho riunite in un'unica applicazione che allego di seguito:
Public Class Form1
Private WithEvents TextBox1 As New TextBox
Private WithEvents btnBubbleSort As New Button
Private WithEvents btnShellSort As New Button
Private WithEvents btnMetznerSort As New Button
Private WithEvents btnQuickSort As New Button
Private WithEvents btnEsci As New Button
Dim n As Integer = 9
Dim numero(0 To n) As Integer
Dim elenco(0 To n) As Integer
Public Sub New()
InitializeComponent()
With Me
.Size = New Size(270, 270)
.Text = "Metodi di riordinamento"
End With
With TextBox1
.Location = New Point(12, 16)
.Multiline = True
.Size = New Size(114, 204)
.ScrollBars = ScrollBars.Vertical
End With
With btnBubbleSort
.Location = New Point(142, 12)
.Size = New Size(108, 36)
.Text = "Bubble Sort"
End With
With btnShellSort
.Location = New Point(142, 54)
.Size = New Size(108, 36)
.Text = "Shell Sort"
End With
With btnMetznerSort
.Location = New Point(142, 96)
.Size = New Size(108, 36)
.Text = "Metzner Shell Sort"
End With
With btnQuickSort
.Location = New Point(142, 138)
.Size = New Size(108, 36)
.Text = "Quick Sort"
End With
With btnEsci
.Location = New Point(142, 180)
.Size = New Size(108, 36)
.Text = "Esci"
End With
Me.Controls.Add(TextBox1)
Me.Controls.Add(btnBubbleSort)
Me.Controls.Add(btnShellSort)
Me.Controls.Add(btnMetznerSort)
Me.Controls.Add(btnQuickSort)
Me.Controls.Add(btnEsci)
Randomize()
For i As Integer = 0 To n
numero(i) = CInt(Int((100 * Rnd()) + 1))
elenco(i) = numero(i)
Next
End Sub
Private Sub BubbleSort(ByVal array() As Integer)
Dim z As Boolean
Dim num As Integer = 0
Do
z = False
For i As Integer = 0 To n - 1
If array(i) > array(i + 1) Then
num = array(i)
array(i) = array(i + 1)
array(i + 1) = num
z = True
End If
Next
Loop While z = True
Visualizza(array)
End Sub
Private Sub ShellSort(ByVal array() As Integer)
Dim z As Integer = n
Dim y As Integer
Dim zz As Integer
Dim xx As Integer
Dim w As Integer
Do
z = CType(z / 2, Integer)
y = n - z
Do
zz = 0
For x As Integer = 0 To y
xx = x + z
If array(x) > array(xx) Then
w = array(x)
array(x) = array(xx)
array(xx) = w
zz = 1
End If
Next
Loop While zz > 0
Loop While z > 1
Visualizza(array)
End Sub
Private Sub MetznerSort(ByVal array() As Integer)
Dim z As Integer = n
Dim y As Integer = 0
Dim zz As Integer = 0
Dim x As Integer = 0
Dim xx As Integer = 0
Dim w As Integer = 0
Do
z = CType(z / 2, Integer)
If z = 0 Then Exit Do
y = n - z
zz = 0
Do
x = zz
Do
xx = x + z
If array(x) <= array(xx) Then
Exit Do
Else
w = array(x)
array(x) = array(xx)
array(xx) = w
x = x - z
End If
Loop While x >= 1
zz += 1
Loop While zz <= y
Loop While z > 0
Visualizza(array)
End Sub
Private Sub QuickSort(ByVal array() As Integer)
Dim k As Integer = 1
Dim i As Integer = 0
Dim s(n) As Integer
Dim a As Integer
Dim b As Integer
Dim l As Integer
Dim u As Integer
Dim z As Integer
s(i) = 0
s(i + 1) = n
Do
If k = 0 Then Exit Do
k -= 1
i = k + k
a = s(i)
b = s(i + 1)
z = array(a)
u = a
l = b + 1
Do
l -= 1
If z > array(l) Then
array(u) = array(l)
Do
u += 1
If z < array(u) Then
array(l) = array(u)
Exit Do
End If
Loop While l <> u
End If
Loop While l <> u
array(u) = z
If (b - u) >= 2 Then
i = k + k
s(i) = u + 1
s(i + 1) = b
k += 1
End If
If l - a >= 2 Then
i = k + k
s(i) = a
s(i + 1) = l - 1
k += 1
End If
Loop
Visualizza(array)
End Sub
Private Sub btnBubbleSort_Click(ByVal sender As Object, ByVal e As System.EventArgs) _
Handles btnBubbleSort.Click
Ricopia()
TextBox1.Text += Environment.NewLine + "Bubble Sort" + Environment.NewLine
BubbleSort(numero)
End Sub
Private Sub btnShellSort_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles btnShellSort.Click
Ricopia()
TextBox1.Text += Environment.NewLine + "Shell Sort" + Environment.NewLine
ShellSort(numero)
End Sub
Private Sub btnMetznerSort_Click(ByVal sender As Object, ByVal e As System.EventArgs) _
Handles btnMetznerSort.Click
Ricopia()
TextBox1.Text += Environment.NewLine + "Metzner Shell Sort" + Environment.NewLine
MetznerSort(numero)
End Sub
Private Sub btnQuickSort_Click1(ByVal sender As Object, ByVal e As System.EventArgs) _
Handles btnQuickSort.Click
Ricopia()
TextBox1.Text += Environment.NewLine + "Quick Sort" + Environment.NewLine
QuickSort(numero)
End Sub
Private Sub Visualizza(ByVal array() As Integer)
For i As Integer = 0 To n
TextBox1.Text += elenco(i).ToString + " " + array(i).ToString + Environment.NewLine
Next
End Sub
Private Sub Ricopia()
For i As Integer = 0 To n
numero(i) = elenco(i)
Next
End Sub
Private Sub btnEsci_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles btnEsci.Click
End
End Sub
End Class
Si tratta di 4 routine BubbleSort, ShellSort, MetznerShellSort e QuickSort.
Solamente la prima delle 4, BubbleSort, non è indicata per grandi liste, perché lenta, le altre, invece, consentono un riordinamento piuttosto veloce degli elementi. Fra tutte spicca la QuickSort.
