/**
* @file 06-QuickSort.cpp
* Utiliza el enfoque divide y vencerás para esto,
* lo que significa que la matriz de elementos
* se divide en 2 partes, y luego se aplica un algoritmo
* de ordenación rápida adicional a estas 2 partes.
* Esta división de la matriz se lleva a cabo utilizando
* un punto de pivote. La posición de un pivote se selecciona
* de manera que los elementos de la izquierda del pivote sean
* menores que el elemento de pivote y también el elemento de
* la derecha sea mayor que el elemento de pivote.
* Esta partición tiene como objetivo obtener la matriz ordenada
* en tiempo de ejecución lineal.
*/
#include <iostream>
using namespace std;
// funcion para encontrar el elemento pivote
int partition(int myarr[], int left, int right){
int i,j,pivot;
pivot = myarr[right];
i = (left - 1);
for (j = left; j <= right- 1; j++){
if (pivot > myarr[j] ){
i++;
//swap myarr[i] and myarr[j]
swap(myarr[i],myarr[j] );
}
}
//swap myarr[i + 1] and myarr[right])
swap(myarr[i+1],myarr[j] );
return (i + 1);
}
int quickSort(int myarr[], int left, int right){
int pi;
if (left < right){
pi = partition(myarr, left, right);
quickSort(myarr, left, pi - 1);
quickSort(myarr, pi + 1, right);
}
return 0;
}
void printArray(int arr[], int ind){
for (int i = 0; i<ind; i++){
cout << "arr["<< i << "] =" << arr[i] << endl; ;
}
cout << endl;
}
void swap(int &a, int &b){
int x;
x=a;
a=b;
b=x;
}
int main(int argc, char const *argv[])
{
int result=1;
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "antes de ordenar"<< endl;
printArray(arr,n);
result = quickSort(arr, 0, n);
cout << "despues de ordenar"<< endl;
printArray(arr,n);
return 0;
}
