SEDE MANIZALES DNSAV

PROBLEMA DEL ORDENAMIENTO

Cómo ordenar ascendentemente un arreglo de n-números enteros. ALGORITMO DE ORDENAMIENTO POR INTERCAMBIO El algoritmo del intercambio aunque es el más sencillo de implementar es uno de los mas pobres en rendimiento, se basa en la idea de buscar cada vez el menor elemento del conjunto y ubicarlo al principio del mismo, repitiendo este proceso cada vez con el conjunto sin su primer elemento (el menor del conjunto anterior), hasta llegar a un conjunto de un solo elemento que por definición ya está ordenado. En cada paso del algoritmo se compara el primer elemento del conjunto x[i], con los demás elementos del mismo x[j] (j=i+1 .. n) y cuando x[i] es mayor que x[j], se intercambian sus valores. Cuando se termina de recorrer el arreglo el proceso nos garantiza que en x[i] está el menor elemento del conjunto. Teniendo en cuenta que el algoritmo de ordenamiento por intercambio se realiza siempre de la misma maneraindependiente de los datos que estén almacenados, no existe un mejor, peor o caso promedio y su complejidad siempre será O(n²)

	void ordenar1(int arreglo[ ], int n) {
		int temporal, i, j; for (i=0; i<n-1; i++) {
		for (j=i+1;j<n; j++){
				if (arreglo[i] > arreglo[j]) {
					temporal = arreglo[i]; arreglo[i] = arreglo[j]; arreglo[j] = temporal;
				}
				}
}
}
ALGORITMO DE LA BURBUJA La idea básica del ordenamiento de la burbuja es recorrer el conjunto de elementos en forma secuencial varias veces. Cada paso compara un elemento del conjunto con su sucesor (x[i] con x[i+i]), e intercambia los dos elementos si no están en el orden adecuado. El algoritmo utiliza una bandera que cambia cuando se realiza algún intercambio de valores,y permanece intacta cuando no se intercambia ningún valor, pudiendo así detener el ciclo y terminar el proceso de ordenamiento cuando no se realicen intercambios, lo que indica que este ya está ordenado. Este algoritmo es de fácil comprensión y programación pero es poco eficiente puesto que existen n-1 pasos y n-i comprobaciones en cada paso, aunque es mejor que el algoritmo de ordenamiento por intercambio.En el peor de los casoscuandoloselementos están en el orden inverso, el número máximo de recorridos es n-1 y el número deintercambios o comparaciones está dado por (n-1) (n-1) = n² - 2n + 1.En el mejor de los casos cuando los elementos están en su orden, el número de recorridos es mínimo 1 y el ciclo de comparaciones es n-1*.La complejidad del algoritmo de la burbuja es O(n)enel mejor de los casos y O(n²) en el peor de los casos, siendo su complejidad total O(n²).

	void ordenar2(int arreglo[], int n) {
		int temporal, i = 0, j, cambio = 1; while (i<n-1 && cambio == 1) {
				cambio=0; for (j=0; j<n-1, j++) {
					if (arreglo[j]>arreglo[j+1]) {
						cambio=1; temporal = arreglo[j]; arreglo[j] = arreglo[j+1]; arreglo[j+1] = temporal;
					}
				} i++;
			}
}

ALGORITMO DE ORDENAMIENTO POR INSERCION La estrategia del ordenamiento por inserción consiste en crear un nuevo arreglo vacío e irle insertando en la posición correcta cada uno de los elementos del arreglo original, hasta tener el arreglo ordenado. La desventaja de este método radica en su normal implementación mediante vectores ya que cuando se desea insertar un nuevo elemento en el vector, es necesario desplazar todos los elementos que hay desde ese punto hasta el final del arreglo, para así crear un espacio para el nuevo elemento: su implementación mediante listas encadenadas es más compleja pero mucho más eficiente.El tiempo requerido para ordenar los elementos depende significativamente del orden inicial, ya que se refleja en la cantidad de comparaciones que se debe realizar para encontrar la posición del nuevo valor y la cantidad de elementos que deben ser desplazados para su ubicación.Si los elementos están ordenados en sentido inverso en el peor de los casos, la complejidad es O(n)², ya que para insertar un elemento es necesario mover todos los que están delante de él, pero este algoritmo funciona mejor mientras el arreglo se encuentra más ordenado y como el tiempo de cada ciclo para insertar un elemento no es constante, ya que depende de la posición del elemento a insertar, esta variará entre 1 y n, y como se debe realizar para los n elementos, su complejidad será O(n)².

ALGORITMO DE ORDENAMIENTO RAPIDO (QUICK - SORT)
	void Insertar(int temporal[ ], int valor, int tam) {
		if (tam==0)
			temporal[0]=valor;
		else {
			int x = 0, y; while(temporal[x] < valor &&x < tam)
				x++;
			for(y=tam; y>x; y--)
				temporal[y]=temporal[y-1];
			temporal[x]=valor;
}
}

		void ordenar3 (int arreglo[ ], int n) {
			int temporal, x;* temporal = (int ) malloc(sizeof(int) * n);* for (x=0; x<n; x++)
				Insertar(temporal, arreglo[x], x);
			for (x=0; x<n; x++)
				arreglo[x]=temporal[x];
			free(temporal);
}


El algoritmo de ordenamiento rápido se basa en el principio de dividir y conquistar (ver sección 13.2 de este libro) y busca encontrar un pivote o elemento central (idealmente debe ser el elemento del medio), ubicarlo en la posición que le corresponde y luego ubicar todos los elementos menores que él a su izquierda y los mayores a su derecha; una vez realizado este proceso, se repite el proceso para el subconjunto de elementos a la izquierda del pivote y de igual manera para el subconjunto de elementos a la derecha del pivote. Este proceso implica el uso de la técnica de recursión en la cual un proceso se llama a sí mismo. La eficiencia del algoritmo depende de la escogencia del pivote, ya que si este no queda ubicado muy cerca de la mitad del conjunto puede desequilibrar el tamaño de los dos subconjuntos, generando un alto número de llamados recursivos. Analizando su eficiencia podemos encontrar que si los pivotes coinciden siempre en los extremos del arreglo, generará exactamente n particiones, lo que implicará una complejidad de O(n²), pero si el pivote esta siempre en la mitad, la complejidad será de O(nlog₂n).

	void Intercambio(intarreglo[], intposx, int posy) {
		inttemporal; temporal = arreglo[posx]; arreglo[posx] = arreglo[posy]; arreglo[posy] = temporal;
	}

	intmenores(intarreglo[ ], int inicio, int fin, int valor) {
		intcontador = 0, x; for (x=inicio; x<=fin; x++)
			if (arreglo[valor] > arreglo[x]) contador ++;
		return(contador);
}

		void particion(int arreglo[ ], int inicio, int fin, int medio) {
			intizquierda, derecha; izquierda=inicio;derecha=fin; while (izquierda < derecha) {
				while (arreglo[izquierda] < arreglo[medio])
					izquierda++;

				while (arreglo[derecha] > arreglo[medio])
					derecha--;
				if (izquierda < derecha)
					Intercambio(arreglo, izquierda, derecha);
			}
		}

		void quicksort(int arreglo[ ], int inicio, int fin) {
			intmedio; if (inicio < fin) {
				medio=inicio + menores(arreglo, inicio, fin, inicio); intercambio(arreglo, medio, inicio); particion(arreglo, inicio, fin, medio); quicksort(arreglo, inicio, medio-1); quicksort(arreglo, medio+1, fin);
			}
}

			void ordenar4(int arreglo[ ], int n) {
				quicksort(arreglo,0, n-1);
}
ALGORITMO DE ORDENAMIENTO POR MONTICULO (Heap - Sort)

Un montículo es una estructura de datos tipo árbol binario, cuya principal característica es que el nodo padre es mayor que sus hijos, sin importar la relación que haya entre los hijos. [5]El ordenamiento por montículo es el más lento de los algoritmos de ordenamiento con complejidad O(n log₂n) pero a diferencia de los ordenamientos de mezcla y rápido, no requiere de masivos llamados recursivos para encontrar una solución, lo que lo hace bastante atractivo para grandes conjuntos de datos. El funcionamiento del ordenamiento por montículo se basa en la construcción de un montículo de datos, el cual requiere de O(log₂ n) operaciones para insertar un elemento y como son n elementos, entonces la complejidad de su construcción es O(n log₂ n), y luego remueve cada uno de los elementos del montículo y lo ubica al final del arreglo; después de remover cada elemento se debe reconstruir el montículo para que siga cumpliendo con sus propiedades, lo que tiene una complejidad de O(log2 n); el proceso se realiza hasta que el montículo esté vacío, indicando que el arregloestá ordenado.

	void undir(int arreglo[], int raiz, int tope) {
		nt fin, hijo, temp;fin = 0; while ((raiz2 <= tope) && (!fin))* {
			if (raiz2 == tope)*
				hijo = raiz 2;*
			else
				if (arreglo[raiz 2] > arreglo[raiz * 2 + 1])*
					hijo = raiz 2;*
				else
					hijo = raiz 2 + 1;*
			if (arreglo[raiz] < arreglo[hijo]) {
				temp = arreglo[raiz]; arreglo[raiz] = arreglo[hijo]; arreglo[hijo] = temp;raiz = hijo;
			}
			else
				fin = 1;
}
			}

			void ordenar5(int arreglo[], int n) {
				int i, temp; for (i = (n / 2)-1; i >= 0; i--)
					undir(arreglo, i, n);
				for (i = n-1; i >= 1; i--) {
					temp = arreglo[0]; arreglo[0] = arreglo[i]; arreglo[i] = temp; undir(arreglo, 0, i-1);
				}
		}

ALGORITMO DE ORDENAMIENTO POR MEZCLA (Merge - Sort)

Mediante el enfoque de Dividir y conquistar, este algoritmo divide el arreglo inicial en dos arreglos donde cada uno contiene la mitad de los datos (partes iguales mas o menos uno), y se ordenan mediante sucesivos llamados recursivos para luego fusionar los resultados en el arreglo inicial. Este algoritmo se basa en una función que permite mezclar dos vectores ordenados, produciendo como resultado un tercervector ordenado que contiene los elementos de los dos vectores iniciales, el cual tiene una complejidad de O(n) para mezclar dos arreglos, donde n es la suma de los tamaños de los dos arreglos. El algoritmo principal que divide el arreglo, realiza O(log₂ n) particiones y como llama a la función que mezcla los dos arreglos y que tiene una complejidad de O(n), entonces la complejidad total del algoritmo será de O(n log₂ n).

	void mezclar(int arreglo1[], int n1,int arreglo2[],int n2, int arreglo3[]) {
		int x1,x2,x3; x1=x2=x3=0; while (x1<n1 && x2<n2) {
				if (arreglo1[x1]<arreglo2[x2]) {
					arreglo3[x3]=arreglo1[x1];x1++;
				}
				else {
					arreglo3[x3]=arreglo2[x2]; x2++;
				}
				x3++;
}
			while (x1<n1) {
				arreglo3[x3]=arreglo1[x1]; x1++; x3++; }
				while (x2<n2) {
					arreglo3[x3]=arreglo2[x2]; x2++; x3++;
				}
}


				void mezcla(int vector[], int n) {
					int vector1, vector2, n1, n2,x,y; if (n>1) {
					if (n%2 == 0)
							n1=n2=(int) n / 2;
					else {
							n1=(int) n / 2;n2=n1+1;
					}
					vector1=(int ) malloc(sizeof(int)n1); vector2=(int ) malloc(sizeof(int)n2); for(x=0;x<n1;x++)
							vector1[x]=vector[x];
					for(y=0;y<n2;x++,y++)
							vector2[y]=vector[x]; mezcla(vector1, n1); mezcla(vector2,n2); mezclar(vector1, n1, vector2, n2, vector); free(vector1); free(vector2);
						}
					}


					void ordenar6(int arreglo[], int n) {
							mezcla(arreglo,n);
}