Implementación de Algoritmos C++: Búsqueda Binaria, Shell Sort y Más

Búsqueda Binaria (Binary Search)

Implementación del algoritmo de búsqueda binaria en C++ para encontrar un elemento en un arreglo ordenado.

#include <iostream>
#include <conio.h> // Para clrscr() y getch() (no estándar)

using namespace std;

int main() {
    // clrscr(); // Limpia la pantalla (dependiente de conio.h)
    int a[50], n, dato;
    
    cout << "Ingrese el tamaño del arreglo (max 50): ";
    cin >> n;

    cout << "Ingrese los elementos del arreglo (en orden ascendente):" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Elemento[" << i << "]: ";
        cin >> a[i];
    }

    cout << "Ingrese el número a buscar: ";
    cin >> dato;

    int primero = 0;
    int ultimo = n - 1;
    int c;
    bool band = false; // Bandera para indicar si se encontró el dato

    while (primero <= ultimo) {
        c = (primero + ultimo) / 2;

        if (dato == a[c]) {
            cout << "\nValor encontrado en la posición: " << c << endl;
            band = true;
            break; // Salir del bucle una vez encontrado
        } else if (dato > a[c]) {
            primero = c + 1;
        } else { // dato < a[c]
            ultimo = c - 1;
        }
    }

    if (!band) { // Si la bandera sigue en false
        cout << "\nValor no encontrado en el arreglo." << endl;
    }

    getch(); // Espera a que se presione una tecla (dependiente de conio.h)
    return 0;
}

Ordenamiento Shell (Shell Sort)

Implementación del algoritmo de ordenamiento Shell en C++.

#include <iostream>
#include <conio.h> // Para clrscr() y getch() (no estándar)

using namespace std;

int main() {
    // clrscr(); // Limpia la pantalla (dependiente de conio.h)
    int v[50], n, aux;

    cout << "Ingrese tamaño del vector (max 50): ";
    cin >> n;

    cout << "Ingrese los elementos del vector:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Elemento[" << i << "]: ";
        cin >> v[i];
    }

    int inter = n / 2; // Intervalo inicial

    while (inter > 0) {
        for (int i = inter; i < n; i++) {
            int j = i - inter;
            while (j >= 0) {
                int k = j + inter;
                if (v[j] <= v[k]) { // Si ya están en orden
                    j = -1; // Salir del while interno
                } else { // Intercambiar
                    aux = v[j];
                    v[j] = v[k];
                    v[k] = aux;
                    j = j - inter; // Moverse al anterior elemento del subgrupo
                }
            }
        }
        // Opcional: Mostrar proceso en cada intervalo
        /*
        cout << "\nProceso (intervalo " << inter << "): ";
        for (int l = 0; l < n; l++) {
            cout << v[l] << " ; ";
        }
        cout << endl;
        */
        inter = inter / 2; // Reducir el intervalo
    }

    cout << "\nResultado final (vector ordenado):" << endl;
    for (int i = 0; i < n; i++) {
        cout << v[i] << " ; ";
    }
    cout << endl;

    getch(); // Espera a que se presione una tecla (dependiente de conio.h)
    return 0;
}

Generación de Números Aleatorios

Genera una secuencia de números pseudoaleatorios en C++.

#include <iostream>
#include <stdlib.h> // Para rand() y srand()
#include <time.h>   // Para time()
#include <conio.h>  // Para clrscr() y getch() (no estándar)

using namespace std;

int main() {
    // clrscr(); // Limpia la pantalla (dependiente de conio.h)
    int n, i;

    cout << "Ingrese la cantidad de números aleatorios a generar: ";
    cin >> n;

    // Inicializar la semilla del generador de números aleatorios
    srand(time(NULL));

    cout << "\nNúmeros generados (entre 0 y 99):" << endl;
    for (i = 0; i < n; i++) {
        cout << rand() % 100 << " "; // Genera números entre 0 y 99
    }
    cout << endl;

    getch(); // Espera a que se presione una tecla (dependiente de conio.h)
    return 0;
}

Vector Aleatorio y Ordenamiento Burbuja

Crea un vector con números aleatorios y lo ordena usando el método de la burbuja.

#include <iostream>
#include <stdlib.h> // Para rand() y srand()
#include <time.h>   // Para time()
#include <conio.h>  // Para clrscr() y getch() (no estándar)

using namespace std;

int main() {
    // clrscr(); // Limpia la pantalla (dependiente de conio.h)
    int n, v[100], aux;

    cout << "Ingrese tamaño del vector (max 100): ";
    cin >> n;

    // Inicializar la semilla
    srand(time(NULL));

    cout << "\nVector original (aleatorio):" << endl;
    for (int i = 0; i < n; i++) {
        v[i] = rand() % 100; // Números aleatorios entre 0 y 99
        cout << v[i] << " ";
    }
    cout << endl;

    // Algoritmo de Ordenamiento Burbuja
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (v[j] > v[j + 1]) {
                // Intercambiar elementos
                aux = v[j + 1];
                v[j + 1] = v[j];
                v[j] = aux;
            }
        }
    }

    cout << "\nVector ordenado por Burbuja:" << endl;
    for (int k = 0; k < n; k++) {
        cout << v[k] << " ";
    }
    cout << endl;

    getch(); // Espera a que se presione una tecla (dependiente de conio.h)
    return 0;
}

Ordenamiento Shell e Inserción de Elemento

Ordena un vector usando Shell Sort y luego inserta un nuevo elemento manteniendo el orden.

#include <iostream>
#include <conio.h> // Para clrscr() y getch() (no estándar)

using namespace std;

int main() {
    // clrscr(); // Limpia la pantalla (dependiente de conio.h)
    int v[51], n, aux, nuevoElemento;
    // Se declara v[51] para permitir la inserción de un elemento extra si n=50

    cout << "Tamaño inicial del vector (max 50): ";
    cin >> n;

    if (n > 50) {
        cout << "Tamaño excede el máximo permitido." << endl;
        return 1;
    }

    cout << "Ingrese los elementos del vector:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Elemento[" << i << "]: ";
        cin >> v[i];
    }

    // --- Ordenamiento Shell Sort (copiado de la sección anterior) ---
    int inter = n / 2;
    while (inter > 0) {
        for (int i = inter; i < n; i++) {
            int j = i - inter;
            while (j >= 0) {
                int k = j + inter;
                if (v[j] <= v[k]) {
                    j = -1;
                } else {
                    aux = v[j];
                    v[j] = v[k];
                    v[k] = aux;
                    j = j - inter;
                }
            }
        }
        inter = inter / 2;
    }
    // --- Fin Shell Sort ---

    cout << "\nEl vector ordenado (Shell Sort):" << endl;
    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }
    cout << endl;

    // --- Inserción de un nuevo elemento --- 
    cout << "\nIngrese nuevo elemento a insertar: ";
    cin >> nuevoElemento;

    // Encontrar la posición correcta para insertar
    int pos = 0;
    while (pos < n && v[pos] < nuevoElemento) {
        pos++;
    }

    // Desplazar los elementos mayores hacia la derecha
    for (int i = n; i > pos; i--) {
        v[i] = v[i - 1];
    }

    // Insertar el nuevo elemento
    v[pos] = nuevoElemento;
    n++; // Incrementar el tamaño efectivo del vector

    cout << "\nVector con nuevo elemento insertado:" << endl;
    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }
    cout << endl;

    getch(); // Espera a que se presione una tecla (dependiente de conio.h)
    return 0;
}