Métodos de ordenación y búsqueda

Carreño Pardo Douglas Andrey

Universidad Nacional de Loja
[email protected]
Abstract—Este ensayo explora en profundidad seis algoritmos
fundamentales de ordenación y búsqueda utilizados en estructuras Este algoritmo reduce la cantidad de movimientos de datos, por
de datos, destacando su funcionamiento, eficiencia y aplicación en lo que puede ser útil cuando los intercambios son costosos (por
diferentes contextos computacionales. Se analizan métodos
ejemplo, en arreglos de objetos grandes) [1].
clásicos como Selection Sort y Binary Search, junto con técnicas
avanzadas como Enhanced Merge Sort, Radix Sort y Hashing
semisupervisado. B. MERGE SORT MEJORADO
I. INTRODUCCIÓN El algoritmo Enhanced Merge Sort es una variación del clásico
En la programación, ordenar y buscar datos son operaciones Merge Sort que optimiza el proceso de mezcla para reducir el
esenciales para manejar la información de forma eficiente. Para tiempo de ejecución. Mantiene la complejidad O(n log n), pero
ello, se utilizan algoritmos conocidos como métodos de mejora el rendimiento con listas pequeñas o parcialmente
ordenación y búsqueda, los cuales permiten organizar los datos ordenadas, utilizando estrategias como Max-Min y mezcla
y encontrar elementos específicos dentro de estructuras como iterativa[2].
arreglos o listas. Este ensayo analiza varios de estos métodos,
destacando su funcionamiento, ventajas y aplicaciones. void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
II. MÉTODOS DE ORDENACIÓN mergeSort(arr, l, m);
Un método de ordenación es un procedimiento algorítmico mergeSort(arr, m + 1, r);
diseñado para reorganizar los elementos de una estructura de merge(arr, l, m, r);
datos (como un arreglo o lista) en un orden determinado, ya sea }
ascendente o descendente, de acuerdo con un criterio de }[2]
comparación definido [1] [2]. El arreglo se divide recursivamente en mitades hasta obtener
arreglos de uno o dos elementos, que luego se ordenan y
fusionan mediante un proceso eficiente de mezcla que prioriza
A. SELECTION SORT comparaciones entre pares alternos [2].
El algoritmo de ordenación por selección (Selection Sort) es un
método simple que selecciona repetidamente el elemento más Es ideal para procesamiento de grandes volúmenes de datos en
pequeño del subconjunto no ordenado y lo intercambia con el estructuras como listas encadenadas o datos externos (archivos)
primer elemento no ordenado. Se caracteriza por su facilidad de [2].
implementación, aunque es ineficiente en grandes conjuntos de
datos debido a su complejidad cuadrática [1]: C. RADIX SORT
Radix Sort es un algoritmo de ordenación no comparativo que
void selectionSort(int arr[]) { clasifica los datos procesando cada dígito. Utiliza una
int n = arr.length; distribución basada en posiciones de menor a mayor
for (int i = 0; i < n-1; i++) { significancia. En su versión paralela para GPU, puede ser hasta
int min_idx = i; dos veces más rápido que las versiones anteriores en grandes
for (int j = i+1; j < n; j++) volúmenes de datos [3].
if (arr[j] < arr[min_idx])
min_idx = j; def counting_sort(arr, exp):
int temp = arr[min_idx]; n = len(arr)
arr[min_idx] = arr[i]; output = [0] * n
arr[i] = temp; count = [0] * 10
}
}[1] for i in range(n):
El algoritmo recorre el arreglo y selecciona el menor elemento index = (arr[i] // exp) % 10
del subconjunto restante, lo intercambia con el primer elemento count[index] += 1
de la parte no ordenada, y repite hasta que el arreglo esté
completamente ordenado [1]. for i in range(1, 10):
 count[i] += count[i - 1] B. BINARY SEARCH
Binary Search es un algoritmo eficiente para buscar elementos
for i in range(n - 1, -1, -1): en arreglos ordenados. Divide el arreglo a la mitad y descarta
index = (arr[i] // exp) % 10 una mitad en cada paso, logrando complejidad logarítmica [5].
output[count[index] - 1] = arr[i] O(log n) int binarySearch(int arr[], int key) {
count[index] -= 1
int left = 0, right = arr.length - 1;
for i in range(n):
arr[i] = output[i]
[3]. while (left <= right) {

Se procesan los dígitos de los números desde la menor hasta la int mid = left + (right - left) / 2;
mayor significancia, usando Counting Sort como subrutina.
Cada paso asegura el orden parcial que se va acumulando hasta if (arr[mid] == key) return mid;
lograr un orden total [3].
else if (arr[mid] < key) left = mid + 1;
Radix Sort es especialmente eficiente cuando se trabaja con
claves de longitud fija y registros grandes, como en GPUs y
else right = mid - 1;
simulaciones físicas [3].

}[5]
III. MÉTODOS DE BÚSQUEDA
Un método de búsqueda es un algoritmo diseñado para localizar
return -1;
un elemento específico dentro de una estructura de datos, como
un arreglo, lista, árbol o base de datos. Su objetivo es determinar
si dicho elemento existe y, en caso afirmativo, devolver su }.[5]
ubicación. Dependiendo de la estructura y el orden de los datos,
los métodos de búsqueda pueden ser secuenciales, binarios o El algoritmo compara el valor buscado con el valor central del
basados en técnicas de dispersión (hashing), cada uno con arreglo. Si no coincide, descarta la mitad que no puede contener
distintos niveles de eficiencia. el valor y repite el proceso sobre la mitad restante. Aunque es
muy eficiente, solo funciona si el arreglo está previamente
A. LINEAR SEARCH ordenado. Es la base de algoritmos más avanzados como
búsqueda exponencial o interpolada [5].
La búsqueda lineal recorre cada elemento del arreglo desde el
inicio hasta encontrar el objetivo. La variante Two-Way Linear
Search mejora el tiempo de búsqueda al comparar C. HASHING
simultáneamente desde los extremos del arreglo hacia el centro Hashing es una técnica para acceso rápido a datos mediante una
[4]. función hash que mapea claves a índices en una tabla. El
documento analiza "Semi-Supervised Hashing", que mezcla
int twoWayLinearSearch(int arr[], int key) { aprendizaje supervisado y no supervisado para generar códigos
int left = 0, right = arr.length - 1; binarios que preservan similitud semántica [6].
while (left <= right) {
if (arr[left] == key) return left; Fórmula genérica:
if (arr[right] == key) return right;
left++;
h(x) = sgn(w · x + b) --> y(x) = (1 + h(x)) / 2 [6].
right--;
}
return -1; El conjunto de datos se transforma mediante funciones hash en
}[4] códigos binarios que preservan las relaciones de similitud. El
Se comienza la búsqueda desde ambos extremos del arreglo, modelo semi supervisado ajusta estas funciones según etiquetas
reduciendo la cantidad de iteraciones necesarias cuando el valor conocidas y distribución general de los datos. Es ideal para
buscado se encuentra cerca de los bordes. Esta versión es buscar vecinos más cercanos (ANN) en bases de datos grandes
especialmente efectiva cuando se espera que el dato se y multidimensionales como las de imágenes o videos [6].
encuentre en los extremos del arreglo [4].
 IV. CUAL MÉTODO DE ORDENACIÓN Y BÚSQUEDA
USARÍAS?
La elección del método depende del contexto de uso, pero si se
trata de trabajar con grandes volúmenes de datos numéricos,
como registros en bases de datos o información para
visualización en tiempo real, optaría por el algoritmo de
ordenación Radix Sort debido a su alta eficiencia en entornos
paralelos y su naturaleza no comparativa que lo hace ideal para
claves enteras de longitud fija.

Para la búsqueda, elegiría el método de Hashing, ya que permite

acceder a los datos en tiempo constante promedio y es
especialmente útil en escenarios donde la velocidad es
prioritaria, como en sistemas de recuperación de información,
cachés o búsqueda de vecinos más cercanos. Además, la
variante semisupervisada permite mantener relaciones
semánticas en conjuntos de datos complejos, como imágenes o
datos multivariados.

V.CONCLUSIONES
➢ En muchas aplicaciones, antes de buscar eficientemente
un dato, es necesario ordenar la estructura. Esta relación
entre métodos resalta la importancia de dominar ambos
tipos de algoritmos para optimizar soluciones
computacionales.

➢ Más allá de los algoritmos clásicos, las nuevas

aproximaciones como Hashing con aprendizaje
automático permiten búsquedas rápidas y precisas en
entornos complejos como bases de datos de imágenes,
donde la similitud semántica es más relevante que la
coincidencia exacta.

VI.REFERENCIAS
[1] R. Purnomo and T. D. Putra, "Theoretical Analysis of Standard
Selection Sort Algorithm," Sinkron: Jurnal dan Penelitian Teknik
Informatika, vol. 7, no. 2, pp. 666–668, Apr. 2023
[2] S. Paira, S. Chandra, and S. S. Alam, "Enhanced Merge Sort - A New
Approach to the Merging Process," Procedia Computer Science, vol.
93, pp. 982–987, 2016.
[3] L. Ha, J. Krüger, and C. Silva, "Fast parallel sorting for visualization on
GPU," Computer Graphics Forum, vol. 28, no. 3, pp. 1121–1130, 2009.
[4] N. Arora, G. Bhasin, and N. Sharma, "Optimized linear search
algorithm using two-way search," International Journal of Computer
Applications, vol. 95, no. 25, pp. 32–35, Jun. 2014.
[5] N. Arora, G. Bhasin, and N. Sharma, "Optimized Binary Search and
Interpolation Search Algorithm," International Journal of Computer
Applications, vol. 95, no. 25, pp. 28–31, Jun. 2014.
[6] J. Wang, S. Kumar, and S.-F. Chang, "Semi-supervised hashing for
scalable image retrieval," in Proceedings of the IEEE Conference on
Computer Vision and Pattern Recognition (CVPR), 2010, pp. 3424–
3431.