Estudiante

METODOS DE ORDENAMIENTO EN PROGRAMACION C++

Ordenamiento de Burbuja (Método de intercambio)
Es uno de los métodos relativamente más sencillo e intuitivo, pero también resulta ser muy ineficiente. Se basa en la ordenación por cambio, y recibe su nombre de la semejanza con las burbujas de un depósito de agua donde cada burbuja busca su propio nivel. Los pasos a efectuar en el caso de unaordenación ascendente (en el caso de la ordenación descenderte solo habría que cambiar el signo de comparación) son:

1. Comparar el primer y segundo elemento, intercambiarlos si el primero es mayor que el segundo, luego se compara el primero con el tercero, intercambiándose en caso necesario, y el proceso se repite hasta llegar al último elemento. De este modo, tras la primera iteración la casillaprimera conservara el elemento más pequeño de esa iteración.

2. Se repite el paso anterior, pero ahora con el segundo y tercero, en caso de ser necesario se intercambian, y así hasta llegar a comparar el segundo con el último.

En el código de C++ las líneas que determinan este tipo de ordenamiento son las siguientes:
/* ordenamiento de burbuja */
for (int i = 0; i < n-1; i++)
for (int j= i + 1; j < n; j++) {
if ( v[i] > v[j] ) { //realiza la comparación
int tem = v[i]; //si es cierta intercambia los datos
v[i] = v[j];
v[j] = tem;
}
}
}
Ordenamiento de Burbuja Mejorada
Existe una versión mejorada de dicho algoritmo en donde se integra una variable que funge como switch (bandera) que permite detectar el momento en que ya no se presenten mas intercambios aunque sumejora no suele ser tan importante pues el algoritmo sigue comportándose como una ordenación cuadrática O(n2).

void burbuja_mej(int *v, int n) /*** código en C++ ***/
{
bool sw = true;
int li = 0;
do {
li++;
sw = true;
for (int i = 0; i < n - li; i++) {
if ( v[i] > v[i+1] ) { // compara los valores
// intercambia los datos
int tem = v[i];
v[i] = v[i+1];
v[i+1] = tem;
sw =false;
}
}
} while(!sw); }
Ordenamiento Quicksort.
Es también conocido con el nombre de ordenamiento rápido. El método Quicksort basa su estrategia en la idea intuitiva de que es más fácil ordenar una gran estructura de datos subdividiéndolas en otras más pequeñas introduciendo un orden relativo entre ellas. En otras palabras, si dividimos el array a ordenar como en dos subarrays de forma que loselementos del subarray inferior sean más pequeños que los del subarray superior, y aplicamos el método reiteradamente, al final tendremos el array inicial totalmente ordenado.
Codigo de Quicksort:
void quicksort (int arreglo[], int inf, int sup)
{
int elem_div = arreglo[sup];
int temp ;
int i = inf - 1, j = sup;
int cont = 1;if (inf >= sup) /* Se cruzaron los indices ? */
return;
while (cont)
{
while (arreglo[++i] < elem_div);
while (arreglo[--j] > elem_div); /*Aquí es donde se revisa si se cumple la condición*/
if (i < j) {
temp = arreglo[i];
arreglo[i] = arreglo[j];arreglo[j] = temp;
}
else
cont = 0;
}

Ordenamiento de Búsqueda Binaria.
La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. La búsqueda binaria es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento centraldel arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento...