Advertisement
AntonioVillanueva

QuickSort c++

Sep 2nd, 2018
267
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. //QuickSort
  2. #include <iostream>
  3. #include <vector>
  4. /* En cada paso selecciona un eje, el primer elemento de la matriz
  5.  * crea dos subarrays  izq. der. copiando a la izq. los elemento inferiores al eje y los superiores
  6.  * a la derercha , se vuelven a ordenar los dos subarrays  recursivamente,
  7.  * al final retorna todo el array ordenado
  8.  */
  9. using namespace std;
  10. /*----------------------------------------------------------------------*/
  11. class QuickSort{
  12.     public:
  13.     QuickSort(vector<int> &datos);//Constructor de la clase con parametros
  14.     virtual void ordena();     
  15.    
  16.     private:
  17.     vector <int> &matriz;
  18.     void swap(vector<int> &matriz,int primero,int segundo);//Intercambia dos indices en la matriz
  19.     void OperacionQuickSort(vector <int> & matriz,int inferior,int superior);//El nucleo de QuickSort
  20. };
  21. /*----------------------------------------------------------------------*/
  22. QuickSort::QuickSort(vector<int> &datos):matriz(datos){}//Const. inicializa la matriz
  23. /*----------------------------------------------------------------------*/
  24. void QuickSort::ordena(){
  25.     int longitudMatriz=matriz.size();
  26.     OperacionQuickSort(matriz,0,longitudMatriz-1);
  27. }
  28. /*----------------------------------------------------------------------*/
  29. void QuickSort::OperacionQuickSort(vector <int> &matriz,int inferior,int superior){ //El nucleo de QuickSort
  30.     if (superior<=inferior){return;}
  31.    
  32.     int eje =matriz[inferior];//eje es el valor inferior de la matriz
  33.     int comienzo=inferior;
  34.     int parar=superior;
  35.    
  36.     while (inferior<superior){
  37.         while(matriz[inferior]<=eje && inferior<superior){inferior++;}  //Mientras que los valores son inferiores al eje sube incrementa inferior  
  38.         while (matriz[superior] > eje && inferior<=superior){superior--;}//Mientras el valor superior sea inferior al eje incrementa superior
  39.        
  40.         if (inferior<superior){ swap(matriz,superior,inferior);}
  41.     }      
  42.     swap (matriz,superior,comienzo);//superior es igual al eje  
  43.  
  44.     OperacionQuickSort(matriz,comienzo,superior-1);//eje -1, es el superior de la "sub-matriz" izquierda
  45.     OperacionQuickSort(matriz,superior+1,parar);//eje -1,  es el superior de la "sub-matriz" derecha   
  46. }
  47.  
  48. /*----------------------------------------------------------------------*/
  49. void QuickSort::swap(vector<int> &matriz,int primero,int segundo){//Intercambia dos indices en la matriz0
  50.     int temp=matriz[primero];
  51.     matriz[primero]=matriz[segundo];
  52.     matriz[segundo]=temp;
  53. }
  54. /*----------------------------------------------------------------------*/
  55. /*----------------------------------------------------------------------*/
  56. int main (){
  57.     vector <int> matrizDeTest{3,4,2,1,6,5,7,8,1,1};//Matriz de prueba
  58.     QuickSort *instanciaQs= new QuickSort(matrizDeTest);//Crea una instancia de la clase inicializando
  59.    
  60.     for (auto i:matrizDeTest){cout <<i<<" ";}//Imprime datos de la matriz antes de ordenar
  61.    
  62.     cout <<endl;
  63.    
  64.     instanciaQs->ordena();//Ordena la matriz
  65.        
  66.     for (auto i:matrizDeTest){cout <<i<<" ";}//Imprime datos de la matriz ordenada
  67.  
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement