Métodos de Ordenación y Búsqueda en C++: Implementación Práctica de Algoritmos

Métodos de Ordenación y Búsqueda en C++

A continuación se presenta un programa en C++ que implementa distintos métodos de ordenación y búsqueda sobre un arreglo de enteros. El programa permite al usuario ingresar los datos, elegir el algoritmo deseado y visualizar el resultado.

Librerías y espacio de nombres

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

Declaración de funciones

void Ingresar(int *A, int x);
void Orden(int *A, int x);
void Seleccion(int *A, int x);
void Insercion(int *A, int x);
void Burbuja(int *A, int x);
void Shell(int *A, int x);
void Quicksort(int *A, int p, int x);
int secuencial(int *A, int b, int x);
void Mostrar(int *A, int x);

Función principal

int main(){
    char op;
    int m = 0, y = 0, p = 0, b = 0, z = 0;

    system("color 4");
    do{
        system("Cls");
        cout << "\n\t\t**** MÉTODOS DE ORDENACIÓN ****";
        cout << "\n\tNúmero de elementos: ";
        cin >> y;

        int *A1 = new int[y];
        Ingresar(A1, y);

        cout << "\n\t\t=> Elija un método:";
        cout << "\n\t1. M. de intercambio"
             << "\n\t2. M. por selección"
             << "\n\t3. M. por inserción"
             << "\n\t4. M. de burbuja"
             << "\n\t5. M. Shell"
             << "\n\t6. M. Quicksort"
             << "\n\t7. Búsqueda secuencial y binaria"
             << "\n\t8. Salir: ";
        cin >> m;

        switch(m){
            case 1:
                system("Cls");
                cout << "\n\t\t**** MÉTODO DE INTERCAMBIO ****";
                Orden(A1, y);
                Mostrar(A1, y);
                cout << "\n\t¿Desea regresar al menú principal (s/n)? ";
                cin >> op;
                break;

            case 2:
                system("Cls");
                cout << "\n\t\t**** MÉTODO DE SELECCIÓN ****";
                Seleccion(A1, y);
                cout << "\n\t¿Desea regresar al menú principal (s/n)? ";
                cin >> op;
                break;

            case 3:
                system("Cls");
                cout << "\n\t\t**** MÉTODO DE INSERCIÓN ****";
                Insercion(A1, y);
                cout << "\n\t¿Desea regresar al menú principal (s/n)? ";
                cin >> op;
                break;

            case 4:
                system("Cls");
                cout << "\n\t\t**** MÉTODO DE BURBUJA ****";
                Burbuja(A1, y);
                Mostrar(A1, y);
                cout << "\n\t¿Desea regresar al menú principal (s/n)? ";
                cin >> op;
                break;

            case 5:
                system("Cls");
                cout << "\n\t\t**** MÉTODO SHELL ****";
                Shell(A1, y);
                Mostrar(A1, y);
                cout << "\n\t¿Desea regresar al menú principal (s/n)? ";
                cin >> op;
                break;

            case 6:
                system("Cls");
                cout << "\n\t\t**** MÉTODO QUICKSORT ****";
                Quicksort(A1, p, y - 1);
                Mostrar(A1, y);
                cout << "\n\t¿Desea regresar al menú principal (s/n)? ";
                cin >> op;
                break;

            case 7:
                system("Cls");
                cout << "\n\t\t**** BÚSQUEDA SECUENCIAL Y BINARIA ****";
                cout << "\n\t¿Qué número desea buscar? ";
                cin >> b;
                Mostrar(A1, y);
                cout << "\n\tSu valor se encuentra en la posición: "
                     << secuencial(A1, b, y);
                cout << "\n\t¿Desea regresar al menú principal (s/n)? ";
                cin >> op;
                break;

            case 8:
                return 0;
        }
        delete[] A1;
    } while(op != 'n');

    system("pause");
    return 0;
}

Ingreso de datos

void Ingresar(int *A, int x){
    cout << "\n\tIngresar datos:\n";
    for(int i = 0; i < x; i++){
        cout << "\n\t";
        cin >> A[i];
    }
}

Método de intercambio

void Orden(int *A, int x){
    int y;
    for(int i = 0; i < x; i++){
        for(int j = i + 1; j < x; j++){
            if(A[j] < A[i]){
                y = A[j];
                A[j] = A[i];
                A[i] = y;
            }
        }
    }
}

Método por selección

void Seleccion(int *A, int x){
    int tp, p_min;
    cout << "\n\tDatos:\n";
    for(int i = 0; i < x - 1; i++){
        p_min = i;
        for(int j = i + 1; j < x; j++){
            if(A[j] < A[p_min])
                p_min = j;
        }
        tp = A[i];
        A[i] = A[p_min];
        A[p_min] = tp;
    }
    cout << "\n\tPaso " << x << ": " << A[p_min];
}

Método por inserción

void Insercion(int *A, int x){
    int tp, i, j;
    cout << "\n\tDatos:\n";
    for(i = 1; i < x; i++){
        tp = A[i];
        for(j = i; (j > 0) && (tp < A[j - 1]); j--){
            A[j] = A[j - 1];
            A[j - 1] = tp;
        }
        cout << "\n\tPaso " << i << ": " << A[j - 1];
    }
}

Método de burbuja

void Burbuja(int *A, int x){
    int aux;
    for(int i = 0; i < x; i++){
        for(int j = 0; j < x - 1; j++){
            if(A[j] > A[j + 1]){
                aux = A[j];
                A[j] = A[j + 1];
                A[j + 1] = aux;
            }
        }
    }
}

Método Shell

void Shell(int *A, int x){
    int i, j, ic, tp;
    for(ic = 1; ic < x; ic = ic * 3 + 1);

    while(ic > 0){
        for(i = ic; i < x; i++){
            j = i;
            tp = A[i];
            while((j >= ic) && (A[j - ic] > tp)){
                A[j] = A[j - ic];
                j = j - ic;
            }
            A[j] = tp;
        }
        ic /= 2;
    }
}

Método Quicksort

void Quicksort(int *A, int p, int x){
    int i, j, tp, cent;
    double pivote;

    cent = (p + x - 1) / 2;
    pivote = A[cent];
    cout << "\n\tEl pivote seleccionado es: " << pivote << "\n";

    i = p;
    j = x;
    do{
        while(A[i] < pivote) i++;
        while(A[j] > pivote) j--;
        if(i <= j){
            tp = A[i];
            A[i] = A[j];
            A[j] = tp;
            i++;
            j--;
        }
    } while(i <= j);

    if(p < j)
        Quicksort(A, p, j); // Mismo proceso con la sublista izquierda
    if(i < x)
        Quicksort(A, i, x); // Mismo proceso con la sublista derecha
}

Búsqueda secuencial

int secuencial(int *A, int b, int x){
    int t = 0;
    for(int i = 0; i < x; i++){
        if(b == *(A + i)){
            t = i + 1;
            break;
        }
    }
    return t;
}

Mostrar resultados

void Mostrar(int *A, int x){
    cout << "\n\tLos datos ordenados son:\n";
    for(int i = 0; i < x; i++){
        cout << "\n\t" << A[i];
    }
}

Conclusiones

Este programa permite comparar distintos algoritmos de ordenación (intercambio, selección, inserción, burbuja, Shell y Quicksort) y de búsqueda, siendo una herramienta útil para comprender su funcionamiento y sus diferencias en eficiencia y complejidad.