#include <stdio.h>

void intercambiar(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int particion(int vector[], int inicio, int fin) {
    int pivote = vector[fin];
    int i = inicio - 1;

    for (int j = inicio; j < fin; j++) {
        if (vector[j] < pivote) {
            i++;
            intercambiar(&vector[i], &vector[j]);
        }
    }

    intercambiar(&vector[i + 1], &vector[fin]);

    return i + 1;
}

void quickSort(int vector[], int inicio, int fin) {
    if (inicio < fin) {

        int posicionPivote = particion(vector, inicio, fin);

        quickSort(vector, inicio, posicionPivote - 1);
        quickSort(vector, posicionPivote + 1, fin);
    }
}

void imprimir(int vector[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", vector[i]);
    }
    printf("\n");
}

int main() {

    int vector[] = {45, 12, 78, 34, 23, 9, 56};
    int n = sizeof(vector) / sizeof(vector[0]);

    printf("Vector original:\n");
    imprimir(vector, n);

    quickSort(vector, 0, n - 1);

    printf("Vector ordenado:\n");
    imprimir(vector, n);

    return 0;
}