Hace unos días hablando con un amigo que es autodidacta y está aprendiendo a programar mediante cursos, me comentó que le preguntaron sobre algoritmos de ordenamiento y no tenía ni idea de que eran. Seguramente, si estudiaste alguna carrera universitaria, los viste en algún lenguaje, casi siempre en Java.
Si bien no necesitas recordar todos los algoritmos, inclusive tal vez no lo uses, es importante saberlo por 2 razones. La primera, muchos de estos son utilizados en las bases de datos para obtener mejores resultados en las búsquedas. La segunda y más importante, son preguntas que se realizan en las entrevistas de trabajo.
Para ayudar a mi amigo, decidí escribir este post con los algoritmos de búsqueda que pueden preguntarte en una entrevista de trabajo.
Programación dinámica
Básicamente, trata de reducir las funciones recesivas eliminando las llamadas recursivas mediante alguna estrategia. Para entrar en más detalle, la recursividad se elimina almacenando los resultados de las subfunciones anteriores para que no tengan que volver a llamarse varias veces. Según el manual, se reduce la complejidad temporal de ejecución de forma exponencial a polinomial. Algunos ejemplos de estas estrategias:
Ugly Numbers
class SampleUglyNumbers{
/*This function divides a by
greatest divisible power of b*/
static int maxDivide(int a, int b)
{
while (a % b == 0)
a = a / b;
return a;
}
/* Function to check if a number
is ugly or not */
static int isUgly(int no)
{
no = maxDivide(no, 2);
no = maxDivide(no, 3);
no = maxDivide(no, 5);
return (no == 1) ? 1 : 0;
}
/* Function to get the nth ugly
number*/
static int getNthUglyNo(int n)
{
int i = 1;
// ugly number count
int count = 1;
// Check for all integers
// until count becomes n
while (n > count) {
i++;
if (isUgly(i) == 1)
count++;
}
return i;
}
// Driver code
public static void Main()
{
int no = getNthUglyNo(150);
// Function call
Console.WriteLine("150th ugly"
+ " no. is " + no);
}
}
Fibonacci Numbers
using System;
class SampleFibonacciNumbers
{
static void fib(int n)
{
int a = 0, b = 1, c;
if (n >= 0)
Console.Write( a + " ");
if (n >= 1)
Console.Write( b + " ");
for (int i = 2; i <= n; i++)
{
c = a + b;
Console.Write( c + " ");
a = b;
b = c;
}
}
public static void Main ()
{
fib(9);
}
}
Binomial Coefficient
public static long BinomCoefficient(long n, long k)
{
if (k > n) { return 0; }
if (n == k) { return 1; }
if (k > n - k) { k = n - k; }
long c = 1;
for (long i = 1; i <= k; i++)
{
c *= n--;
c /= i;
}
return c;
}
Permutation Coefficient
using System;
class SamplePermutatioCoefficient
{
// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff(int n,
int k)
{
int [,]P = new int[n + 2,k + 2];
// Caculate value of Permutation
// Coefficient in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0;
j <= Math.Min(i, k);
j++)
{
// Base Cases
if (j == 0)
P[i,j] = 1;
// Calculate value using previosly
// stored values
else
P[i,j] = P[i - 1,j] +
(j * P[i - 1,j - 1]);
// This step is important
// as P(i,j)=0 for j>i
P[i,j + 1] = 0;
}
}
return P[n,k];
}
// Driver Code
public static void Main()
{
int n = 10, k = 2;
Console.WriteLine("Value of P( " + n +
","+ k +")" + " is " +
permutationCoeff(n, k) );
}
}
Binary Search
La búsqueda binaria funciona cuando tenemos una matriz ordenada de elementos y una clave de búsqueda. Funciona seleccionando el elemento del medio y comparándolo con la clave de búsqueda. Si el valor que buscamos es igual al elemento del medio, este será retornado. Si el elemento es menor o mayor del elemento del medio, la búsqueda seguirá de una mitad u otra mitad dejando una de las 2 miradas fuera de la siguiente búsqueda. Una vez separada se vuelve a comenzar por el valor medio.
public static object BinarySearchDisplay(int[] arr, int key) {
int minNum = 0;
int maxNum = arr.Length - 1;
while (minNum <=maxNum) {
int mid = (minNum + maxNum) / 2;
if (key == arr[mid]) {
return ++mid;
} else if (key < arr[mid]) {
max = mid - 1;
}else {
min = mid + 1;
}
}
return "None";
}
Depth First Search
Este algoritmo de búsqueda inicia el proceso de búsqueda desde el nodo y llega hasta la última hoja de la rama izquierda. Luego de llegar hasta la hoja más a la izquierda, comienza a retroceder y atraviesa el árbol hacia la derecha. Este tipo de búsqueda tiene un problema, si tenemos más de un ciclo, es posible que estemos obligados a visitar más de un nodo una vez. El tiempo de respuesta dependerá del número de vértices y aristas que tengamos en un grafo.
public static bool DepthFirstSearch<T>(this IEnumerable<T> vertices, T rootVertex, T targetVertex, Func<T, IEnumerable<T>> getConnectedVertices, Func<T, T, bool> matchFunction = null)
{
if (getConnectedVertices == null)
{
throw new ArgumentNullException("getConnectedVertices");
}
if (matchFunction == null)
{
matchFunction = (t, u) => object.Equals(t, u);
}
var directlyConnectedVertices = getConnectedVertices(rootVertex);
foreach (var vertex in directlyConnectedVertices)
{
if (matchFunction(vertex, targetVertex))
{
return true;
}
else if (vertices.DepthFirstSearch(vertex, targetVertex, getConnectedVertices, matchFunction))
{
return true;
}
}
return false;
}
Merge Sort
Este pertenece a los algoritmos de ordenamiento. Funciona según los principios de divide y vencerás. Esto quiere decir que dividiremos el problema en partes más pequeñas y las resolveremos una a una para fusionarlas finalmente. Merge Sort divide la matriz por la mitad e invoca a una función de ordenación en ambas mitades. Esas mitades se ordenan y luego se combinan mediante la función merge.
using System;
namespace SampleMergeSort
{
class Program
{
static public void MergeMethod(int[] numbers, int left, int mid, int right)
{
int[] temp = new int[25];
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
temp[tmp_pos++] = numbers[left++];
else
temp[tmp_pos++] = numbers[mid++];
}
while (left <= left_end)
temp[tmp_pos++] = numbers[left++];
while (mid <= right)
temp[tmp_pos++] = numbers[mid++];
for (i = 0; i < num_elements; i++)
{
numbers[right] = temp[right];
right--;
}
}
static public void SortMethod(int[] numbers, int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
SortMethod(numbers, left, mid);
SortMethod(numbers, (mid + 1), right);
MergeMethod(numbers, left, (mid + 1), right);
}
}
static void Main(string[] args)
{
int[] numbers = { 38, 27, 43, 3, 9, 82, 10 };
int len = numbers.Length;
Console.WriteLine("Before Merge Sort:");
foreach(int item in numbers)
{
Console.Write(item + " ");
}
Console.WriteLine();
Console.WriteLine("After Merge Sort");
SortMethod(numbers, 0, len - 1);
foreach (int item in numbers)
{
Console.Write(item + " ");
}
Console.Read();
}
}
}
Quick Sort
Al igual que el anterior, se basa en la premisa divide y triunfarás. La diferencia con el anterior es en su funcionalidad de ordenamiento. En este algoritmo seleccionaremos el último elemento como el número pivot y lo colocaremos en medio. Quedarán a la izquierda los números más pequeños y a la derecha los números más grandes. Ambos lados se llamarán nuevamente con la función de ordenamiento que dará como resultado la matriz ordenada.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Quick_Sort
{
class Program
{
private static void Quick_Sort(int[] arr, int left, int right)
{
if (left < right)
{
int pivot = Partition(arr, left, right);
if (pivot > 1) {
Quick_Sort(arr, left, pivot - 1);
}
if (pivot + 1 < right) {
Quick_Sort(arr, pivot + 1, right);
}
}
}
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[left];
while (true)
{
while (arr[left] < pivot)
{
left++;
}
while (arr[right] > pivot)
{
right--;
}
if (left < right)
{
if (arr[left] == arr[right]) return right;
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
else
{
return right;
}
}
}
static void Main(string[] args)
{
int[] arr = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };
Console.WriteLine("Original array : ");
foreach (var item in arr)
{
Console.Write(" " + item);
}
Console.WriteLine();
Quick_Sort(arr, 0, arr.Length-1);
Console.WriteLine();
Console.WriteLine("Sorted array : ");
foreach (var item in arr)
{
Console.Write(" " + item);
}
Console.WriteLine();
}
}
}
Conclusiones
Estos son los algoritmos más consultados en las entrevistas. Existen una gran cantidad de algoritmos de búsqueda y ordenamiento. Si deseas que veamos que veamos todo un tutorial de los que existe dejame en los comentarios.
