Algoritmos de búsqueda y ordenamiento

Algoritmos de búsqueda y ordenamiento

Algoritmos de Ordenamiento

Algoritmos de búsqueda

Ordenamiento por selección (Selection sort)

Búsqueda lineal

Ordenamiento por inserción (Insertion sort)

Búsqueda lineal mejorada (Better linear search)

Ordenamiento por fusión (Merge sort)

Búsqueda lineal con centinela (Sentinel linear search)

Ordenamiento rápido (Quicksort)

Búsqueda binaria

Búsqueda lineal

Algoritmo BÚSQUEDA_LINEAL(A, n, x) Entradas: - A: un arreglo. - n: el número de elementos en A para buscar. - x: el valor que se está buscando. Salida: Ya sea un índice i para el cual A[i] sea igual a x, o el valor especial NO-ENCONTRADO, que podría ser cualquier índice no válido en el arreglo, como 0 o cualquier entero negativo. Establecer “answer” en NO-ENCONTRADO. Para cada índice i, yendo de 1 a n, en orden: A. Si A[i]=x, entonces establecer “answer” en el valor de i. 3. Devolver el valor de “answer” como salida.

linear-search

Encuentra más información en:

Búsqueda lineal mejorada

Algoritmo BÚSQUEDA_LINEAL_MEJORADA(A, n, x) Entradas: - A: un arreglo. - n: el número de elementos en A para buscar. - x: el valor que se está buscando. Salida: Ya sea un índice i para el cual A[i] sea igual a x, o el valor especial NO-ENCONTRADO, que podría ser cualquier índice no válido en el arreglo, como 0 o cualquier entero negativo. Para i=1 a n: A. Si A[i]=x, entonces regresa el valor de i como salida. Devolver NO ENCONTRADO como salida.

linear-search

Encuentra más información en:

Búsqueda lineal con centinela

Algoritmo BÚSQUEDA_LINEAL_CENTINELA (A, n, x) Entradas: - A: un arreglo. - n: el número de elementos en A para buscar. - x: el valor que se está buscando. Salida: Ya sea un índice i para el cual A[i] sea igual a x, o el valor especial NO-ENCONTRADO, que podría ser cualquier índice no válido en el arreglo, como 0 o cualquier entero negativo. Guarda A[n] en "last" y luego coloca x en A[n]. Establece i en 1. Mientras A[i] no sea igual a x, realiza lo siguiente: A. Incrementa i. Restaura A[n] desde "last". Si i < n o A[n]=x, entonces devuelve el valor de i como salida. De lo contrario, devuelve NO-ENCONTRADO como salida.

linear-search

Encuentra más información en:

Búsqueda binaria

Algoritmo BÚSQUEDA_BINARIA (A, n, x) Entradas: - A: un arreglo. - n: el número de elementos en A para buscar. - x: el valor que se está buscando. Salida: Ya sea un índice i para el cual A[i] sea igual a x, o el valor especial NO-ENCONTRADO, que podría ser cualquier índice no válido en el arreglo, como 0 o cualquier entero negativo. Establece p en 1 y r en n. Mientras p no sea mayor que r, realiza lo siguiente: A. Establece q en ⌊(p + r)/2⌋. B. Si A[q]=x, entonces devuelve q. C. En caso contrario (A[q] no es igual a x), si A[q]>x, entonces establece r en q - 1. D. En caso contrario (A[q]<x), establece p en q + 1. Devuelve NO-ENCONTRADO.

linear-search

Encuentra más información en:

Ordenamiento por selección

(Selection Sort)

Algoritmo ORDENAMIENTO_POR_SELECCIÓN (A, n) Entradas: - A: un arreglo. - n: el número de elementos en A para ordenar. Salida: Los elementos de A están ordenados de forma no decreciente. Para i=1 hasta n - 1: A. Establecer “smallest” al índice del elemento más pequeño en el subarreglo A[i …n]. B. Intercambiar A[i] con A[smallest].

linear-search

Encuentra más información en:

Ordenamiento por inserción

(Insertion Sort)

Algoritmo ORDENAMIENTO_POR_INCERSIÓN (A, n) Entradas: - A: un arreglo. - n: el número de elementos en A para ordenar. Salida: Los elementos de A están ordenados de forma no decreciente. Para i =2 hasta n - 1: A. Establecer “key” como A[i], y establecer j en i - 1. B. Mientras j > 0 y A[j] > key, realiza lo siguiente: i. Establecer A[j + 1] en A[j]. ii. Decrementar j (es decir, establecer j en j - 1). C. Establecer A[j + 1] en “key”.

linear-search

Encuentra más información en:

Ordenamiento por fusión

(Merge Sort)

Este método asume que podemos llamar a un procedimiento FUSIONAR(A, p, q, r) para fusionar los subarreglos ordenados A[p … q] y A[q+1 … r], en el único subarreglo ordenado A[p … r].

Algoritmo ORDENAMIENTO_POR_FUSIÓN (A, p, r) Entradas: - A: un arreglo. - p, r: para los índices de inicio y fin de un subarreglo de A. Resultado: Los elementos del subarreglo A[p … r] están ordenados en orden no decreciente. Si p ≥ r, entonces el subarreglo A[p … r] tiene a lo sumo un elemento, y por lo tanto ya está ordenado. Solo regresa sin hacer nada. De lo contrario, realiza lo siguiente: A. Establece q como la parte entera de (p + r)/2. B. Llama recursivamente a ORDENAMIENTO_POR_FUSION (A, p, q). C. Llama recursivamente a ORDENAMIENTO_POR_FUSION (A, q+1, r). D. Llama a FUSIONAR (A, p, q, r).

linear-search

Encuentra más información en:

Ordenamiento rápido

(Quicksort)

Este método asume que podemos llamar a un procedimiento PARTICION(A, p, r) que particiona el subarreglo A[p … r], devolviendo el índice q donde ha colocado el pivote.

Algoritmo ORDENAMIENTO_RÁPIDO (A, p, r) Entradas: - A: un arreglo. - p, r: para los índices de inicio y fin de un subarreglo de A. Resultado: Los elementos del subarreglo A[p … r] están ordenados en orden no decreciente. Si p ≥ r, entonces solo regresa sin hacer nada. De lo contrario, realiza lo siguiente: A. Llama a PARTICION (A, p, r), y establece q en su resultado. C. Llama recursivamente a ORDENAMIENTO_RAPIDO (A, p, q-1). D. Llama a ORDENAMIENTO_RAPIDO (A, q+1, r).

linear-search

Encuentra más información en:

Referencias:

Thomas H. Cormen. (2013). Algorithms Unlocked. The MIT Press.