Metodos de ordenación y búsqueda
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <time.h>
using namespace std;
// Constantes
#define MAX 10
// Variables
int A[ MAX ]; // Arreglo de enteros
int N = MAX; // Total de elementos
// *** Sección de Prototipos
// Funciones generales
void MenuPrincipal();
void IngresarUsuario();
void IngresarAleatorio();
void MostrarArreglo();
void MostrarTiempo( time_t Inicio, time_t Final );
// Métodos de Ordenación
void BubbleSort( int A[], int N );
void ShakerSort( int A[], int N );
void InsercionDirecta( int A[], int N );
void InsercionBinaria( int A[], int N );
void SeleccionDirecta( int A[], int N );
void Shell( int A[], int N );
void QuickSort( int A[], int Izq, int Der );
void HeapSort( int A[], int N );
void Merge( int A[], int Izq, int Der);
// Métodos de Ordenación
int BusqSec( int A[], int N, int X );
int BusqBin( int A[], int N, int X );
int Hash();
// Implementación de procedimientos y funciones de usuario generales
void IngresarUsuario()
{
for ( int i=0; i < MAX; i++)
{
cout << "Introduce elemento " << i + 1 << ": ";
cin >> A[i];
};
};
void IngresarAleatorio()
{
srand(time(NULL));
for ( int i=0; i < MAX; i++)
A[i]= rand() % 999;
};
void MostrarArreglo()
{
for (int i=0; i<MAX; i++)
cout << A[i] << " ";
cout << endl;
};
void MostrarTiempo( time_t Inicio, time_t Final )
{
printf( "Comienzo: %u s\n", Inicio );
printf( "Final: %u s\n", Final );
printf( "Número de segundos transcurridos desde el comienzo del programa: %f s\n", difftime( Final, Inicio) );
system("pause");
}
// Implementación de Métodos de Ordenación
// Métodos de Ordenación
void BubbleSort( int A[], int N )
{
// Ciclo externo realiza N-1 iteraciones
for (int i = 0; i < N - 1; i++)
{
// Ciclo interno para comparar e intercambiar si es necesario
for (int j = 0; j < N - i - 1; j++)
{
if (A[j] > A[j + 1])
{
// Intercambio de elementos
int AUX = A[j];
A[j] = A[j + 1];
A[j + 1] = AUX;
}
}
}
MostrarArreglo();
system("pause");
}
void ShakerSort( int A[], int N )
{
int IZQ = 1;
int DER = N - 1;
int K = N - 1;
int AUX;
do {
// Ciclo descendente (de derecha a izquierda)
for (int I = DER; I >= IZQ; I--) {
if (A[I - 1] > A[I]) {
// Intercambiar A[I-1] y A[I]
AUX = A[I - 1];
A[I - 1] = A[I];
A[I] = AUX;
K = I;
}
}
IZQ = K + 1;
// Ciclo ascendente (de izquierda a derecha)
for (int I = IZQ; I <= DER; I++) {
if (A[I - 1] > A[I]) {
// Intercambiar A[I-1] y A[I]
AUX = A[I - 1];
A[I - 1] = A[I];
A[I] = AUX;
K = I;
}
}
DER = K - 1;
} while (DER >= IZQ); // Termina cuando los índices se crucen
MostrarArreglo();
system ("pause");
}
void InsercionDirecta( int A[], int N )
{
int AUX, K;
for (int i = 1; i < N; i++){
AUX = A[i];
K = i - 1;
while (K >= 0 && A[K] > AUX){
A[K + 1] = A[K];
K -= 1;
}
A[K + 1] = AUX;
}
MostrarArreglo();
system ("pause");
}
void InsercionBinaria( int A[], int N )
{
int AUX, IZQ, DER, M, J;
for (int I = 1; I < N; I++) {
AUX = A[I]; // Guardar el valor actual en AUX
IZQ = 0; // El límite izquierdo comienza en 0
DER = I - 1; // El límite derecho es el índice del elemento anterior a I
// Buscar la posición correcta con búsqueda binaria
while (IZQ <= DER) {
M = (IZQ + DER) / 2; // Calcular la mitad
if (AUX < A[M]) {
DER = M - 1; // Ajustar límite derecho
} else {
IZQ = M + 1; // Ajustar límite izquierdo
}
}
// Desplazar los elementos para hacer espacio para AUX
for (J = I - 1; J >= IZQ; J--) {
A[J + 1] = A[J];
}
A[IZQ] = AUX; // Insertar AUX en la posición correcta
}
MostrarArreglo();
cout << endl;
}
void SeleccionDirecta( int A[], int N )
{
int MENOR, K;
// Repetir con I desde 0 hasta N-2 (ajustado para trabajar con índices en 0)
for (int I = 0; I < N - 1; I++) {
MENOR = A[I];
K = I;
// Repetir con J desde I+1 hasta N-1
for (int J = I + 1; J < N; J++) {
if (A[J] < MENOR) {
MENOR = A[J];
K = J;
}
}
// Intercambiar A[I] y A[K] si K cambió
if (K != I) {
int AUX = A[I];
A[I] = A[K];
A[K] = AUX;
}
}
MostrarArreglo();
system ("pause");
}
void Shell( int A[], int N )
{
int INT = N + 1;
do {
INT = INT / 2;
bool BAND = true;
while (BAND) {
BAND = false;
int I = 0;
while ((I + INT) < N) {
if (A[I] > A[I + INT]) {
int AUX = A[I];
A[I] = A[I + INT];
A[I + INT] = AUX;
BAND = true;
}
I++;
}
}
} while (INT > 1);
MostrarArreglo();
system ("pause");
}
void QuickSort( int A[], int INI, int FIN )
{
int IZQ = INI, DER = FIN, POS = INI;
bool BAND = true;
// Paso 2: Mientras (BAND = VERDADERO) Repetir
while (BAND) {
BAND = false;
// 2.1 Mientras ((A[POS] ≤ A[DER]) y (POS ≠ DER)) Repetir
while ((A[POS] <= A[DER]) && (POS != DER)) {
DER--; // Hacer DER <- DER - 1
}
// 2.3 Si (POS ≠ DER) entonces
if (POS != DER) {
int AUX = A[POS]; // Hacer AUX <- A[POS]
A[POS] = A[DER]; // A[POS] <- A[DER]
A[DER] = AUX; // A[DER] <- AUX
POS = DER; // POS <- DER
// 2.3.1 Mientras ((A[POS] ≥ A[IZQ]) y (POS ≠ IZQ)) Repetir
while ((A[POS] >= A[IZQ]) && (POS != IZQ)) {
IZQ++; // Hacer IZQ <- IZQ + 1
}
// 2.3.3 Si (POS ≠ IZQ) entonces
if (POS != IZQ) {
BAND = true;
AUX = A[POS]; // Hacer AUX <- A[POS]
A[POS] = A[IZQ]; // A[POS] <- A[IZQ]
A[IZQ] = AUX; // A[IZQ] <- AUX
POS = IZQ; // POS <- IZQ
}
}
}
// Paso 6: Condiciones para llamadas recursivas
if ((POS - 1) > INI) {
QuickSort(A, INI, POS - 1); // Llamada recursiva
}
if ((POS + 1) < FIN) {
QuickSort(A, POS + 1, FIN); // Llamada recursiva
}
}
void InsertaHeap ( int A[], int N )
{
for (int i = 1; i < N; i++) {
int k = i;
bool BAND = true;
while (k > 0 && BAND) {
BAND = false;
int parent = (k - 1) / 2; // Índice del padre
if (A[k] > A[parent]) { // Comparar con el padre
// Intercambiar A[k] con A[parent]
int AUX = A[parent];
A[parent] = A[k];
A[k] = AUX;
k = parent;
BAND = true;
}
}
}
}
void EliminaHeap ( int A[], int N )
{
int AUX = A[0];
A[0] = A[N - 1];
A[N - 1] = AUX;
N--; // Reducir el tamaño del montón
int k = 0;
bool BAND = true;
while (2 * k + 1 < N && BAND) {
BAND = false;
int hijo_izq = 2 * k + 1;
int hijo_der = 2 * k + 2;
int mayor = hijo_izq;
// Verificar si el hijo derecho es mayor que el izquierdo
if (hijo_der < N && A[hijo_der] > A[hijo_izq]) {
mayor = hijo_der;
}
if (A[mayor] > A[k]) {
// Intercambiar A[k] con A[mayor]
AUX = A[k];
A[k] = A[mayor];
A[mayor] = AUX;
k = mayor;
BAND = true;
}
}
}
void HeapSort( int A[], int N )
{
InsertaHeap ( A, N );
for (int i = N; i > 1; i--) EliminaHeap ( A, i );
MostrarArreglo();
system("pause");
}
void intercalar(int arr[], int inicio, int medio, int fin) {
int n1 = medio - inicio + 1;
int n2 = fin - medio;
int izquierda[n1], derecha[n2];
for (int i = 0; i < n1; i++)
izquierda[i] = arr[inicio + i];
for (int j = 0; j < n2; j++)
derecha[j] = arr[medio + 1 + j];
int i = 0, j = 0, k = inicio;
while (i < n1 && j < n2) {
if (izquierda[i] <= derecha[j]) {
arr[k] = izquierda[i];
i++;
} else {
arr[k] = derecha[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = izquierda[i];
i++;
k++;
}
while (j < n2) {
arr[k] = derecha[j];
j++;
k++;
}
}
void Merge( int A[], int Izq, int Der)
{
if (Izq < Der) {
int medio = Izq + (Der - Izq) / 2;
Merge(A, Izq, medio);
Merge(A, medio + 1, Der);
intercalar(A, Izq, medio, Der);
}
}
// Implementación de Métodos de Búsqueda
int BusqSec( int A[], int N, int X )
{
int i=0;
while ( (i<N) && (A[i]!= X) )
i++;
if (i>=N)
return 0;
else
return i+1;
}
int BusqBin( int V[], int N, int X )
{
int IZQ = 0, DER = N - 1;
bool BAN = false;
int CEN;
while (IZQ <= DER && !BAN) {
CEN = IZQ + (DER - IZQ) / 2; // Calcula posición central
if (X == V[CEN]) {
BAN = true; // Elemento encontrado
} else {
if (X > V[CEN]) {
IZQ = CEN + 1; // Busca en la mitad derecha
} else {
DER = CEN - 1; // Busca en la mitad izquierda
}
}
}
if (BAN) {
return CEN +1;
} else {
return 0;
}
}
int Hash(int A[], int N, int K)
{
const int VACIO = -1;
int D = K % N; // Hacer D ← H(K), genera dirección
int DX = D; // Inicializar DX
// Si ((V[DX] ≠ VACIO) y (V[DX] = K)) entonces
if (A[DX] != VACIO && A[DX] == K) {
cout << "La información está en la posición " << D << endl;
return D; // Fin
}
// Si no
DX = D + 1; // Hacer DX ← D + 1
// Mientras (DX ≠ N) y (V[DX] ≠ VACIO) y (V[DX] ≠ K) y (DX ≠ D) Repetir
while ((DX != N) && (A[DX] != VACIO) && (A[DX] != K) && (DX != D)) {
DX = DX + 1; // Hacer DX ← DX + 1
// Si (DX = N + 1) entonces
if (DX == N) {
DX = 0; // Hacer DX ← 1
}
}
// Si ((V[DX] = VACIO) o (DX = D)) entonces
if (A[DX] == VACIO || DX == D) {
return 0; // Fin
}
// Si no
return DX+1; // Fin
}
void MenuPrincipal()
{ // Variables locales
char Opc; // Variable auxiliar Opcion
int X, Y;
time_t Inicio, Final;
do {
system("cls");
cout << "\n\t\t *powered by ImNotLeo :D\n" << endl;
cout << "\t**** Metodos de Ordenacion y Busqueda. " << endl;
cout << "1. Introducir valores Usuario. " << endl;
cout << "2. Introducir valores aleatoriamente. " << endl;
cout << "3. Mostrar Arreglo. " << endl << endl;
cout << "\t**** Algoritmos de Ordenacion. " << endl;
cout << "4. Por Intercambio Directo (Burbuja). " << endl;
cout << "5. Metodo de la Sacudida (ShakerSort). " << endl;
cout << "6. Metodo de Insercion Directa. " << endl;
cout << "7. Metodo de Insercion Binaria. " << endl;
cout << "8. Metodo de Seleccion Directa. " << endl;
cout << "9. Shell. " << endl;
cout << "A. QuickSort. " << endl;
cout << "B. Monticulo (HeapSort). " << endl;
cout << "C. Intercalacion de archivos (Merge). " << endl << endl;
cout << "\t**** Algoritmos de Busqueda. " << endl;
cout << "D. Busqueda Secuencia." << endl;
cout << "E. Busqueda Binaria." << endl;
cout << "F. Hash." << endl;
cout << "0. Salir " << endl << endl;
cout << "Opcion: "; cin >> Opc;
switch (Opc) {
case '1': IngresarUsuario(); break;
case '2': IngresarAleatorio(); break;
case '3': MostrarArreglo(); system("Pause"); break;
//----------------------------------------------
case '4': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; BubbleSort( A, N ); break;
case '5': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; ShakerSort( A, N ); break;
case '6': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; InsercionDirecta( A, N ); break;
case '7': // Inserción Binaria
Inicio= time(NULL); // Tiempo inicial o actual
cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; InsercionBinaria( A, N ); // Llamada al Método de Ordenación
Final= time(NULL); // Tiempo final o actual
MostrarTiempo( Inicio, Final ); // Muestra tiempo transcurrido
break;
case '8': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; SeleccionDirecta( A, N ); break;
case '9': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; Shell( A, N ); break;
case 'A': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; QuickSort( A, 0, MAX-1 ); MostrarArreglo(); system ("pause"); break;
case 'B': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; HeapSort( A, N ); break;
case 'C': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; Merge( A, 0, MAX-1 ); MostrarArreglo(); system ("pause"); break;
//----------------------------------------------
case 'D': // Método de Búsqueda Secuencial
cout << "Escriba valor a buscar: ";
cin >> X;
Inicio= time(NULL); // Tiempo inicial o actual
Y= BusqSec( A, N, X ); // llamada al Método de Busqueda
Final= time(NULL); // Tiempo final o actual
if (Y == 0) cout << "\n\tLa informacion no esta en el arreglo. \n";
else printf("\n\tLa posicion encontrada fue %i \n", Y);
MostrarTiempo( Inicio, Final ); // Muestra tiempo transcurrido
break;
case 'E': // Método de Búsqueda Binaria
cout << "Escriba valor a buscar: ";
cin >> X;
Merge( A, 0, MAX-1 );
cout << "\n\tArreglo Original: "; MostrarArreglo();
Inicio= time(NULL); // Tiempo inicial o actual
Y= BusqBin( A, N, X ); // llamada al Método de Busqueda
Final= time(NULL); // Tiempo final o actual
if (Y == 0) cout << "\n\tLa informacion no esta en el arreglo. \n";
else printf("\n\tLa posicion encontrada fue %i \n", Y);
MostrarTiempo( Inicio, Final ); // Muestra tiempo transcurrido
break;
case 'F': // Método de Hash
cout << "Escriba valor a buscar: ";
cin >> X;
Inicio= time(NULL); // Tiempo inicial o actual
Y= Hash( A, N, X ); // llamada al Método de Busqueda
Final= time(NULL); // Tiempo final o actual
if (Y == 0) cout << "\n\tLa informacion no esta en el arreglo. \n";
else printf("\n\tLa posicion encontrada fue %i \n", Y);
MostrarTiempo( Inicio, Final ); // Muestra tiempo transcurrido
break;
};
} while (Opc!='0');
system("cls");
cout << "\n\n\tGracias por usar mi programa, puedes usarlo cuando gustes!\n" << endl;
cout << "\t\t\t\tby ImNot Leo :D\n\n" << endl;
};
// Programa o función principal del programa
int main()
{
MenuPrincipal();
return 0;
};
Top comments (0)