EVAP7

MÉTODOS DE ORDENAMIENTO

Hoy les comparto los métodos de ordenamiento de datos más populares que hay, unos más eficientes que otros pero todos conocidos, y de una vez les mostraré un poco de C# para que se den cuenta de la similitud con Java, los ejemplos en código están en ambos lenguajes.

ORDENAMIENTO BURBUJA:

Es el algoritmo de ordenamiento más sencillo de todos, conocido también como método del intercambio directo, el funcionamiento se basa en la revisión de cada elemento de la lista que va a ser ordenada con el elemento siguiente, intercambiando sus posiciones si están en el orden equivocado, para esto se requieren varias revisiones hasta que ya no se necesiten más intercambios, lo que indica que la lista ha sido ordenada.

El origen del nombre de este algoritmo proviene de la forma con la que suben por la lista los elementos durante los intercambios, tal y como si fueran "burbujas", el algoritmo fundamental de este método es la simple comparación de elementos siendo así el más fácil de implementar.

EJEMPLO: 

Public int[] OrdenarBurbuja(int[]x)
{

        int t= x.Length, temp;

        for(int i=1 ; i< t ; i++)
        {

                for(int j = t-1 ; j >= i; j--)

                {

                        if(x[j] < x[j-1])

                        {

                                temp= x[j];

                                x[j]= x[j-1];

                                x[j-1]= temp;

                        }

                }

        }

}

ORDENAMIENTO RÁPIDO: 

Es el algoritmo de ordenamiento más eficiente de todos, se basa en la técnica de "Divide y Vencerás", que permite en promedio, ordenar n elementos en un tiempo proporcional a n*log(n).
Algoritmo Fundamental:

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.


Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.





 EJEMPLO:


void Quicksort(int[] v, int prim, int ult)
{
 if (prim < ult)
 {
  /*Selecciona 1 elemento del vector y coloca los menores
   que él a su izq y los mayores a su derech*/
  int p = Pivote(v, prim, ult, ult);
 
  /* Repite el proceso para c/u de las particiones
     generadas en el paso anterior */
  Quicksort(v, prim, p - 1);
  Quicksort(v, p + 1, ult);
 }
}
 
/* Implementación no clásica de la función Pivote. En lugar de
recorrer el vector simultáneamente desde ambos extremos hasta el
cruce de índices, se recorre desde el comienzo hasta el final */
int Pivote(int[] v, int prim, int ult, int piv)
{
 int p = v[piv];
 int j = prim;
 
 // Mueve el pivote a la última posición del vector
 Intercambia(v, piv, ult);
 
 /* Recorre el vector moviendo los elementos menores
  o iguales que el pivote al comienzo del mismo */
 for (int i = prim; i < ult; i++)
 {
  if (v[i] <= p)
  {
   Intercambia(v, i, j);
   j++;
  }
 }
 
 // Mueve el pivote a la posición que le corresponde
 Intercambia(v, j, ult);
 
 return j;
}
 
void Intercambia(int[] v, int a, int b)
{
 if (a != b)
 {
  int tmp = v[a];
  v[a] = v[b];
  v[b] = tmp;
 }
}

ORDENAMIENTO POR MONTICULOS: 


Es un algoritmo de ordenamiento no recursivo, no estable, consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

 EJEMPLO:


public class heap_Sort
{
      public static void main(String a[])
      {
            int i;
            int arr[] = {1,3,4,5,2};
            System.out.println("Heap Sort");   
            System.out.println("\n---------------\n");
            System.out.println("\nUnsorted array\n\n");
            for (i = 0; i < arr.length; i++)
                  System.out.print(" "+arr[i]);
            for(i=arr.length; i>1; i--)
            {
                  fnSortHeap(arr, i - 1);
            }
            System.out.println("Sorted array");
            System.out.println("\n---------------\n");
            for (i = 0; i < arr.length; i++)
            {
                  System.out.print(" "+arr[i]);
            }
            public void fnSortHeap(int arr[], int arr2)
            {
                  int i, o;
                  int lCh, rCh, mCh, root, tmp;
                  root = (arr2-1)/2;

                  for(o = root; o >= 0; o--)
                  {
                        for(i=root;i>=0;i--)
                        {
                              lCh = (2*i)+1;
                              rCh = (2*i)+2;
                              if((lCh <= arr2) && (rCh <= arr2))
                              {
                                    if(arr[rCh] >= arr[lCh])
                                    {
                                          mCh = rCh;
                                    }
                                    else
                                    {
                                          mCh = lCh;
                                    }
                              }
                              else
                              {
                                    if(rCh > arr2)
                                    {
                                          mCh = lCh;
                                    }
                                    else
                                    {
                                          mCh = rCh;
                                    }
                              }

                              if(arr[i] < arr[mCh])
                              {
                                    tmp = arr[i];
                                    arr[i] = arr[mCh];
                                    arr[mCh] = tmp;
                              }
                        }
                  }
                  tmp = arr[0];
                  arr[0] = arr[arr2];
                  arr[arr2] = tmp;
                  return;
            }
      }
}

EVAP6

MATRICES

Una matriz es un vector de vectores o un también llamado array bidimensional. La manera de declarar una matriz es C++ es similar a un vector:

Puede almacenar distintas variables del mismo tipo en una estructura de datos de matriz. Para declarar una matriz especifique el tipo de sus elementos.

INFORMACION GENERAL DE MATRICES:

Una matriz tiene las propiedades siguientes:

• Una matriz puede ser unidimensional, multidimensional o escalonada.
• El número de dimensiones y la longitud de cada dimensión se establecen cuando se crea la instancia de la matriz. Estos valores no se pueden cambiar durante la duración de la instancia.
• Los valores predeterminado de los elementos numéricos de matriz se establece en cero y el de los elementos de referencia se establece en null.
• Una matriz escalonada es una matriz de matrices y por consiguiente sus elementos son tipos de referencia y se inicializan en null.
• Las matrices se indizan basadas en cero: una matriz con n elementos se indiza desde 0 hasta n-1.
• Los elementos de una matriz pueden ser de cualquier tipo, incluido el tipo matriz.
• Los tipos de matriz son tipos de referencia derivados del tipo base abstracto Array. Puesto que este tipo implementa IEnumerable e IEnumerable<T>, puede utilizar la iteración foreach en todas las matrices de C#.

EJEMPLO:

class TestArraysClass
{
    static void Main()
    {
        // Declare a single-dimensional array 
        int[] array1 = new int[5];

        // Declare and set array element values
        int[] array2 = new int[] { 1, 3, 5, 7, 9 };

        // Alternative syntax
        int[] array3 = { 1, 2, 3, 4, 5, 6 };

        // Declare a two dimensional array
        int[,] multiDimensionalArray1 = new int[2, 3];

        // Declare and set array element values
        int[,] multiDimensionalArray2 = { { 1, 2, 3 }, { 4, 5, 6 } };

        // Declare a jagged array
        int[][] jaggedArray = new int[6][];

        // Set the values of the first array in the jagged array structure
        jaggedArray[0] = new int[4] { 1, 2, 3, 4 };
    }
}

EVAP 5

VECTORES 

En programación, un vector (llamado en inglés array) es una zona de almacenamiento continuo, que contiene una serie de elementos del mismo tipo, los elementos de la matriz. Desde el punto de vista lógico una matriz se puede ver como un conjunto de elementos ordenados en fila (o filas y columnas si tuviera dos dimensiones).

En principio, se puede considerar que todas las matrices son de una dimensión, la dimensión principal, pero los elementos de dicha fila pueden ser a su vez matrices (un proceso que puede ser recursivo), lo que nos permite hablar de la existencia de matrices multidimensionales, aunque las más fáciles de imaginar son los de una, dos y tres dimensiones.

Estas estructuras de datos son adecuadas para situaciones en las que el acceso a los datos se realice de forma aleatoria e impredecible. Por el contrario, si los elementos pueden estar ordenados y se va a utilizar acceso secuencial sería más adecuado utilizar una lista, ya que esta estructura puede cambiar de tamaño fácilmente durante la ejecución de un programa.

Todo vector se compone de un determinado número de elementos. Cada elemento es referenciado por la posición que ocupa dentro del vector. Dichas posiciones son llamadasíndice y siempre son correlativos. Existen tres formas de indexar los elementos de una matriz:

• Indexación base-cero (0): en este modo el primer elemento del vector será la componente cero ('0') del mismo, es decir, tendrá el índice '0'. En consecuencia, si el vector tiene 'n' componentes la última tendrá como índice el valor 'n-1'. El lenguaje C es un ejemplo típico que utiliza este modo de indexación.

• Indexación base-uno (1): en esta forma de indexación, el primer elemento de la matriz tiene el índice '1' y el último tiene el índice 'n' (para una matriz de 'n' componentes).

• Indexación base-n (n): este es un modo versátil de indexación en la que el índice del primer elemento puede ser elegido libremente, en algunos lenguajes de programación se permite que los índices puedan ser negativos e incluso de cualquier tipo escalar (también cadenas de caracteres).

FORMA DE ACCESO:

La forma de acceder a los elementos de la matriz es directa; esto significa que el elemento deseado es obtenido a partir de su índice y no hay que ir buscándolo elemento por elemento (en contraposición, en el caso de una lista, para llegar, por ejemplo, al tercer elemento hay que acceder a los dos anteriores o almacenar un apuntador o puntero que permita acceder de manera rápida a ese elemento).

Para trabajar con vectores muchas veces es preciso recorrerlos. Esto se realiza por medio de bucles. El siguiente pseudocódigo muestra un algoritmo típico para recorrer un vector y aplicar una función '' a cada una de las componentes del vector:

i = 0
mientras (i < longitud)
    #Se realiza alguna operación con el vector en la i-ésima posición
    f(v[i])
    i=i+1
fin_mientras

EJEMPLO:

• Declaración en C/C++ de un vector estático.

int main(void)
{
  int i, v[5];  // v[5] es un vector de 5 componentes
 
  for(i=0; i<5; i++)
  {
    v[i] = 0; // Asignamos un valor
    printf("%d\n", v[i]);
    printf("\n");  // Crea una nueva línea
  }
  return 0
}