Quispe Fernandez, JAMES
semana 12:
​
METODOS DE ORDENAMIENTO c++
En general los métodos de ordenamiento no son utilizados con frecuencia, en algunos casos sólo una vez. Hay métodos muy simples de implementar que son útiles en los casos en dónde el número de elementos a ordenar no es muy grande (ej, menos de 500 elementos). Por otro lado hay métodos sofisticados, más difíciles de implementar pero que son más eficientes en cuestión de tiempo de ejecución.
Los métodos sencillos por lo general requieren de aproximadamente n x n pasos para ordenar n elementos.
Los métodos simples son: insertion sort (o por inserción directa) selection sort, bubble sort, y shellsort, en dónde el último es una extensón al insertion sort, siendo más rápido. Los métodos más complejos son el quick-sort, el heap sort, radix y address-calculation sort. El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente.
Se ha dicho que el ordenamiento puede efectuarse moviendo los registros con las claves. El mover un registo completo implica un costo, el cual se incrementa conforme sea mayor el tamaño del registro. Es por ello que es deseable evitar al máximo el movimiento de los registros. Una alternativa es el crear una tabla de referencias a los registros y mover las referencias y no los datos. A continuación se mostrarán los métodos de ordenamiento empezando por el más sencillo y avanzando hacia los mas sofisticados
La eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el número de elementos que tiene el arreglo a ordenar y se dice que un algoritmo realiza O(n2) comparaciones cuando compara n veces los n elementos.
METODO BURBUJA
​
​
Para ordenar arrays tenemos a nuestra disposición diferentes tipos de algoritmos para hacerlo. Hay lo que se llaman formas naturales de ordenación y las que no lo son. El método de la burbuja es un método de ordenación no natural para ordenar arrays. Consiste en ir recorriendo todo el array a ordenar, comparando dos elementos al mismo tiempo e intercambiándolos si no están en el lugar apropiado. Al finalizar el recorrido por todos los elementos, se determina si hubo algún cambio, y en caso afirmativo, se repite el algoritmo hasta que no haya cambio alguno.
De todas formas si quieres profundizar en el tema de algoritmos de ordenación, puedes visitar los apuntes (de mi universidad) que tengo subidos sobre ello.
El nombre que se le atribuye viene porque al hacer el intercambio, los elementos más pequeños “burbujean” de forma progresiva hasta el inicio del array, mientras que los más grandes se “hunden”. Es el algoritmo de ordenación por comparación más sencillo de implementar.
En cuanto al rendimiento, el algoritmo no destaca por su rapidez. Es de los más pobres en rendimiento y sobre todo no es recomendable usarlo en arrays largos. Sin embargo, está bastante bien si estás empezando ya que se caracteriza por su sencillez.
En concreto el ejemplo que voy a mostrar a continuación es el código para ordenar un array de mayor a menor, sin embargo para ordenador de menor a mayor solo habría que cambiar uno de los signos que comento en el código
#include<iostream>
#include<math.h>
using namespace std ;
int main(){
int n,aux;
cout<<"IIIEE-2\n\n\n ";
cout<<"ingrese el numero de elementos :";
cin>>n;
int V[n];
for(int i=0;i<n;i++){
cout<<"\n Numero "<<i+1<<" = ";
cin>>V[i];
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(V[j]<V[i]){
aux=V[i];
V[i]=V[j];
V[j]=aux;
}
}
}
cout<<"EL orden correpto es "<<endl;
for(int i=0;i<n;i++){
cout<<V[i]<<endl;
}
}
Método por selección
Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación de intercambiar los elementos sería más costosa en este caso. Su funcionamiento se puede definir de forma general como:
-
Buscar el mínimo elemento entre una posición i y el final de la lista
-
Intercambiar el mínimo con el elemento de la posición i
Así, se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:
para i=1 hasta n-1;
minimo = i; para j=i+1 hasta n si lista[j] < lista[minimo] entonces minimo = j fin si fin para intercambiar(lista[i], lista[minimo])
fin para
Ejemplo
El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e']. Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'. Esta se intercambia con el dato que está en la segunda posición, la 's', quedando el arreglo así después de dos recorridos: a = ['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e']. El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'. El arreglo ahora se ve de la siguiente manera: a = ['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r']. De esta manera se va buscando el elemento que debe ir en la siguiente posición hasta ordenar todo el arreglo.
#include<iostream>
#include <math.h>
using namespace std;
void Seleccion(int [] , int );
void Imprimir(int [] , int );
int main()
{
int n;
cout<<"IIIEE-2\n\n\n ";
cout<<"ingrese el numero de elementos "<<endl;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cout<<"Ingrese valores "<<(i+1)<<" del arreglo"<<endl;
cin>>a[i];
}
Seleccion(a , n);
Imprimir(a , n);
}
void Seleccion(int a[] , int n)
{
//Variables a utilizar
int k , menor , i , j;
for(i=0;i<n;i++)
{
menor=a[i];
k=i;
for(j=i+1;j<n;j++)
{
if(a[j]<menor)
{
menor = a[j];
k=j;
}
}
a[k]=a[i];
a[i]=menor;
}
}
void Imprimir(int a[] , int n)
{
cout<<"EL orden correpto es "<<endl;
for(int i=0;i<n;i++)
cout<<"[ "<<a[i]<<" ]";
}
Método por inserción
Este algoritmo también es bastante sencillo. ¿Has jugado cartas?. ¿Cómo las vas ordenando cuando las recibes? Yo lo hago de esta manera: tomo la primera y la coloco en mi mano. Luego tomo la segunda y la comparo con la que tengo: si es mayor, la pongo a la derecha, y si es menor a la izquierda (también me fijo en el color, pero omitiré esa parte para concentrarme en la idea principal). Después tomo la tercera y la comparo con las que tengo en la mano, desplazándola hasta que quede en su posición final. Continúo haciendo esto, insertando cada carta en la posición que le corresponde, hasta que las tengo todas en orden. ¿Lo haces así tu también? Bueno, pues si es así entonces comprenderás fácilmente este algoritmo, porque es el mismo concepto.
Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderá un elemento. Lo que hacemos es guardar una copia del elemento actual (que sería como la carta que tomamos) y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó.
#include<iostream>
#include<math.h>
using namespace std;
void Imprimir(int a[] , int n)
{
cout<<"IIIEE-2\n\n\n ";
cout<<"Numeros Ordenados de Menor a Mayor"<<endl;
for(int i=0;i<n;i++)
cout<<"[ "<<a[i]<<" ]";
}
void Insercion(int a[] , int n)
{
int i,k,aux;
for(i=0;i<=n-1;i++)
{
aux=a[i];
k=i-1;
while((k>=0) && (aux<a[k]))
{
a[k+1]=a[k];
k=k-1;
}
a[k+1]=aux;
}
}
int main()
{
int n;
cout<<"ingrese el numero de elementos"<<endl;
cin>>n;
int num[n];
for(int i=0;i<n;i++)
{
cout<<"Ingrese el numero "<<(i+1)<<endl;
cin>>num[i];
}
Insercion(num,n);
Imprimir(num,n);
return 0;
}
Método Shell
Adaptación y mejora del método por inserción directa. Se utiliza un array con gran número de elemento en el cual compara a cada elemento con el que está a cierto número de lugares a su izquierda. Este salto es constante a razón de N/2 (siendo N el número de elementos). Se realiza el bucle hasta que no se intercanvien mas elementos de sitio. Este salto se reduce a la mitad y se vuelven a dar pasadas hasta que no se intercambie nadie con nadie. El algoritmo finaliza en el momento en que el salto es 1.
Ejemplo:
Tenemos el siguente array {55,36,19,24,25,50}
Salto=3:
Primera iteración:
{24,36,19,55,25,50} <-- Cambia el 55 y el 24.
{24,25,19,55,36,50} <-- Cambia el 36 y el 25.
Salto=1:
Primera iteración:
{24,19,25,55,36,50} <-- Cambia el 25 y el 19.
{24,19,25,36,55,50} <-- Cambia el 55 y el 36.
{24,19,25,36,50,55} <-- Cambia el 50 y el 55.
Segunda iteración:
{19,24,25,36,50,55} <-- Cambia el 19 y el 24.
#include<iostream>
#include<math.h>
using namespace std;
void Imprimir(int [] , int n);
void Shell(int [] , int n);
int main()
{
int total;
cout<<"IIIEE-2\n\n\n ";
cout<<"ingrese el numero de elementos"<<endl;
cin>>total;
int num[total];
for(int i=0;i<total;i++)
{
cout<<"Ingrese el numero para la posicion [ "<<(i+1)<<" ] del arreglo"<<endl;
cin>>num[i];
}
Shell(num,total);
}
void Shell(int a[] , int n)
{
int ints,i,aux;
bool band;
ints=n;
while(ints>1)
{
ints=(ints/2);
band=true;
while(band==true)
{
band=false;
i=0;
while((i+ints)<=n)
{
if(a[i]>a[i+ints])
{
aux=a[i];
a[i]=a[i+ints];
a[i+ints]=aux;
band=true;
}
i++;
Imprimir(a,n);
}
}
}
}
void Imprimir(int a[] , int n)
{
cout<<"Numeros del arreglo ordenandos de Menor a Mayor"<<endl;
for(int i=0;i<n;i++)
cout<<"[ "<<a[i]<<" ]";
}
Quicksort en C++
​
Quicksort es un algoritmo de ordenación considerado entre los más rápidos y eficientes. Fue diseñado en los años 60s por C. A. R. Hoare un científico en computación.
El algoritmo usa la técnica divide y vencerás que básicamente se basa en dividir un problema en subproblemas y luego juntar las respuestas de estos subproblemas para obtener la solución al problema central.
Me pareció una buena manera de practicar programación y C++ y hacer una explicación que permite entender este algoritmo , bueno al menos eso intenté. Hace año y medio también publiqué unos ejemplos de ordenación en Haskell.
Voy a explicar el funcionamiento del quicksort brevemente y después veremos su implementación en C++.
Se tiene una array de n elementos, tomamos un valor del array como pibote(usualmente el primero), separamos los elementos menor a este pibote a la izquierda y los mayores a la derecha, es decir, dividimos el array en 2 subarrays.
Con estos subarrays se repite el mismo proceso de forma recursiva hasta que estos tengan más de 1 elemento. Por lo tanto la función quicksort quedaría de la siguiente manera:
#include<iostream>
#define MAX 1000
using namespace std;
void QuickSort(int [] , int );
void Imprimir(int [] , int);
int main()
{
int n ;
cout<<"IIIEE-2\n\n\n ";
cout<<"ingrese el numero de elementos "<<endl;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cout<<"Ingresa el elemento numero "<<i+1<<" : "<<endl;
cin>>a[i];
}
QuickSort(a,n);
Imprimir(a,n);
}
void QuickSort(int a[] , int n)
{
int tope, ini, fin , pos;
int may[MAX],menor[MAX];
tope=0;
menor[tope]=0;
may[tope]=n-1;
while(tope>=0)
{
ini = menor[tope];
fin = may[tope];
tope--;
int izq,der,aux;
bool band;
izq=ini;
der=fin;
pos=ini;
band=true;
while(band==true)
{
while((a[pos]<a[der]) && ( pos!=der ))
der--;
if(pos==der)
band=false;
else
{
aux=a[pos];
a[pos]=a[der];
a[der]=aux;
pos=der;
}
while((a[pos]>a[izq]) && ( pos!=izq ))
izq++;
if(pos==izq)
band=false;
else
{
aux=a[pos];
a[pos]=a[izq];
a[izq]=aux;
pos=izq;
}
}
if(ini<=(pos-1))
{
tope++;
menor[tope]=ini;
may[tope]=pos-1;
}
if(fin>=(pos+1))
{
tope++;
menor[tope]=pos+1;
may[tope]=fin;
}
}
}
void Imprimir(int a[] , int n){
cout<<"Elementos Ordenados"<<endl;
for(int i =0 ;i<n;i++){
cout<<"["<<a[i]<<"]";
}
}
