next up previous
Next: 2 Ejercicios Up: Práctica 6 Previous: Práctica 6

Subsecciones

1 Ordenación

Se considera ordenar como el proceso de reorganizar un conjunto dado de objetos en una secuencia especificada.

Dados los ítems $a_1, a_2,\dots,a_n$. Ordenar consiste en permutar estos ítems $a_{k_1},a_{k_2},\dots,a_{k}$ de forma que dada una función de ordenación $f$ se verifique: $f(a_{k_1}) \le f(a_{k_2}) \le \dots \le f(a_{k})$.

Método de la burbuja

El siguiente pseudocódigo describe el método de ordenación conocido como la burbuja:

             procedure burbuja;
               var i, j : indice; x: item;
             begin
               for i = 2 to n do
               begin
                 for j = n downto i do
                   if (a[j-1].clave > a[j].clave) then
                   begin
                     x = a[j-1];
                     a[j-1] = a[j];
                     a[j] = x;
                   end
               end
             end

El método quicksort

El quicksort es un método de ordenación basado en intercambios, que aplica que los intercambios sobre distancias largas son los más efectivos. El pseudocódigo del algoritmo es el siguiente:

                  procedure quicksort(iz, de: indice);
                    var i, j : indice; x, w: item;
                  begin
                    i = iz; 
                    j = de;
                    x = a[(iz + de) div 2];
                    repeat
                      while (a[i].clave < x.clave) do i = i + 1; 
                      while (x.clave < a[j].clave) do j = j - 1; 
                      if (i <= j) then
                        begin
                          w = a[i];
                          a[i] = a[j];
                          a[j] = w;
                          i = i + 1;
                          j = j - 1;
                        end
                    until i > j;
                    if iz < j then quicksort(iz, j);
                    if i < de then quicksort(i, de);
                  end;

Los algoritmos de ordenación descritos se han tomado del libro ``Algoritmos + Estructuras de Datos = Programas" de Niklaus Wirth.


next up previous
Next: 2 Ejercicios Up: Práctica 6 Previous: Práctica 6
Programación Avanzada 03-04