Ordenamiento de vectores por metodo burbuja y otros.

                           ORDENACIÓN POR EL MÉTODO DE LA BURBUJA

Este método consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande el la última posición, una vez acomodado el más grande, prosigue a encontrar  y acomodar el siguiente más grande comparando de nuevo los numeros desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo. Este algoritmo es muy deficiente ya que al ir comparando las casillas para buscar el siguiente más grande, éste vuelve a comparar las ya ordenadas. A pesar de ser el algoritmo de ordenamiento más deficiente que hay, éste es el más usado en todos los lenguajes de programación.

Entonces:

Dado un vector a₁, a₂, a₃, ... a_n

1) Comparar a1 con a₂ e intercambiarlos si a₁>a₂ (o a₁2)

2) Seguir hasta que todo se haya comparado a_n-1 con a_n

3) Repetir el proceso anterior n-1 veces

                                     Algoritmo:    

                                           

    for(i=0; i < n-1; i++){                           

           for(j=0; j < n-1; j++){                    

                if(vec[j] > vec[j+1]){               

                        aux=vec[j];                    

                        vec[j]=vec[j+1];            

                        vec[j+1]=aux;}              

                                                     }

                                          }

    El procedimiento de la burbuja es el siguiente:

• Ir comparando desde la casilla 0 numero tras número hasta encontrar uno mayor, si este es realmente  el mayor de todo el vector se llevará hasta la última casilla, si no es así, será reemplazado por uno mayor que él.
• Este procedimiento seguirá así hasta que halla ordenado todas las casillas del vector.
• Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.

                        Ejemplo:

Variables				Vector
				pos	0	1	2	3	4	5	6	7
i	j	a[j]	a[j+1]	inicio	44	55	12	42	94	18	6	67
0	1	55	12	cambio	44	12	55	42	94	18	6	67
0	2	55	42	cambio	44	12	42	55	94	18	6	67
0	4	94	18	cambio	44	12	42	55	18	94	6	67
0	5	94	6	cambio	44	12	42	55	18	6	94	67
0	6	94	67	cambio	44	12	42	55	18	6	67	94
1	0	44	12	cambio	12	44	42	55	18	6	67	94
1	1	44	42	cambio	12	42	44	55	18	6	67	94
1	3	55	18	cambio	2	42	44	18	55	6	67	94
1	4	55	6	cambio	12	42	44	18	6	55	67	94
2	2	44	18	cambio	12	42	18	44	6	55	67	94
2	3	44	6	cambio	12	42	18	6	44	55	67	94
3	1	42	18	cambio	12	18	42	6	44	55	67	94
3	2	42	6	cambio	12	18	6	42	44	55	67	94
4	1	18	6	cambio	12	6	18	42	44	55	67	94
5	0	12	6	ordenado	6	12	18	42	44	55	67	94

Otros tipos de ordenamiento.

 SelectionSort.

Entre los métodos elementales de ordenación de vectores se encuentra el algoritmo de selección:

for (i=0; i<n; i++)
{
  imin=i;
  for (j=i+1; j<n; j++)
  {
    if(V[j]<V[imin])
    imin=j;
  }
  aux = V[i];
  V[i] = V[imin];
  V[imin] = aux;
}

Es decir, el método se basa en buscar en cada iteracción el mínimo elemento del “subvector” situado entre el índice i y el final del vector e intercambiarlo con el de índice i. Tomando la dimensión del vector n como tamaño del problema es inmediato que el bucle se repite n veces y por tanto la función que da el número de repeticiones es de tipo lineal (O(n)). La operación interior al bucle se puede desarrollar a su vez como:

imin:=i;
para j desde i+1 hasta n hacer
  si V[j]<V[imin] entonces imin:=j fsi
fpara
intercambiar(V[i],V[imin])

Se trata de una secuencia de tres operaciones, la segunda de las cuales es, a su vez, una iteración. La primera (asignación) y la tercera(intercambio) pueden considerarse de coste constante. La segunda es un bucle que internamente incluye una operación condicional que en el peor caso supone una operación de coste constante (O(1)) (en el peor caso y en el mejor, puesto que la comparación se ha de realizar siempre ) y el número de repeticiones de esa operación es de tipo lineal, ya que se realiza n-(i+1) veces, y por tanto, al crecer n, el número de veces crece proporcionalmente a n. Luego será de costeO(n) O(1) = O(n). Éste será entonces el coste de la secuencia completa (sucesión de dos operaciones de coste constante y una de coste lineal)

El algoritmo total será entonces de ordenO(n).O(n) =O(n^2)

Es interesante observar que en este algoritmo el contenido de los datos de entrada, no influye en el coste del algoritmo. En efecto se puede comprobar (aplicar el algoritmo sobre varios vectores ejemplo), que se ejecutan de forma completa ambos bucles tanto para vector desordenado como para vector ordenado.

InsertionSort

En este procedimiento se recurre a una búsqueda binaria en lugar de una búsqueda secuencial para insertar un elemento en la parte de arriba del arreglo, que ya se encuentra ordenado. El proceso, al igual que en el método de inserción directa, se repite desde el segundo hasta el n-ésimo elemento.

algoritmo:

for(i=1; i<n; i++) {
  temp = V[i];
  Izq = 0;
  Der = i-1;
  while(Izq <= Der){
    Medio = (Izq+Der)/2;
    if (temp < V[Medio])
      Der = Medio - 1;
    else
      Izq = Medio + 1;
  }
  for (j=i-1; j>=Izq; j--){
    V[j+1]=V[j];
  }
  V[Izq] = temp;
}

ShellSort

Denominado así por su desarrollador Donald Shell (1959), ordena una estructura de una manera similar a la del Bubble Sort, sin embargo no ordena elementos adyacentes sino que utiliza una segmentación entre los datos. Esta segmentación puede ser de cualquier tamaño de acuerdo a una secuencia de valores que empiezan con un valor grande (pero menor al tamaño total de la estructura) y van disminuyendo hasta llegar al '1'.

Este método funciona de la siguiente manera:

• Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.
• Después de que los primeros K subgrupos han sido ordenados, se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
• Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.
• Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
• "Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos."
• Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.
• El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.

Algoritmo:

void shellSort(int a[], int h)
{
  int i;
  while (h > 0)
  { for (i = h-1; i<n; i++)
    {
       int B = a[i];
       int j = i;
       for (j = i; (j >= h) && (a[j - h] > B); j -= h)
       { a[j] = a[j - h];}
         a[j] = B;
     }
       h = h / 2;
  }
}

MergeSort

El algoritmo Merge divide el arreglo original en dos arreglos y los coloca en arreglos separados. Cada arreglo es recursivamente ordenado y finalmente se unen los arreglos en un arreglo ordenado. Como cualquiera de los algoritmos de ordenamiento recursivo el algoritmo Merge tiene complejidad de O(n log n). Fue desarrollado por John Von Neumann.

Algoritmo:

void ordenarMezcla(TipoEle A[], int izq, int der)
{ if ( izq < der )
  { centro = ( izq + der ) % 2;
    ordenarMezcla( A, izq, centro );
    ordenarMezcla( A, centro+1, der);
    intercalar( A, izq, centro, der );
  }
}
void intercalar(TipoEle A[], int a, int c, int b )
{ k = 0;
  i = a;
  j = c + 1;
  n = b - a;
  while ( i < c + 1 ) && ( j < b + 1 )
  { if ( A[i] < A[j] )
    { B[k] = A[i];
      i = i + 1;
    }
    else
    { B[k] = A[j];
      j = j + 1;
    }
   k = k + 1;
  };
while ( i < c + 1 )
{ B[k] = A[i];
  i++;
  k++;
};
while ( j < b + 1 )
{ B[k] = A[j];
  j++;
  k++;
};
i = a;
for ( k = 0; k < n; i++ )
{ A[i] = B[k];
  i++;
};
};