C++ / algoritmo sort

Bienvenidos sean a este post, hoy veremos otro algoritmo de STL.

En el post anterior cuando hablamos de la funcion para buscar en forma binaria, no de la propia de STL, mencionamos que para poder realizarlo correctamente debiamos pasar los valores en forma ordenada. Debido a esto, esta mecanica es una de las mas populares y antiguas en programacion. Por esta razon, hoy en dia es muy raro tener que desarrollar una funcion para ello. Por lo general, se utiliza a la funcion sort que nos provee STL, y es algo que hemos usado en algunos momentos. Este algoritmo toma nua coleccion como entrada y devuelve otra coleccion ordenada.

Existen muchos algoritmos de busqueda pero uno de los mas populares (y rapidos) es quicksort. La idea de trabajo del algoritmo es tomar al elemento mas chico o mas grande e ir intercambiando por los elementos mas grandes o chicos para lograr ordenarlo de menor a mayor o lo contrario. Para lograr esto, la coleccion se divide en dos partes: la ordenada y sin ordenar. Siendo que la parte ordenada se inicia vacia, y para el caso de ordenar de menor a mayor el algoritmos mira por el valor mas chico en la parte sin ordenar y lo pasa a la ordenada. Esto es simplemente pasando el elemento al primer elemento pero tendra dos acciones. La primera es que incrementara el tamaño de la parte ordenada y decrementara la parte sin ordenar. Este proceso se repetira hasta que la parte sin ordenar quede completamente vacia.

Para entender el concepto vamos a tomar el codigo que vimos en el post anterior y lo modificaremos de la siguiente manera:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
size_t buscar(const vector<T>& v, const T& e, int i, int f)
{
        if (i > f) return -1;
        int m = i + (f - i) / 2;
        if (v[m] == e)
                return m;
        if (v[m] > e)
                return buscar(v, e, i, m - 1);
        return buscar(v, e, m + 1, f);
}


int main(int argc, char **argv)
{
        vector<int> v{100,22,13,54,5,16,27,98,99,10};
        int res = buscar(v, 100, 0, v.size());
        if (res!= -1)
          cout << "Valor encontrado" << endl;
        else
          cout << "Valor no encontrado" << endl;

        return 0;
}

Primero definimos la funcion encargada de la busqueda, sin entrar en muchos detalles simplemente hace una recursion tomando como referencia la mitad de un rango y buscando el valor y asi ir reduciendolo. Para mas detalles visiten el post anterior. Una vez encontrado nos devuelve la posicion donde se ubica, en caso contrario devuelve -1 para indicar que fallo.

En el main, creamos un vector con varios mezclados, lo pasamos a la funcion anterior junto al valor a buscar y el rango de busqueda. En este caso, tenemos todo el vector. Luego tenemos un condicional donde evalua el valor recibido para mostrar si fue encontrado o no. Compilemos y veamos como es la salida:

$ ./buscar
Valor no encontrado
$

Nos devolvio que el valor no fue encontrado, a pesar de que este existe. Esto es debido a como trabaja, la funcion primero compara el valor del medio del rango informado. Si el valor es menor a este, toma la mitad del lado izquierdo para evaluar los valores nuevamente. En cambio, si es mayor toma el rango del lado derecho. Este valor es mayor pero se encuentra en el rango contrario. Por lo tanto, al empezar la recursion no lo hara en el rango correcto y devuelve que no lo encontro. Tomemos el main del codigo anterior y hagamos el siguiente cambio:

int main(int argc, char **argv)
{
        vector<int> v{100,22,13,54,5,16,27,98,99,10};
        sort(v.begin(), v.end());
        for(int e : v)
                cout << e << " ";
        cout << endl;

        int res = buscar(v, 100, 0, v.size());
        if (res!= -1)
          cout << "Valor encontrado" << endl;
        else
          cout << "Valor no encontrado" << endl;

        return 0;
}

En este caso, basicamente agregamos el algoritmo de sort (por esa razon agregamos a la libreria algorithm antes) para ordenar el vector anterior. Para ello pasamos el inicio y final del mismo, y el algoritmo se encarga de ordenarlo. Luego agregamos un bucle para mostrar los valores del vector ordenado y luego seguimos con el mismo codigo anterior pero la unica diferencia es que ahora recibe un vector ordenado. Compilemos y veamos como es la salida:

$ ./buscar
5 10 13 16 22 27 54 98 99 100
Valor encontrado
$

Vemos como se ordeno el listado anterior y como ahora si fue encontrado. Tal como comentamos anteriormente, esto es debido a como trabaja el algoritmo a la hora de buscarlo. Pero sort tambien dispone de un parametro mas. Para ello debemos tomar el codigo anterior y hacer el siguiente cambio:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
size_t buscar(const vector<T>& v, const T& e, int i, int f)
{
        if (i > f) return -1;
        int m = i + (f - i) / 2;
        if (v[m] == e)
                return m;
        if (v[m] > e)
                return buscar(v, e, i, m - 1);
        return buscar(v, e, m + 1, f);
}

int main(int argc, char **argv)
{
        vector<int> v{100,22,13,54,5,16,27,98,99,10};
        sort(v.begin(), v.end(),
                [](const int& a, const int& b) { return a > b; });
        for(int e : v)
                cout << e << " ";
        cout << endl;

        int res = buscar(v, 100, 0, v.size());
        if (res!= -1)
          cout << "Valor encontrado" << endl;
        else
          cout << "Valor no encontrado" << endl;

        return 0;
}

El tercer parametro que podemos pasar es una funcion para establecer el tipo de orden que deseamos utilizar. Si no especificamos alguno, de manera predeterminada lo hara de menor a mayor. Para este ejemplo, usamos una funcion lambda (tambien conocida como funcion anonima) pero se puede utilizar una funcion normal para hacerlo. Pero en general, por un tema de practicidad y dado que esta funcion solo sera para esto se tiende a usar mas este tipo de funcion. En este caso en particular, recibe dos argumentos y solo devuelve el valor de a si es mayor que b. Esto hara que nuestro orden sea de mayor a menor. El resto sigue siendo lo mismo que haciamos antes. Compilemos y veamos como es la salida:

$ ./buscar
100 99 98 54 27 22 16 13 10 5
Valor no encontrado
$

Primer detalle, nos devolvio el orden inverso como estaba planeado pero esto nos devuelve al primer error. El valor no fue encontrado porque el orden no respeta el criterio de busqueda. Pero esta es la forma de poder invertir el orden de los datos.

En resumen, hoy hemos visto al algoritmo sort, que es, como se utiliza, un ejemplo para solucionar un inconveniente que teniamos con otra funcion, y una caracteristica para trabajar de otra manera. Espero les haya sido de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.