Advertisement
xlujiax

QuickSort_Indices

Sep 21st, 2016
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <cstdio>
  3. #define N 10
  4. void intercambiar(int datos[], int i, int j){
  5.     int temp;
  6.     temp = datos[i];
  7.     datos[i] = datos[j];
  8.     datos[j] = temp;
  9. }
  10. void quicksort(int datos[], int izq, int der){
  11.     int limite,i;
  12.     if(izq>=der) return; //Condición de salida
  13.     intercambiar(datos,izq,(izq+der)/2); //Con el pivote se intercambia
  14.     limite = izq;
  15.     for(i=izq+1;i<=der;i++)
  16.         if(datos[izq]>datos[i]) intercambiar(datos,++limite,i); //Condición de intercambio
  17.     intercambiar(datos,izq,limite);
  18.     quicksort(datos,izq,limite-1);
  19.     quicksort(datos,limite+1,der);
  20. }
  21. void quicksortIndices(int datos[], int izq, int der, int indices[]){
  22.     int limite,i;
  23.     if(izq>=der) return; //Condición de salida
  24.     intercambiar(indices,izq,(izq+der)/2); //Con el pivote se intercambia
  25.     limite = izq;
  26.     for(i=izq+1;i<=der;i++)
  27.         if(datos[indices[izq]]>datos[indices[i]]) intercambiar(indices,++limite,i); //Condición de intercambio
  28.     intercambiar(indices,izq,limite);
  29.     quicksortIndices(datos,izq,limite-1,indices);
  30.     quicksortIndices(datos,limite+1,der,indices);
  31. }
  32. void imprimeArreglo(int arreglo[], int tamano){
  33.     for(int i=0;i<tamano;i++)
  34.         printf("%d ", arreglo[i]);
  35.     printf("\n");
  36. }
  37. void inicializacionIndices(int indices[], int tamanoArreglo){
  38.     for(int i=0;i<tamanoArreglo;i++)
  39.         indices[i] = i;
  40. }
  41. int main(int argc, char** argv) {
  42.     int arreglo[N] = {9,3,4,2,1,5,6,10,7,8};
  43.     printf("Arreglo Original: \n");
  44.     imprimeArreglo(arreglo,N);
  45.     printf("Arreglo Ordenado: \n");
  46.     quicksort(arreglo,0,N-1);
  47.     imprimeArreglo(arreglo,N);
  48.     //Probando el quicksort de indices con el arreglo original
  49.     int arreglo2[N] = {9,3,4,2,1,5,6,10,7,8};
  50.     int indices[N];
  51.     inicializacionIndices(indices, N); //La inicializacion del arreglo de indices, indices[N] = {0,1,2,3,4,5,6,7,8,9,...} depende del tamaño del arreglo
  52.     printf("Arreglo Indices Ordenados del Arreglo Original:\n");
  53.     quicksortIndices(arreglo2,0,N-1,indices);
  54.     imprimeArreglo(indices,N);
  55.     return 0;}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement