0

Estoy siguiendo el libro de programación en C escrito por Ritchie, hay un ejemplo donde se utilizan los arreglos de apuntadores para crear un programa que ordene alfabéticamente (usando strcmp) diferentes líneas digitadas.

La cuestión es que no entiendo que hace la función que ordena las líneas, hay algunas cosas que entiendo y otras que no, el código es el siguiente:

void qsort(char *v[ ], int left, int right){

    int i, last;
    void swap(char *v[ ], int i, int j);

    if (left > = right) /* no hace nada si el arreglo contiene */
       return; /* menos de dos elementos */

    swap(v, left, (left + right)/2);
    last = left;

    for (i = left+l; i < = right; i+ +)
       if (strcmp(v[i], v[left]) < 0)

    swap(v, + +last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+l, right);

}

void swap(char *vector[], int i, int j){
  char *temp;

  temp = vector[i]; 
  vector[i] = vector[j];
  vector[j] = temp;

}

¿alguien podría explicarme con algún diagrama de flujo o algo mas gráfico, qué hace la función?.

2

1 respuesta 1

2

Se trata del algoritmo de ordenación rápida o Quicksort.

Es difícil de entender sólo mirando código, porque es un algoritmo que hasta que no lo estudias en pseudocódigo o con dibujos, no se termina de comprender.

Básicamente es un algoritmo que sigue el esquema "Divide y Vencerás", en el cual el problema se subdivide en varios subproblemas de menor tamaño, dichos subproblemas se resuelven, y las subsoluciones se combinan para formar la solución al problema original.

En el caso de este algoritmo, se elige un elemento del vector como pivote. El objetivo es que los elementos a la izquierda del pivote sean menores, y los que están a la derecha sean mayores. Entonces se inspeccionan los elementos de ambas partes, y si no están ordenadas, se intercambian algunos de sus elementos, pudiendo intercambiarse con el pivote.

En este paso, el pivote quedará ordenado, porque todos a su izquierda serán menores y todos a su derecha serán mayores.

Entonces, se llama al procedimiento de nuevo, pero en este caso, para resolver dos subproblemas: el de ordenar la parte que queda a la izquierda del pivote, y el de ordenar la parte que queda a la derecha del pivote.

Puedes ver una ejecución del algoritmo de manera visual en https://es.wikipedia.org/wiki/Quicksort

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.