Instalacion y Configuración
Metodología de Programación

Ordenar una matriz mediante el algoritmo QuickSort en C++

Este ejercicio demuestra cómo implementar el algoritmo QuickSort en C++ para ordenar un array de enteros. QuickSort es un algoritmo de ordenamiento altamente eficiente que sigue la estrategia de "divide y vencerás". Selecciona un elemento pivote y particiona el array de forma que todos los elementos menores que el pivote se encuentren a la izquierda y los mayores a la derecha. Este proceso se aplica recursivamente a los subarreglos. QuickSort es conocido por su rendimiento promedio de O(n log n), lo que lo hace adecuado para grandes conjuntos de datos. Al completar esta actividad, comprenderá mejor la recursividad, la lógica de particionamiento y las técnicas de ordenamiento eficientes.

Grupo

Algoritmos de Búsqueda y Ordenación en C++

Ojetivo

Cree una función llamada quickSort que tome como parámetros un array, un índice inicial y un índice final. Implemente la lógica de partición dentro de una función auxiliar y llame recursivamente a quickSort en los subarrays. En la función principal, defina un array de enteros y aplique la función quickSort para ordenarlo. A continuación, muestre el array ordenado.

Implemente el algoritmo QuickSort.

Ejemplo de Código C++

 Copiar Código C++ 
#include <iostream>   // Include the input-output stream library
using namespace std;

// Function to swap two integers
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// Function to partition the array and return the pivot index
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Choose the last element as pivot
    int i = low - 1;        // Index of smaller element

    for (int j = low; j < high; j++) {
        // If current element is less than or equal to pivot
        if (arr[j] <= pivot) {
            i++;                 // Move the smaller element index forward
            swap(arr[i], arr[j]);  // Swap current element with the element at i
        }
    }

    swap(arr[i + 1], arr[high]);  // Place pivot in the correct position
    return i + 1;  // Return pivot index
}

// QuickSort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // Get the pivot index

        // Recursively sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    // Initialize an unsorted array
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);  // Calculate array size

    // Call quickSort on the array
    quickSort(arr, 0, size - 1);

    // Print the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;  // End of program
}

 Salida

Sorted array: 1 5 7 8 9 10

Comparte este ejercicio C++

Más ejercicios de programación C++Algoritmos de Búsqueda y Ordenación en C++

¡Explora el conjunto de ejercicios de programación en C++! Diseñados específicamente para principiantes, estos ejercicios te ayudarán a desarrollar una sólida comprensión de los fundamentos de C++. Desde variables y tipos de datos hasta estructuras de control y funciones simples, cada ejercicio está diseñado para desafiarte gradualmente a medida que adquieres confianza en la programación en C++.