Métodos de ordenamiento
La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo uno de los más sencillos de implementar.
Ordenamiento por método de Selección
Algoritmo de ordenamiento por Selección (Selection Sort en inglés): Consiste en encontrar el menor de todos los elementos del arreglo o vector e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenarlo todo. Su implementación requiere O(n2) comparaciones e intercambios para ordenar una secuencia de elementos.
Ordenamiento por método de Shell
Algoritmo de ordenamiento Shell: El método se denomina así en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso, aunque un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n).
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones: El ordenamiento por inserción es eficiente si la entrada está "casi ordenada". 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.
C++
#include<iostream>
#include<math.h>
using namespace std;
int i,A[10],r,axu,n,menor,j,k,a,inc,izquierda,derecha;
float leer(),ordenar(),ver(),Seleccion(),Burbuja(),ordenar1(),Insercion(),ordenar2(),Shell(),QuickSort(),ordenar3(int A[],int n),ordenar4(int A[],int izquierda,int derecha);
int main(){
int opcion;
do{
cout<<"**************Prueba 10**************\n";
cout<<"1)BurbBuja\n";
cout<<"2)SelecCion\n";
cout<<"3)Insercion\n";
cout<<"4)Shell\n";
cout<<"5)Quick Sort\n";
cout<<endl;
cout<<"Eliga Opcion\n";
cin>>opcion;
if(opcion>0,opcion<6){
switch (opcion){
case 1:{
Burbuja();
break;
}
case 2:{
Seleccion();
break;
}
case 3:{
Insercion();
break;
}
case 4:{
Shell();
break;
}
case 5:{
QuickSort();
break;
}
}
}else
cout<<"Opcion no existente\n";
cout<<endl;
cout<<endl;
}while (opcion!=0);
system("pause");
return(0);
}
float Burbuja(){
cout<<"*******Metodo Burbuja*******\n";
int opcion1;
cout<<"1)Leer\n";
cout<<"1)Oredenar\n";
cout<<"2)Ver\n";
cout<<endl;
cin>>opcion1;
if(opcion1>0,opcion1<4){
switch (opcion1){
case 1:{
leer();
break;
}
case 2:{
ordenar();
break;
}
case 3:{
ver();
break;
}
}
}
}
float leer(){
cout<<endl;
cout<<"*******Leer Vectores*******\n";
cout<<endl;
cout<<"Total= ";cin>>n;cout<<endl;
i=1;
cout<<"Vector[]\n";
while(i<=n){
cout<<"Vector["<<i<<"]= ";
cin>>A[i];
i=i+1;
}cout<<endl;
}
float ordenar(){
cout<<endl;
cout<<"*******Ordenamiento*******\n";
cout<<endl;
for(r=1;r<=n-1;r++){
for(i=1;i<=n;i++){
if(A[i]>A[i+1]){
axu=A[i];
A[i]=A[i+1];
A[i+1]=axu;
}
}
}
}
float ver(){
cout<<endl;
cout<<"*******Mirar Vectores*******\n";
cout<<endl;
i=1;
cout<<"Vector[]\n";
while(i<=n){
cout<<"Vector["<<i<<"]= ";
cout<<A[i];
i=i+1;
cout<<endl;
}
cout<<"#vueltas: "<<r<<endl;
cout<<endl;
}
float Seleccion(){
cout<<"*******Metodo Seleccion*******\n";
int opcion2;
cout<<"1)Oredenar\n";
cout<<"2)Ver\n";
cout<<endl;
cin>>opcion2;
if(opcion2>0,opcion2<3){
switch (opcion2){
case 1:{
ordenar1();
break;
}
case 2:{
ver();
break;
}
}
}
}
float ordenar1(){
for(i=1;i<=n;i++){
menor=A[i];
k=i;
for(j=1;j<=n;j++){
if(A[j]<menor){
menor=A[j];
k=j;
}
}A[k]=A[i];
A[i]=menor;
}
}
float Insercion(){
cout<<"*******Metodo Insercion*******\n";
int opcion3;
cout<<"1)Oredenar\n";
cout<<"2)Ver\n";
cout<<endl;
cin>>opcion3;
if(opcion3>0,opcion3<3){
switch (opcion3){
case 1:{
ordenar2();
break;
}
case 2:{
ver();
break;
}
}
}
}
float ordenar2(){
for (i=1; i<n; i++){
a=A[i];
j=i - 1;
while ( (A[j] >a) && (j >= 0) ){
A[j+1] = A[j];
j--;
A[j+1] = a;
}
}
}
float Shell(){
cout<<"*******Metodo Shell*******\n";
int opcion4;
cout<<"1)Oredenar\n";
cout<<"2)Ver\n";
cout<<endl;
cin>>opcion4;
if(opcion4>0,opcion4<3){
switch (opcion4){
case 1:{
ordenar3(A,n);
break;
}
case 2:{
ver();
break;
}
}
}
}
float ordenar3(int A[],int n){
int i, j, inc,axu;
for(inc=1 ; inc>0;){
for (i=inc;i=inc;A[j-inc]>axu){
A[j] = A[j-inc];
j = j-inc;
}A[j] = axu;
}inc/= 2;
}
float QuickSort(){
cout<<"*******Metodo Quick Sort*******\n";
int opcion5;
cout<<"1)Oredenar\n";
cout<<"2)Ver\n";
cout<<endl;
cin>>opcion5;
if(opcion5>0,opcion5<3){
switch (opcion5){
case 1:{
ordenar4(A,izquierda,derecha);
break;
}
case 2:{
ver();
break;
}
}
}
}
float ordenar4(int A[],int izquierda,int derecha){
int i,j,x,axu;
i=izquierda;
j=derecha;
x=A[(izquierda+derecha)/2];
do{
while((A[i]<x) && (j<=derecha)){
i++;
}
while((x<A[j]) && (j>izquierda)){
j--;
}
if( i<= j){
axu=A[i];
A[i]=A[j];
A[j]=axu;
i++;
j--;
}
}while( i <= j );
if( izquierda < j ){
ordenar4(A,izquierda,j);
}
if( i < derecha ){
ordenar4(A,i,derecha);
}
// FIN PROCESO
}