Burb Uja

NOMBRE: Kirk Freire López
CURSO: 3 -A
ASIGNATURA: Estructura de Datos
METODOS DE ORDENACION EN C++
Tipos de Ordenamiento:
Ordenamiento interno.
Se lleva a cabo completamente en memoria principal. Todos los objetos que se ordenan
caben en la memoria principal de la computadora
Ordenamiento externo.
No cabe toda la información en memoria principal y es necesario ocupar memoria
secundaria. El ordenamiento ocurre transfiriendo bloques de información a memoria
principal en donde se ordena el bloque y este es regresado, ya ordenado, a memoria
secundaria
METODOS:
BURBUJA
Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes

de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se
intercambian.
Ejemplo:
1. for (i=1; i<TAM; i++)

2. for j=0 ; j<TAM - 1; j++)
3. if (lista[j] > lista[j+1])
4. temp = lista[j];
5. lista[j] = lista[j+1];
6. lista[j+1] = temp;
POR SELECCIÓN
El método de ordenamiento por selección consiste en encontrar el menor de todos los

elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el
segundo más pequeño, y así sucesivamente hasta ordenar todo el arreglo.
Ejemplo:
#include<iostream>
using namespace std;
#include"leearreglo.h"
#define largo 50
void seleccionsort (int A[], int n)
{
int min,i,j,aux;
for (i=0; i<n-1; i++)
{
min=i;
for(j=i+1; j<n; j++)
if(A[min] > A[j])
min=j;
aux=A[min];
A[min]=A[i];
A[i]=aux ;
}
}void main ()
{
int A[largo],n;
do{
cout<<"Cantidad de numeros a ingresar: ";cin>>n;
if(n<=0||n>largo)
cout<<"Debe ingresar un valor > a 0 y < a "<<largo<<endl;
}while(n<=0||n>largo);
leeCadena(n,A);
seleccionsort(A,n);
muestraCadena(n,A);
}
INSERCION
Este método toma cada elemento del arreglo para ser ordenado y lo compara con los que
se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el
elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre
hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que
se está comparando es menor que el elemento a ordenar, se detiene el proceso de
comparación pues se encontró que el elemento ya está ordenado y se coloca en su
posición (que es la siguiente a la del último número con el que se comparó).
Este también es un algoritmo lento, pero puede ser de utilidad para listas que están
ordenadas o semiordenadas, porque en ese caso realiza muy pocos desplazamientos.
Ejemplo:
#include<iostream>
#define largo 50
void insercionDirecta(int A[],int n)
{
int i,j,v;
for (i = 1; i < n; i++)
{
v = A[i];
j=i -1;
while (j >= 0 && A[j] > v)
{
A[j + 1] = A[j];
j--;
}A [j + 1 ] = v ;
}
}void main ()
{
int A[largo],n;
do{
if(n<=0||n>largo)
leeCadena(n,A);
insercionDirecta(A,n);
muestraCadena(n,A);
ORDENAMIENTO RAPIDO
Es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio,

ordenar n elementos en un tiempo proporcional a n log n.
Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada

desordenados completamente, que para elementos semiordenados. Esta situación es
precisamente la opuesta al ordenamiento de burbuja.
Ejemplo:
void quicksort(int a[], int l, int r)

{
int i,j,v;
if(r > l)
{
v = a[r];
i = l-1;
j = r;
for(;;)
{
while(a[++i] < v && i < r);
while(a[--j] > v && j > l);
if( i >= j)
break;
swap(a,i,j);
}
swap(a,i,r);
quicksort(a,l,i-1);
quicksort(a,i+1,r);
}
}
MÉTODO DE ORDENAMIENTO POR INSERCIÓN BINARIA
El método de ordenación por 'inserción binaria'' es una mejora del método de inserción
directa. Para lograr esta mejora se recurre a una búsqueda binaria en lugar de una
búsqueda secuencial para insertar un elemento en la parte izquierda del arreglo, que ya
se encuentra ordenado. El resto del procedimiento es similar al de inserción directa, es
decir, se repite este mismo procedimiento desde el segundo término hasta elúltimo
elemento.
Ejemplo:
#include<iostream>
#define largo 50
void insercionBinaria(int A[],int n)
{
int i,j,aux,izq,der,m;
for(i=1;i<n;i++)
{
aux = A[i];
izq=0;
der=i-1;
while(izq<=der)
{
m=((izq+der)/2);
if (aux<A[m])
der=m-1;
else
izq=m+1;
}
j=i-1;
while(j>=izq)
{
A[j+1]=A[j];
j=j-1;
}A[izq]=aux;
}
}void main ()
{
int A[largo],n;
do{
if(n<=0||n>largo)
leeCadena(n,A);
insercionBinaria(A,n);
muestraCadena(n,A);
ORDENAMIENTO POR EL MÉTODO DE SHELL
El método Shell es una versión mejorada del método de inserción directa. Este método
también se conoce con el nombre de inserción con incrementos decrecientes. En el
método de ordenación por inserción directa cada elemento se compara para su ubicación
correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del
mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se
encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de
su ubicación.
Ejemplo:
#include<iostream>
#define largo 50
void ordenShell(int A[],int n)
{int i, j, inc, temp;
for(inc = 1 ; inc<n;inc=inc*3+1);
while (inc > 0)
{
for (i=inc; i < n; i++)
{
j = i;
temp = A[i];
while ((j >= inc) && (A[j-inc] > temp))
{
A[j] = A[j - inc];

j = j - inc;
}A[j] = temp;
}inc/= 2;
}
}void main ()
{
int A[largo],n;
do{
if(n<=0||n>largo)
leeCadena(n,A);
ordenShell(A,n);
muestraCadena(n,A);
ORDENAMIENTO HEAP SORT
Este método consiste en almacenar todos los elementos del vector a ordenar en un
montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima)
en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en
una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento
(o el mayor, según se haya definido el montículo) de todos los almacenados enél.
Ejemplo:
#include <iostream>
#define max 100
int main()
{
int A[max],j,item,temp,i,k,n;
cout<<"Ingresa la cantidad de elementos del arreglo: ";
cin>>n;
for(i=1;i<=n;i++)
cin >> A[i];
for(k=n;k>0;k--)
{
for(i=1;i<=k;i++)
{
item=A[i];
j=i/2;
while(j>0 && A[j]<item)
{
A[i]=A[j];
i=j;
j=j/2;
}A[i]=item;
}temp=A[1];
A[1]=A[k];
A[k]=temp;
}cout<<"El orden es:"<<endl;
for(i=1;i<=n;i++)
cout<<A[i] << endl;
return 0;

Burb Uja

Cargado por

Copyright:

Formatos disponibles

Burb Uja

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Burb Uja

Cargado por

Copyright:

Formatos disponibles

NOMBRE: Kirk Freire López

Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes

1. for (i=1; i<TAM; i++)

El método de ordenamiento por selección consiste en encontrar el menor de todos los

if(A[min] > A[j])

Es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio,

Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada

void quicksort(int a[], int l, int r)

MÉTODO DE ORDENAMIENTO POR INSERCIÓN BINARIA

ORDENAMIENTO POR EL MÉTODO DE SHELL

A[j] = A[j - inc];

ORDENAMIENTO HEAP SORT

También podría gustarte