Arreglos

Un arreglo (matriz, vector, lista) es un tipo especial de objeto compuesto por una colección de elementos del mismo tipo de datos que se almacenan consecutivamente en memoria. Ej.

Propiedades de Arreglos 

• Los arreglos son objetos.

• Son creados dinámicamente (en run time).

• Pueden ser asignados a variables de tipo Object .

• Cualquier método de la clase Object puede ser invocado en un arreglo.

• Un objeto arreglo contiene una secuencia de variables del mismo tipo.

• Las variables son llamadas los componentes del arreglo.

Arreglos Lineales o Unidimensionales

Estos arreglos constituyen una lista de variables relacionadas. La forma de acceso a cada uno de sus diferentes valores, es usando acompañando al nombre de la variable más un índice: nombreArreglo [índice]. Los índices están en el rango de 0 a tamaño-1.

Declaración: tipoDato[] nombreArreglo;

o

tipoDato nombreArreglo [];

Creación:NombreArreglo = new tipoDato[n];

Ejemplo: int lista[];

lista= new int[10]; 

InicializacióntipoDatonombreArreglo[]={valor1,valor2,…,valorN};
//Este caso no  requiere el uso de new

Tipos de ordenamiento 

Ordenamiento interno.

Se lleva a cabo completamente en memoria principal. Todos los objetos que se ordenan caben en la memoria principal de la computadora.

Ordenamiento externo.

No cabe toda la información en memoria principal y es necesario ocupar memoria secundaria. El ordenamiento ocurre transfiriendo bloques de información a memoria principal en donde se ordena el bloque y este es regresado, ya ordenado, a memoria secundaria.

1. Metodo Burbuja (Bubble Sort)
   
   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.
   

   
   Codificación en java:- Programa principal
   package ordenarburbuja;
   import java.util.Scanner;
   public class OrdenarBurbuja {
   
       public static void main(String[] args) {
   
           Scanner orderbur= new Scanner(System.in);
           int num;
           System.out.println("Ingrese la cantidad de posiciones que tendra el vector ");
           num=orderbur.nextInt();
           System.out.println("Ingrese los datos del vector");       
           Scanner ordenar = new Scanner(System.in);
           int vector[] = new int[30];
           int i,j,aux;
           for (i=0;i<num;i++)
           {
               System.out.print("A["+(i+1)+"]=");
               vector[i]=ordenar.nextInt();
           }
           for (i=0;i<num;i++)
           {
               for (j=i+1;j<num;j++)
               {
                   if (vector[i]>vector[j])
                   {
                       aux=vector[i];
                       vector[i]=vector[j];
                       vector[j]=aux;
                   }
               }
           }
           System.out.print("El vector es = [");
           for (i=0;i<num;i++)
           {
               System.out.print(vector[i]+ ", ");
           }
           System.out.print("]");
           }
       } 
2.  Metodo Insersion directa (Insert Sort)Este método también se denomina “método del jugador de cartas”, por la semejanza con la forma de clasificar las cartas de una baraja, insertando cada carta en el lugar adecuado. El algoritmo ordena los dos primeros elementos de la lista, a continuación el tercer elemento se inserta en la posición que corresponda, el cuarto se inserta en la lista de tres elementos, y así sucesivamente. Este proceso continua hasta que la lista este totalmente ordenada. Sea una lista A[1], A[2], ... A[n]. Los pasos a dar para una ordenación ascendente son: 1. Ordenar A[1] y A[2].
   2. Comparar A[3] con A[2], si A[3] es mayor o igual a que A[2], sigue con el siguiente elemento si no se compara A[3] con A[1]; si A[3] es mayor o igual que A[1], insertar A[3] entre A[1] yA[2]. Si A[3] es menor que A[1], entonces transferir A[3] a A[1], A[1] a A[2] y A[2] a A[3].
   3. Se suponen ordenados los n-1 primeros elementos y corresponde insertar el n-ésimo elemento. Si A[m] es mayor que A[k] (con K = 1, 2, ..., m-1), se debe correr una posición A[k+1], ... A[m-1] y almacenar A[m] en la posición k+1.
   
   
   
   Codificación en Java:
   
   - Programa principal
   package insercion;
   
   import java.util.Scanner;
   public class Insercion {
       public static void main(String[] args) {
   
           Scanner numero= new Scanner(System.in);
           int num;
           System.out.println("Ingrese la cantidad de posiciones que tendra el vector ");
           num=numero.nextInt();
           System.out.println("Ingrese los datos del vector");       
           Scanner ordenar = new Scanner(System.in);
           int vector[] = new int[num];
           int aux;
           int x,y;
          
           for (int i=0;i<num;i++)
           {
               System.out.print("A["+(i+1)+"]=");
               vector[i]=ordenar.nextInt();
           }
              
               for (x=1 ; x < vector.length; x++)
               {
                   aux = vector[x];
                  
                   for (y = x-1; y >=0 && vector [y]>aux ; y --)
                   {
                       vector[y+1] = vector [y];
                       vector [y] = aux;
                   }
               }
                    System.out.println("El nuevo vector es: ");
                    for(int i=0; i<vector.length; i++)
                       {   
                           System.out.println(vector[i]);
                       }
       }
      
   }
3.  Metodo de Seleccion
   La idea básica es encontrar el elemento más pequeño (grande), en orden ascendente de la lista, e intercambiarlo con el elemento que ocupa la primera posición en la lista, a continuación se busca el siguiente elemento más pequeño y se transfiere a la segunda posición. Se repite el proceso hasta que el último elemento ha sido transferido a su posición correcta. El algoritmo de ordenación depende a su vez del algoritmo necesario para localizar el componente mayor (menor) de un array. Es un proceso muy similar al método de la burbuja pero haciendo más eficiente la búsqueda y evitando intercambios innecesarios.
   
   Codificación en Java:
   
   - Programa principal
   
   package ordenamientoporseleccion;
   
   import java.util.Scanner;
   public class OrdenamientoporSeleccion {
       public static void main(String[] args) {
   
           Scanner numero= new Scanner(System.in);
           int num;
           System.out.println("Ingrese la cantidad de posiciones que tendra el vector ");
           num=numero.nextInt();
           System.out.println("Ingrese los datos del vector"); 
          
           Scanner orderselec = new Scanner(System.in);
           int vector[] = new int[num];
          
           for (int i=0;i<num;i++)
           {
               System.out.print("A["+(i+1)+"]=");
               vector[i]=orderselec.nextInt();
           }
         
           OrdenarSe r=new OrdenarSe();
               r.ordselecc(vector);
               r.imprimir(vector);
       }
      
   }
   
   - Clase
   
   package ordenamientoporseleccion;
   public class OrdenarSe {
      
      public void ordselecc(int vector2[]){
          
           for (int i=0;i < vector2.length -1 ; i++){
                   int min=i;
                   for(int j= i+1; j< vector2.length ; j++){
                           if(vector2[j]< vector2[min]){
                                   min=j;
                               }
                       }
                   int aux = vector2[i];
                   vector2[i] = vector2[min];
                   vector2 [min] = aux;
               }
          
           } 
      
       public void imprimir(int vector2[]){
                System.out.println("El nuevo vector es: ");
                    for(int i=0; i<vector2.length; i++)
                       {   
                           System.out.println(vector2[i]);
                       }
           }
      
   }
4.  Metodo Heap Sort (Ordenamiento por Montículos)
   
   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.
   
   
   Codificación en Java:
   
   - Programa principal
   
   package ordenamientoporheap;
   
   import java.util.Scanner;
   public class Ordenamientoporheap {
   
         Scanner numero= new Scanner(System.in);
         int num;
         System.out.println("Ingrese la cantidad de posiciones que tendra el vector ");
         num=numero.nextInt();
         System.out.println("Ingrese los datos del vector"); 
          
         Scanner orderselec = new Scanner(System.in);
         int vector[] = new int[num];
          
           for (int i=0;i<num;i++)
            {
               System.out.print("A["+(i+1)+"]=");
                 vector[i]=orderselec.nextInt();
            }
              
               for(int i=vector.length; i>1; i--)
               {
                   HeapSort r=new HeapSort();
                   r.fnSortHeap(vector, i-1);
               }
               System.out.println("El vector ordenado es: ");
               for (int i = 0; i < vector.length; i++)
               {
                     System.out.print(" "+vector[i]);
               }
         
       }
      
   }
   
   - Clase
   
   package ordenamientoporheap;
   public class HeapSort {
      
       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;
               }
         }
   
   
5.  Metodo Shell (Shell Sort)
   El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n²) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log² n) en el peor caso. Esto es mejor que las O(n²) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución. El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.Codificación en Java:- Programa principalpublic class Shell {
   
       public static void main(String[] args) {
   
           Scanner numero=new Scanner(System.in);
           int num;
           System.out.print("Ingrese el numero de elementos para el vector: ");
           num=numero.nextInt();
           int vector[] = new int[30];
           int aux;
           for (int i=0;i<num;i++)
           {
               System.out.print("Datos["+(i+1)+"]=");
               vector[i]=numero.nextInt();
           }
           for ( int increment = num / 2; increment > 0; increment =
           (increment == 2 ? 1 : (int) Math.round(increment / 2.2)))
           {
               for (int i = increment; i < num; i++)
               {
                   for (int j = i; j >= increment && vector[j - increment] >
                   vector[j]; j -= increment)
               {
               int temp = vector[j];
               vector[j] = vector[j - increment];
               vector[j - increment] = temp;
               }
               }
           }
           System.out.print("Arreglo= {");
           for (int i=0;i<num;i++)
           {
               System.out.print(vector[i]+ ", ");
           }
           System.out.print("}");
       }
      
   }
   
6.  Metodo Quick Sort (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:
   
   

   1. Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
   2. 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.
   3. 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.
   4. 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.
      
      
      

   Codificación en Java:
   
   
   
   - Programa principalpackage javaapplication7;
   
   public class JavaApplication7 {
       public static void main(String[] args) {
          
            System.out.println("El vector ingresado es 5, 8 ,6 ,3 ,9 ,45 ,76 ,9");
           int vector1 []= {5, 8 ,6 ,3 ,9 ,45 ,76 ,9};
          
           OrdenarQ o=new OrdenarQ();
           o.ordenarquicksort(vector1);
          
           for(int i=0; i<vector1.length; i++)
           {
                System.out.println(vector1[i]);
           }
          
       }
      
   }
   - Clasepackage javaapplication7;
   
   public class OrdenarQ {
       public void ordenarquicksort(int [] vector2)
       {
           vector2 = quicksort1(vector2);
       }
       public int[] quicksort1 (int numeros[])
       {
           return quicksort2 (numeros,0,numeros.length -1);
       }
       public int[] quicksort2 (int numeros[],int izq, int der)
           {
               if (izq >= der)
                   return numeros;
               int i=izq,d=der;
               if(izq != der)
                   {
                       int pivote;
                       int aux;
                       pivote= izq;
                       while (izq != der)
                           {
            while (numeros [der] >= numeros [pivote] && izq < der)
                                   der --;
             while (numeros [izq] < numeros [pivote] && izq<der)
                                       izq++;
                               if (der != izq)
                               {
                                   aux=numeros [der];
                                   numeros[der]= numeros [izq];
                                   numeros[izq]= aux;
                               }
                              
                               if (izq == der)
                               {
                                   quicksort2 (numeros,1,izq-1);
                                   quicksort2 (numeros,izq+1,d);
                               }
                           }
                   }
                       else
                               return numeros;
                          
                   return numeros;           
           }   
   }
   By: Jonathan P. Herrera S.