Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //QuickSort
- #include <iostream>
- #include <vector>
- /* En cada paso selecciona un eje, el primer elemento de la matriz
- * crea dos subarrays izq. der. copiando a la izq. los elemento inferiores al eje y los superiores
- * a la derercha , se vuelven a ordenar los dos subarrays recursivamente,
- * al final retorna todo el array ordenado
- */
- using namespace std;
- /*----------------------------------------------------------------------*/
- class QuickSort{
- public:
- QuickSort(vector<int> &datos);//Constructor de la clase con parametros
- virtual void ordena();
- private:
- vector <int> &matriz;
- void swap(vector<int> &matriz,int primero,int segundo);//Intercambia dos indices en la matriz
- void OperacionQuickSort(vector <int> & matriz,int inferior,int superior);//El nucleo de QuickSort
- };
- /*----------------------------------------------------------------------*/
- QuickSort::QuickSort(vector<int> &datos):matriz(datos){}//Const. inicializa la matriz
- /*----------------------------------------------------------------------*/
- void QuickSort::ordena(){
- int longitudMatriz=matriz.size();
- OperacionQuickSort(matriz,0,longitudMatriz-1);
- }
- /*----------------------------------------------------------------------*/
- void QuickSort::OperacionQuickSort(vector <int> &matriz,int inferior,int superior){ //El nucleo de QuickSort
- if (superior<=inferior){return;}
- int eje =matriz[inferior];//eje es el valor inferior de la matriz
- int comienzo=inferior;
- int parar=superior;
- while (inferior<superior){
- while(matriz[inferior]<=eje && inferior<superior){inferior++;} //Mientras que los valores son inferiores al eje sube incrementa inferior
- while (matriz[superior] > eje && inferior<=superior){superior--;}//Mientras el valor superior sea inferior al eje incrementa superior
- if (inferior<superior){ swap(matriz,superior,inferior);}
- }
- swap (matriz,superior,comienzo);//superior es igual al eje
- OperacionQuickSort(matriz,comienzo,superior-1);//eje -1, es el superior de la "sub-matriz" izquierda
- OperacionQuickSort(matriz,superior+1,parar);//eje -1, es el superior de la "sub-matriz" derecha
- }
- /*----------------------------------------------------------------------*/
- void QuickSort::swap(vector<int> &matriz,int primero,int segundo){//Intercambia dos indices en la matriz0
- int temp=matriz[primero];
- matriz[primero]=matriz[segundo];
- matriz[segundo]=temp;
- }
- /*----------------------------------------------------------------------*/
- /*----------------------------------------------------------------------*/
- int main (){
- vector <int> matrizDeTest{3,4,2,1,6,5,7,8,1,1};//Matriz de prueba
- QuickSort *instanciaQs= new QuickSort(matrizDeTest);//Crea una instancia de la clase inicializando
- for (auto i:matrizDeTest){cout <<i<<" ";}//Imprime datos de la matriz antes de ordenar
- cout <<endl;
- instanciaQs->ordena();//Ordena la matriz
- for (auto i:matrizDeTest){cout <<i<<" ";}//Imprime datos de la matriz ordenada
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement