Ordenamiento
En programación de computadoras, es de mucha importancia y se constituye en una herramienta fundamental los procesos de búsqueda de un valor, el trabajo con valores máximos y mínimos y la tarea de ordenamiento de un conjunto de datos.
Trataremos esos tres ejes temáticos partiendo de conjuntos de datos almacenados en arreglos vectoriales o listas. Iniciando el abordaje del tema con el apartado referente a la búsqueda de un valor determinado.
Ordenamiento de datos
Con relación a los algoritmos de ordenación, lo más importante al momento de seleccionar uno es la eficiencia, o sea, como se comporta cada uno al ordenar una gran cantidad de datos, se dice que los menos eficientes cumplen un orden cuadrático, es decir, O(n²), mientras que los algoritmos rápidos siguen un orden logarítmico, o sea, O (n log n).
Los algoritmos fundamentales de ordenamiento son:
· Ordenamiento burbuja
· Ordenamiento por selección
· Ordenamiento por inserción
La escogencia o selección del método de ordenamiento depende del tamaño del vector o lista a clasificar, además del tipo de datos y los recursos disponibles.
Ordenamiento por burbuja
El ordenamiento por burbuja es el algoritmo más sencillo. Consiste en recorrer tantas veces como sea necesario la lista de elementos a ordenar, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. Es un algoritmo estable, con el gran inconveniente de que es muy lento.
Dado que el método de burbuja compara elementos consecutivos de una lista, este puede ser mejorado si en un recorrido no se detectan intercambios, lo que significa que la lista está ordenada. Para mejorar el algoritmo basta con utilizar una variable centinela del tipo booleano que indique si se han producido intercambios en la pasada. Si el resultado es falso la lista está ordenada y se terminará la ejecución del mismo.
Ejemplo:
Escribir un algoritmo de ordenamiento por burbuja para un vector V de n elementos.
Algoritmo ordenación por burbuja
const TAM = 10
mostrarLista(entero lista[])
para(entero i = 0; i < TAM; i++)
escriba(lista[i])
fin-mostrarLista
inicio
entero V[TAM], i, j, aux;
escriba("Llenar arreglo con números aleatorios del 0 al 50)
para(i = 0; i < TAM; i++)
V[i] = aleatorio % 50;
//Recorrer el arreglo
Escriba("Intercambio en cada paso")
para(i = 0; i < TAM; i++)
para(j = 1; j < TAM - 1; j++)
si(V[j] > V[j + 1])
entonces
aux = V[j]
V[j] = V[j + 1]
V[j + 1] = aux
fin-si
fin-para
mostrarLista(V)
fin-para
escriba(“lista ordenada")
mostrarLista(V)
fin
Ordenamiento por inserción
El ordenamiento por inserción es la forma más lógica de ordenar en el quehacer cotidiano, por ejemplo, una pila de naipes. Su eficiencia es cuadrática O(n²).
Inicialmente se tiene un solo elemento, que por supuesto es un conjunto ordenado. Luego, conforme se va incrementando el número de datos, estos n elementos deberían estar ordenados de menor a mayor, para ello se toma el elemento n+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento n+1 con el lógico desplazamiento de los demás elementos.
Ejemplo:
Escribir un algoritmo de ordenamiento por inserción para un vector lista de n elementos.
Algoritmo ordenación por inserción
const TAM = 10
mostrarLista(entero lista[])
para(entero i = 0; i < TAM; i++)
escriba(lista[i])
fin-mostrarLista
inicio
entero lista[TAM] = { 6,10,4,1,3,9,11,7,-3,8}
entero i, aux, j
/Recorrer el arreglo
Escriba("Inserción en cada paso")
para(i = 1, i < TAM, i++)
aux = lista[i];
j = i - 1;
/Comparar valor selecionado con los
valores anteriores
mientras(j >= 0 y lista[j] > aux)
/Proceso de inserción
lista[j + 1] = lista[j]
j = j - 1
fin-mientras
lista[j + 1] = aux
mostrarLista(lista)
fin-para
fin
Ordenamiento por selección
Por último, el ordenamiento por selección: Al igual que el algoritmo de inserción es muy trivial, puesto que recorre el vector o la lista, buscando el elemento más pequeño y colocándolo en la posición 0 del vector, y así sucesivamente n-1 veces, tanto de grande como sea el vector. Al igual que los algoritmos anteriores, requiere O(n²) .
Ejemplo:
Escribir un algoritmo de ordenamiento por selección para un vector lista de n elementos.
Algoritmo ordenación por selección
OrdenarSeleccion
const TAM=20
inicio
entero lista[TAM], i, j;
escriba("Llenar arreglo con números aleatorios del 0 al 50)
para(i = 0; i < TAM; i++)
lista[i] = aleatorio % 50
ordenaSelecc(lista, 0, TAM)
para(i = 0; i < TAM; i++)
escriba(“Lista ordenada: “ lista[i])
fin
Ordenamiento rápido
El método de ordenamiento rápido también llamado Quicksort es el método más eficiente y y rápido de los métodos de ordenación conocidos. Se le conoce con el nombre del método rápido y de ordenamiento por partición.
Su principio consiste en utilizar el método de intercambio directo ordenando los elementos del arreglo a gran velocidad.
El método de ordenamiento rápido es un algoritmo basado en la técnica (top-down) de divide y vencerás, que permite, ordenar n elementos en un tiempo proporcional a n log n.
Ejemplo:
Escribir un algoritmo de ordenamiento rápido para un vector lista de n elementos.
Algoritmo ordenamiento rápido
entero particionar(entero [], entero, entero)
intercambiar(entero*, entero*)
ordenaRapido(entero [], entero, entero)
muestralista(entero [], entero)
inicio
entero lista[TAM]
aleatorizar
para(entero i = 0; i < TAM; i++)
lista[i] = aleatorio() % 100
entero n = tamaño(lista) / tamaño(lista[0])
escriba("Lista de datos inicial")
muestralista(lista, n)
ordenaRapido(lista, 0, n - 1)
escriba("Lista de datos ordenada")
muestralista(lista, n)
retorna 0;
// Dividir el arreglo utilizando un elemento pivot
entero particionar(entero lista[], entero menor, entero mayor)
entero pivot = lista[mayor]
entero i = (menor - 1)
para(entero j = menor; j <= mayor - 1; j++)
si(lista[j] <= pivot)
entonces
i++
intercambiar(&lista[i], &lista[j])
fin-si
intercambiar(&lista[i + 1], &lista[mayor])
retorna (i + 1)
fin-paticionar
intercambiar(entero* a, entero* b)
entero aux = *a
*a = *b;
*b = aux;
fin-intercambiar
ordenaRapido(entero lista[], entero menor, entero mayor)
si(menor < mayor)
entonces
entero pivot = particionar(lista, menor, mayor)
ordenaRapido(lista, menor, pivot - 1)
ordenaRapido(lista, pivot + 1, mayor)
fin-si
fin-ordenaRapido
muestraLista(entero lista[], entero size)
entero i
para(i = 0; i < size; i++)
escriba(lista[i])
fin-muestraLista
