TIPOS DE ALGORITMO SEGUN SU FUNCIO

Tipos de algoritmos según su función

1. Algoritmo de ordenamiento
2. Algoritmo de búsqueda

1). En computación y matemáticas un algoritmo de ordenamiento recursivo es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.
Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSort fue analizado desde 1956^{[. ]} Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, el ordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.

2). Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.
La variante más simple del problema es la búsqueda de un número en un vector.

Búsqueda secuencial

Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del array hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del array. A continuación se muestra el pseudocódigo del algoritmo:

Datos de entrada:

  vec: vector en el que se desea buscar el dato

  tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.

  dato: elemento que se quiere buscar.

Variables

  pos: posición actual en el array

pos = 0

Mientras pos < tam:

 Si vec[pos] == dato devolver verdadero y/o pos, de lo contrario:

 pos = pos + 1

Fin (Mientras)

Devolver falso,

Búsqueda dicotómica (binaria)

Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.
Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).
Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.
A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del array.

Datos de entrada:

  vec: vector en el que se desea buscar el dato

  tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.

  dato: elemento que se quiere buscar.

Variables

  centro: subíndice central del intervalo

  inf: límite inferior del intervalo

  sup: límite superior del intervalo

inf = 0

sup = tam-1

Mientras inf <= sup:

  centro = ((sup - inf) / 2) + inf // División entera: se trunca la fracción

  Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:

   Si dato < vec[centro] entonces:

    sup = centro - 1

   En caso contrario:

    inf = centro + 1

Fin (Mientras)

Devolver Falso

Implementación recursiva en C++

#include <iostream>

#include <vector>

bool busqueda_dicotomica(vector<int> v, int principio, int fin, int x){

    bool res;

    if(principio < fin){

        int m = (principio + fin)/2;

        if(x < v[m]) res = busqueda_dicotomica(v, principio, m, x);

        else if(x > v[m]) res = busqueda_dicotomica(v, m+1, fin, x);

        else res = true;

    }else res = false;

    return res;

}

/*{Post: Si se encuentra devuelve true, sino false}*/