Ordenación y búsqueda son dos temas fundamentales en programación, y por esto son ampliamente estudiados. Esto se debe a dos razones: la primera, es que muchos problemas pueden ser resueltos de manera más eficiente si los datos están ordenados, y muchos otros necesitan ordenar o buscar datos como pasos intermedios; la segunda razón es que los algoritmos de ordenación utilizan una gran variedad de técnicas de programación, por lo cual son útiles para aprenderlas.

Al ser tan estudiados, existe gran diversidad de algoritmos, y la elección de cual es mejor depende en gran medida de cual va a ser su aplicación. Algunos factores que afectan a la elección son: la cantidad de datos, en que orden los obtenemos, posibles limitantes de los datos (principalmente el tamaño), restricciones de memoria, tipo de almacenamiento que utilicemos, si los datos los podemos procesar en paralelo, etc.

Nosotros no debemos preocuparnos mucho por estas limitantes, ya que dentro de los concursos de programación muchos de estos factores ya están determinados. Podemos considerar que nuestros programas correrán dentro de una PC convencional, y que los datos estarán alojados en RAM. Otra limitante, que no es del concurso pero que vamos a agregar, es que los datos los guardaremos dentro de un arreglo.

Una de las definiciones más comunes de ordenación es la siguiente: dada una lista de datos (generalmente números), encontrar la forma de acomodarlos de forma no decreciente, es decir, de menor a mayor. De manera formal lo podemos definir como: dado un conjunto de n elementos a₁, a₂,..., a_n, encontrar una permutación σ tal que a_σ(1) ≤ a_σ(2) ≤ ... ≤ a_σ(n). Aunque generalmente se ordena de forma no decreciente, también se puede ordenar un arreglo de forma no creciente de forma que la permutación de sus elementos sea a_σ(1) ≥ a_σ(2) ≥ ... ≥ a_σ(n).

Decimos que una ordenación es estable cuando datos que tienen el mismo valor de comparación, permanecen en la misma secuencia después de ordenar el arreglo. Esto es particularmente útil cuando queremos ordenar datos con varios campos. Por ejemplo: si deseamos ordenar un arreglo que contiene fechas, ordenando primero por días, luego por meses y después por años, si el algoritmo es estable las fechas terminarían ordenadas correctamente, mientras que si no lo es, los años estarían ordenados pero muy posiblemente los meses y los días no.

La mayoría de los algoritmos de ordenación se basan en la comparación entre datos para después acomodarlos. Los más sencillos e intuitivos son de orden O(n²), y son útiles cuando necesitamos ordenar pocos datos o cuando la ordenación no es una parte crítica en el programa.

El más común y utilizado de estos algoritmos es, probablemente, la ordenación por burbuja (bubblesort). El inconveniente de este método, es que es uno de los más lentos. Por esto, si vamos a recurrir a un algoritmo O(n²) para ordenar, es mejor utilizar ordenación por inserción (insertionsort), que a pesar de ser del mismo orden, realiza menos operaciones y es casi igual de intuitivo.

Existen ordenaciones más veloces. Una de ellas es la Ordenación Rápida de Hoare (quicksort), la cuál se basa en técnicas de “divide y vencerás”. Esta ordenación es una de las más rápidas y utilizadas, inclusive C ya tiene una implementación que podemos usar. El problema que tiene es que, a pesar de tener cota promedio Θ(nlgn), su peor caso es O(n²). Otros algoritmos garantizan ser O(nlgn), como el caso de la ordenación por mezcla (mergesort) y por montículos (heapsort), y aunque en promedio son más lentos por alguna constante, no tenemos problemas con el peor caso.

Está demostrado que mediante comparaciones, la cota más baja que podemos obtener es Ω(nlgn). Pero si no utilizamos comparaciones y sabemos algunos datos adicionales, podemos obtener cotas más bajas. Un ejemplo de esto es la ordenación por conteo, que puede ordenar datos enteros en O(n) si se conoce el rango de dichos números.

Podemos definir búsqueda como el acto de revisar un conjunto de datos hasta encontrar el que nos interesa o averiguar que el dato no existe en conjunto. De manera formal: dado un conjunto de n elementos a₁, a₂, ..., a_n y un elemento d a buscar, encontrar una i (1 ≤ i ≤ n) tal que a_i = d, o determinar que no existe tal i.

El mejor algoritmo de búsqueda dependerá de la forma en que estén arreglados los datos. Si los datos no se encuentran en orden, necesitamos buscar todo el arreglo hasta encontrar la solución. En caso contrario, y considerando que estamos buscando dentro de un arreglo, podemos utilizar un algoritmo conocido como búsqueda binaria que encuentra los datos en O(lgn).