Please enable JavaScript.
Coggle requires JavaScript to display documents.
Métodos de Ordenamiento (Burbuja (Características (La técnica consiste en…
Métodos de Ordenamiento
Burbuja
Características
Se basa en la ordenación por cambios de elementos, ya que se van comparando de dos en dos los elementos de la tabla
La técnica consiste en hacer varias pasadas a través de la tabla, en cada pasada se comparan parejas sucesivas de elementos.
Si una pareja esta en orden creciente (o los valores son idénticos), se dejan los valores como están.
Si una pareja esta en orden decreciente, sus valores se intercambian en la tabla.
Algoritmo
public static void burbuja(int[]matrix){
int temp;
for(int i=1;i < matrix.length;i++){
for (int j=0 ; j < matrix.length- 1; j++){
if (matrix[j] > matrix[j+1]){
temp = matrix[j];
matrix[j] = matrix[j+1];
matrix[j+1] = temp;
}}}}
Quicksort
Características
Se basa en la técnica divide y vencerás
Consiste en ir subdividiendo el array en arrays más pequeños, y ordenar éstos
Para hacer esta división, se toma un valor del array como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha
Se aplica el mismo método a cada una de las dos partes en las que queda dividido el array.
De izquierda a derecha, buscando un elemento mayor que el pivote
De derecha a izquierda, buscando un elemento menor que el pivote.
La implementación del método de ordenación Quicksort es recursiva.
Algoritmo
public static void quicksort(int A[], int izq, int der) {
int pivote=A[izq];
int i=izq;
int j=der;
int aux;
while(i<j){ while(A[i]<=pivote && i<j) i++; while(A[j]>pivote) j--;
if (i<j) {
aux= A[i];
A[i]=A[j];
A[j]=aux;
}}
A[izq]=A[j];
A[j]=pivote;
if(izq<j-1)
quicksort(A,izq,j-1);
if(j+1 <der)
quicksort(A,j+1,der);
}
Shell
Características
Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos
Mejora este tiempo comparando cada elemento con el que está a un cierto número de posiciones llamado salto, en lugar de compararlo con el el que está justo a su lado.
Este salto es constante, y su valor inicial es N/2
Se van dando pasadas con el mismo salto hasta que en una pasada no se intercambie ningún elemento de sitio.
Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.
Algoritmo
public static void shell(int A[]){
int salto, aux, i;
boolean cambios;
for(salto=A.length/2; salto!=0; salto/=2){
cambios=true;
while(cambios){
cambios=false;
for(i=salto; i< A.length; i++){
if(A[i-salto]>A[i]){
aux=A[i];
A[i]=A[i-salto];
A[i-salto]=aux;
cambios=true;
}}}}
Mergesort
Características
Es un algoritmo de ordenación recursivo con un número de comparaciones entre elementos del array mínimo.
Basado en la técnica divide y vencerás.
Funcionamiento
Si la longitud del array es menor o igual a 1 entonces ya está ordenado.
El array a ordenar se divide en dos mitades de tamaño similar.
Cada mitad se ordena de forma recursiva aplicando el método MergeSort.
Las dos mitades ya ordenadas se mezclan formando una secuencia ordenada.
Algoritmo
public static void mergesort(int A[],int izq, int der){
if (izq<der){
int m=(izq+der)/2;
mergesort(A,izq, m);
mergesort(A,m+1, der);
merge(A,izq, m, der);
}}
Rick Brandon López Noguez