4 METODOS DE ORDENACION DE VECTORES EN C++
1. ORDENACIÓN POR SELECCIÓN
DESCRIPCIÓN (PASOS PARA EL ALGORITMO)
•Buscas el elemento más pequeño de la lista.
•Lo intercambias con el elemento ubicado en la primera posición de la lista.
•Buscas el segundo elemento más pequeño de la lista.
•Lo intercambias con el elemento que ocupa la segunda posición en la lista.
•Repites este proceso hasta que hayas ordenado toda la lista.
ANÁLISIS DEL ALGORITMO
•Requerimientos de Memoria:
Al igual que el ordenamiento burbuja, este algoritmo sólo necesita una variable adicional para realizar los intercambios.
•Tiempo de Ejecución:
El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados.
UN EJEMPLO:
Consideremos un vector A con 5
valores enteros: A=[ 5, 2, 4, 8, 3]:
Pasada 0. Seleccionar 2
Intercambiar 2 y A[0]
A[0] A[1] A[2] A[3] A[4]
5
|
2
|
4
|
8
|
3
|
pasada 0
Pasada 1. Seleccionar 36
Intercambiar 3 y A[1]
2
|
5
|
4
|
8
|
3
|
pasada 1
Pasada 2. Seleccionar 4
Intercambiar 4 y A[2]
2
|
3
|
4
|
8
|
5
|
pasada 2
Pasada 3. Seleccionar 51
Intercambiar 5 y A[3]
2
|
3
|
4
|
8
|
5
|
pasada 3
Lista ordenada
2
|
3
|
4
|
5
|
8
|
Ventajas:
•Fácil implementación.
•No requiere memoria adicional.
•Rendimiento constante: poca diferencia entre el peor y el mejor caso.
Desventajas:
•Lento.
•Realiza numerosas comparaciones.
CODIFICACION EN C++
#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 ;
}
}
int 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);
}
2. ORDENACION POR INSERCIÓN DIRECTA
DESCRIPCIÓN (PASOS PARA EL ALGORITMO)
El algoritmo de ordenación por el método de inserción directa es un algoritmo relativamente sencillo y se comporta razonablemente bien en gran cantidad de situaciones. Completa la tripleta de los algoritmos de ordenación más básicos y de orden de complejidad cuadrático, junto con Selection Sort y BubbleSort (burbuja). Se basa en intentar construir una lista ordenada en el interior del vector a ordenar. De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otros dos en la mayor parte de las situaciones. Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un vector o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no.
•En cada iteración del ciclo externo los elementos 0 a i forman una lista ordenada.
ANÁLISIS DEL ALGORITMO
•Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por lo tanto es estable.
•Requerimientos de Memoria: Una variable adicional para realizar los intercambios.
•Tiempo de Ejecución: Para una lista de n elementos el ciclo externo se ejecuta n-1veces. El ciclo interno se ejecuta como máximo una vez en la primera iteración, 2 veces en la segunda, 3 veces en la tercera, etc.
UN EJEMPLO
Así el proceso en el caso de la lista de
enteros A = [6, 3, 5, 9, 4]
Procesar 20
6
|
• Comienzo con 6
3
|
6
|
Procesamos 3 • Se inserta 3 en la posición 0
• 6 se mueve a posición 1
3
|
5
|
6
|
Procesamos 5 • Se inserta 5 en la posición 1
• Se mueve 6 a posición 2
Procesamos 9
3
|
5
|
6
|
9
|
• El elemento 9 está bien ordenado
Procesamos 4
3
|
4
|
5
|
6
|
9
|
• Se inserta 4 en posición 1
• Se desplaza a la derecha la sublista derecha
Ventajas:
•Fácil implementación.
•Requerimientos mínimos de memoria.
Desventajas:
•Lento.
•Realiza numerosas comparaciones. Este también es un algoritmo lento, pero puede ser de utilidad para listas que están ordenadas o semi-ordenadas, porque en ese caso realiza muy pocos desplazamientos.
CODIFICACION EN C++
#include<iostream>
#include"leearreglo.h"
using namespace std;
#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;
}
}
int 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);
insercionDirecta(A,n);
muestraCadena(n,A);
}
3. ORDENACIÓN SHELL
DESCRIPCION (PASOS PARA EL ALGORITMO)
Los pasos a seguir por el algoritmo para una lista de n elementos son:
1. Dividir la lista original en n/2 grupos de dos, considerando un incremento o salto entre los
elementos de n/2.
2. Clarificar cada grupo por separado, comparando las parejas de elementos, y si no están
ordenados, se intercambian.
3. Se divide ahora la lista en la mitad de grupos (n/4), con un incremento o salto entre los
elementos también mitad (n/4), y nuevamente se clasifica cada grupo por separado.
4. Así sucesivamente, se sigue dividiendo la lista en la mitad de grupos que en el recorrido
anterior con un incremento o salto decreciente en la mitad que el salto anterior, y luego
clasificando cada grupo por separado.
5. El algoritmo termina cuando se consigue que el tamaño del salto es 1.
ANALISIS DEL ALGORITMO
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. Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes, así , los elementos quedarán ordenados en el arreglo más rápidamente. El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones: 1. El ordenamiento por inserción es eficiente si la entrada está “casi ordenada".2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez. El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga “pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.
UN EJEMPLO
Obtener las secuencias parciales del vector al aplicar el método Shell para ordenar en orden
creciente la lista:
6 1 5 2 3 4 0
El número de elementos que tiene la lista es 6, por lo que el salto inicial es 6/2 = 3. La siguiente
tabla muestra el número de recorridos realizados en la lista con los saltos correspondiente.
Recorrido Salto Intercambios Lista
1 3 (6,2),(5,4),(6,0) 2 1 4 0 3 5 6
2 3 (2, 0) 0 1 4 2 3 5 6
3 3 ninguno 0 1 4 2 3 5 6
salto 3/2 = 1
4 1 (4,2),(4,3) 0 1 2 3 4 5 6
5 1 ninguno 0 1 2 3 4 5 6
CODIFICACION EN C++
using namespace std;
#include "leearreglo.h"
#include<iostream>
#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 ;
}
}
int 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);
}
4. ORDENACIÓN RÁPIDA (QUICKSORT)
El ordenamiento por partición (Quick Sort) se puede definir en una forma más conveniente como un procedimiento recursivo. 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. Este tipo de algoritmos se basa en la técnica "divide y vencerás", osea es más rápido y fácil ordenar dos arreglos o listas de datos pequeños, que un arreglo o lista grande. Normalmente al inicio de la ordenación se escoge un elemento aproximadamente en la mitad del arreglo, así al empezar a ordenar, se debe llegar a que el arreglo este ordenado respecto al punto de división o la mitad del arreglo. Se podrá garantizar que los elementos a la izquierda de la mitad son los menores y los elementos a la derecha son los mayores. Los siguientes pasos son llamados recursivos con el propósito de efectuar la ordenación por partición al arreglo izquierdo y al arreglo derecho, que se obtienen de la primera fase. El tamaño de esos arreglos en promedio se reduce a la mitad. Así se continúa hasta que el tamaño de los arreglos a ordenar es 1, es decir, todos los elementos ya están ordenados. En promedio para todos los elementos de entrada de tamaño n, el método hace O(n logn) comparaciones, el cual es relativamente eficiente.
UN EJEMPLO
Se ordena una lista de números enteros aplicando el algoritmo quicksort, como pivote se elige el
primer elemento de la lista.
1. Lista original
5
|
2
|
1
|
7
|
9
|
3
|
8
|
7
|
5
|
pivote elegido
2
|
1
|
3
|
sublista izquierda1 (elementos menores que 5)
9
|
8
|
7
|
sublista derecha1 (elementos mayores o iguales a 5)
2. El algoritmo se aplica a la sublista izquierda
Sublista Izda1 2 1 3
pivote sublista Izda 1
sublista Dcha 3
Sublista Izda1
Izda pivote Dcha
1
|
2
|
3
|
3. El algoritmo se aplica a la sublista derecha
Sublista Dcha1 9 8 7
Pivote sublista Izda 7 8
sublista Dcha
Sublista Dcha1 Izda pivote Dcha
7
|
8
|
9
|
4. Lista ordenada final
Sublista izquierda pivote Sublista derecha
1 2 3 5 7 8 9
CODIFICACION EN C++
#include <iostream>
#define largo 100
#include"leearreglo.h"
using namespace std;
void quicksort(int A[],int izq, int der )
{
int i, j, x , aux;
i = izq;
j = der;
x = A[ (izq + der) /2 ];
do{
while( (A[i] < x) && (j <= der) )
{
i++;
}
while( (x < A[j]) && (j > izq) )
{
j--;
}
if( i <= j )
{
aux = A[i]; A[i] = A[j]; A[j] = aux;
i++; j--;
}
}while( i <= j );
if( izq < j )
quicksort( A, izq, j );
if( i < der )
quicksort( A, i, der );
}
int 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);
quicksort(A,0,n-1);
muestraCadena(n,A);
}
gracias me ayudo mucho
ResponderEliminarMuchas Gracias por el aporte.
ResponderEliminar