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:

PLAIN TEXT
VB.NET:
  1. Public Class Form1
  2.  
  3.     Private Function quicksort(ByVal vec() As Integer, ByVal primero As Integer, ByVal ultimo As Integer) As Array
  4.         Dim a, b, piv, Npiv, aux As Integer
  5.         piv = vec(primero) 'sacamos pivote
  6.         Npiv = primero
  7.  
  8.         For a = primero To ultimo
  9.             If a <> Npiv Then 'si el pivote no se esta queriendo comparar con el mismo pivote
  10.                 If vec(a) <piv Then
  11.                     'mandamos los numeros a la izquierda
  12.                     aux = vec(a)
  13.  
  14.                     'recorremos sub-vector (desde piv hasta vec(a))
  15.                     For b = a To Npiv + 1 Step -1
  16.                         vec(b) = vec(b - 1)
  17.                     Next
  18.  
  19.                     vec(Npiv) = aux   'colocamos numero menor a la izquierda de piv
  20.                     Npiv += 1         'actualizamos posicion de piv
  21.                 End If
  22.             End If
  23.         Next
  24.  
  25.         'enviamos recursivamente el vector a la izuierda de piv
  26.         If (Npiv - primero <> 0) Then 'si el sub-vector de la izquierda tiene elementos, entonces se hace recursividad
  27.             vec = quicksort(vec, primero, Npiv - 1)
  28.         End If
  29.  
  30.         'enviamos recursivamente el vector a la derecha de piv
  31.         If (ultimo - Npiv <> 0) Then 'si el sub-vector de la derecha tiene elementos, entonces se hace recursividad
  32.             vec = quicksort(vec, Npiv + 1, ultimo)
  33.         End If
  34.  
  35.         Return vec
  36.     End Function
  37.  
  38.     Private Function getMilisegundos(ByVal fecha As Date) As Long
  39.         Dim respuesta As Long = 0
  40.         Dim dteFechaAux As Date = New Date(1970, 1, 1, 0, 0, 0, 0)
  41.         respuesta = DateDiff(DateInterval.Second, dteFechaAux, fecha) * 1000 + fecha.Millisecond
  42.         Return respuesta
  43.     End Function
  44.  
  45.     Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
  46.         Dim vec1(19999) As Integer
  47.         Dim rand As New Random
  48.         Dim a As Integer
  49.         Dim str1 As String
  50.         Dim tim1I As Long = 0
  51.         Dim tim1F As Long = 0
  52.  
  53.         'llenamos el primer vector de numeros aleatorios
  54.         For a = 0 To vec1.Length - 1
  55.             vec1(a) = rand.Next(0, 101)
  56.         Next
  57.  
  58.         'ordenamos vector con metodo de QickSort y contamos el tiempo trancurrido y total de intercambios
  59.         tim1I = getMilisegundos(DateTime.Now) 'tiempo inicial
  60.  
  61.         'ordenamos
  62.         vec1 = quicksort(vec1, 0, vec1.Length - 1) 'le enviamos el vector, el primer elemento y el ultimo
  63.  
  64.         tim1F = getMilisegundos(DateTime.Now) 'tiempo final
  65.  
  66.         'imprimimos vectores 1,2 y 3 ordenados
  67.         txt1.Text = ""
  68.         str1 = ""
  69.         For a = 0 To vec1.Length - 1
  70.             str1 &= vec1(a) & vbNewLine
  71.         Next
  72.  
  73.         txt1.Text = str1
  74.  
  75.         'imprimimos resultados
  76.         lblcomp1.Text = ""
  77.         lblinter1.Text = ""
  78.         lbltime1.Text = ""
  79.  
  80.         lbltime1.Text = "Tiempo: " & CType((tim1F - tim1I), String) & " ms"
  81.     End Sub
  82. End Class

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

147577693785ca3ea229202308f9eaa9
Share via email