Ordenamiento QuickSort (ordenamiento rápido) en Visual Basic .Net (vb.net)

Este día solo vengo de rapido para postear algunos programas que he estado haciendo de tareas en la escuela. Y pues lo hago de rápido ya que mañana tengo examen de desarrollo de proyectos y sinceramente no he estudiado nada :S jeje así que pues aquí esta algo rápido.

Este es el ordenamiento Quick Sort (en español ordenamiento rápido) y como su nombre lo indica, es el ordenamiento más eficiente y eficaz de todos, y por obviedad el más rápido. Este es un algoritmo algo sencillo, una vez que entiendes el tema de recursividad, se te hará fácil entender su funcionamiento.

Vamos con la explicación rápida:

  1. El vector desordenado es enviado a la función “quicksort()”
  2. Al llegarle el vector a la función, se toma el primer elemento del vector (o cualquiera; Nota: en nuestro caso tomamos el primero) y se considera ese elemento como “pivote” o “comodín”.
  3. Después se recorre todo el vector; durante el recorrido, se va buscando los numeros menores que el pivote, sí el elemento del vector en una vuelta es menor que el pivote, entonces se manda a la izquierda del pivote, de lo contrario no se hace nada. Esto provocará que después de recorrer todo el vector, todos los elementos menores que el pivote quedarán a la izquierda de este y los mayores al pivote a la derecha.
  4. Se envía recursivamente la mitad izquierda del vector (números menores que el pivote sin tomar en cuenta el mismo pivote) a la función quicksort
  5. Se envía recursivamente la mitad derecha del vector (números mayores que el pivote sin tomar en cuenta el mismo pivote) a la función quicksort

Pero una imagen dice más que mil palabras:

Y este es el código:

[vbnet]
Public Class Form1

Private Function quicksort(ByVal vec() As Integer, ByVal primero As Integer, ByVal ultimo As Integer) As Array
Dim a, b, piv, Npiv, aux As Integer
piv = vec(primero) ‘sacamos pivote
Npiv = primero

For a = primero To ultimo
If a <> Npiv Then ‘si el pivote no se esta queriendo comparar con el mismo pivote
If vec(a) < piv Then
'mandamos los numeros a la izquierda
aux = vec(a)

'recorremos sub-vector (desde piv hasta vec(a))
For b = a To Npiv + 1 Step -1
vec(b) = vec(b - 1)
Next

vec(Npiv) = aux 'colocamos numero menor a la izquierda de piv
Npiv += 1 'actualizamos posicion de piv
End If
End If
Next

'enviamos recursivamente el vector a la izuierda de piv
If (Npiv - primero <> 0) Then ‘si el sub-vector de la izquierda tiene elementos, entonces se hace recursividad
vec = quicksort(vec, primero, Npiv – 1)
End If

‘enviamos recursivamente el vector a la derecha de piv
If (ultimo – Npiv <> 0) Then ‘si el sub-vector de la derecha tiene elementos, entonces se hace recursividad
vec = quicksort(vec, Npiv + 1, ultimo)
End If

Return vec
End Function

Private Function getMilisegundos(ByVal fecha As Date) As Long
Dim respuesta As Long = 0
Dim dteFechaAux As Date = New Date(1970, 1, 1, 0, 0, 0, 0)
respuesta = DateDiff(DateInterval.Second, dteFechaAux, fecha) * 1000 + fecha.Millisecond
Return respuesta
End Function

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim vec1(19999) As Integer
Dim rand As New Random
Dim a As Integer
Dim str1 As String
Dim tim1I As Long = 0
Dim tim1F As Long = 0

‘llenamos el primer vector de numeros aleatorios
For a = 0 To vec1.Length – 1
vec1(a) = rand.Next(0, 101)
Next

‘ordenamos vector con metodo de QickSort y contamos el tiempo trancurrido y total de intercambios
tim1I = getMilisegundos(DateTime.Now) ‘tiempo inicial

‘ordenamos
vec1 = quicksort(vec1, 0, vec1.Length – 1) ‘le enviamos el vector, el primer elemento y el ultimo

tim1F = getMilisegundos(DateTime.Now) ‘tiempo final

‘imprimimos vectores 1,2 y 3 ordenados
txt1.Text = “”
str1 = “”
For a = 0 To vec1.Length – 1
str1 &= vec1(a) & vbNewLine
Next

txt1.Text = str1

‘imprimimos resultados
lblcomp1.Text = “”
lblinter1.Text = “”
lbltime1.Text = “”

lbltime1.Text = “Tiempo: ” & CType((tim1F – tim1I), String) & ” ms”
End Sub
End Class
[/vbnet]

Como verás el código está debidamente comentado. Cualquier problema, duda o sugerencia por favor coméntalo aquí.
Aquí te dejo la descarga completa para que veas su funcionamiento.

Descarga

Share Button

Leave a Reply

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *