¿Qué es un Algoritmo de Grafos?

Los algoritmos de grafos son un conjunto de instrucciones que recorren (visitan los nodos de) un grafo.

Algunos algoritmos son usados para hallar un nodo específico o el camino entre dos nodos dados.

¿Por qué son Importantes los Algoritmos de Grafos?

Los grafos son estructuras de datos muy útiles que se usan para modelar varios problemas. Estos algoritmos tienen aplicaciones directas en sitios de redes sociales, modelado de máquinas de estado y más.

Algunos Algoritmos de Grafos Comunes

Algunos de los algoritmos de grafos más comunes son:

• Búsqueda en Amplitud o Anchura (Breadth First Search, BFS)
• Búsqueda en Profundidad (Depth First Search, DFS)
• Dijkstra
• Algoritmo de Floyd-Warshall

Algoritmo de Bellman Ford

El algoritmo de Bellman Ford es un algoritmo de búsqueda del camino más corto para grafos que puede tener pesos negativos. El algoritmo de Bellman Ford es también ideal para detectar ciclos de pesos negativos, ya que el algoritmo converge hacia una solución óptima en O(V*E) pasos. Si la resultante no es óptima, entonces el grafo contiene un ciclo de pesos negativos.

Aquí está una implementación en Python:

infinito = 1e10

def bellman_ford(grafo, inicio, fin):
    num_vertices = grafo.get_num_vertices()
    aristas = grafo.get_edges()

    distancia = [infinito para vértice en range(num_vertices)]
    previo = [ninguno para vértice en range(num_vertices)]

    distancia[inicio] = 0
    for i range(fin+1):
        for (u, v) in aristas:
            if distancia[v] > distancia[u] + grafo.get_weight(u, v):
                distancia[v] = distancia[u] + grafo.get_weight(u, v)
                previo[v] = u

    for (u,v) in aristas:
        if distancia[v] > distancia[u] + grafo.get_weight(u, v):
            raise ErrorCicloPesoNegativo()
    return distancia, previo
# 'distancia' es la distancia desde el inicio hasta ese nodo en el camino más corto, útil para imprimir la distancia más corta.
# Previo es un arreglo que muestra el nodo que es anterior al actual, útil para imprimir el camino.

Búsqueda en Profundidad (Depth First Search, DFS)

La Búsqueda en Profundidad es uno de los algoritmos de grafos más sencillos. Recorre el grafo revisando primero el nodo actual y moviéndose después a uno de sus sucesores para repetir el proceso. Si el nodo actual no tiene sucesor a revisar, regresamos a su predecesor y el proceso continúa (moviéndose a otro sucesor). Si la solución es encontrada, la búsqueda termina.

Visualización

Implementación (C++14)

#include <iostream> 
#include <vector> 
#include <queue>  
#include <algorithm>
using namespace std; 
 
class Grafo{ 
   int v;    // número de vértices 
 
   // puntero a un vector que contiene listas de adyacencia
   vector < int > *adj;
public: 
   Grafo(int v);  // Constructor 
 
   // función para añadir una arista al grafo
   void agregar_arista(int v, int w);  
 
   // imprime el recorrido dfs a partir de una fuente `s` dada
   void dfs();
   void dfs_util(int s, vector < bool> &visitado);   
}; 
 
Grafo::Grafo(int v){ 
   this -> v = v; 
   adj = new vector < int >[v]; 
} 
 
void Grafo::agregar_arista(int u, int v){ 
   adj[u].push_back(v); // agregar v a la lista de u
   adj[v].push_back(v); // agregar u a la lista de v (¡elimina esta declaración si el grafo es dirigido!)
} 
void Grafo::dfs(){
   // vector visitado - para llevar registro de los nodos visitados durante la búsqueda en profundidad)
   vector < bool > visitado(v, false);  // marcar todos los nodos/vértices como no visitados
   for(int i = 0; i < v; i++)
       if(!visitado[i])
           dfs_util(i, visitado);
} 
// ¡observa el uso de la llamada por referencia aquí!
void Grafo::dfs_util(int s, vector < bool > &visitado){ 
   // marcar el nodo/vértice actual como visitado
   visitado[s] = true;
    // enviarlo a la salida estándar(pantalla)
   cout << s << " ";
   
   // ¡recorrer su lista de adyacencia y llamar recursivamente a dfs_util para todos sus vecinos! 
   // (¡solo si el vecino aún no ha sido visitado!)
   for(vector < int > :: iterator itr = adj[s].begin(); itr != adj[s].end(); itr++)
       if(!visitado[*itr])
           dfs_util(*itr, visitado); 
} 
 
int main() 
{ 
   // crear un grafo usando la clase Grafo que definimos anteriormente
   Grafo g(4); 
   g.agregar_arista(0, 1); 
   g.agregar_arista(0, 2); 
   g.agregar_arista(1, 2); 
   g.agregar_arista(2, 0); 
   g.agregar_arista(2, 3); 
   g.agregar_arista(3, 3); 
 
   cout << "A continuación el recorrido de la búsqueda en profundidad del grafo proporcionado"
        << "(a partir del vértice 0): "; 
   g.dfs(); 
   // la salida sería: 0 1 2 3
   return 0; 
} 

Evaluación

Complejidad del Espacio: O(n)

Complejidad del Tiempo en el Peor de los Casos: O(n) La Búsqueda en Profundidad es completa en un conjunto finito de nodos. Funciona mejor en árboles poco profundos.

Implementación de DFS en C++

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct Grafo{
	int v;
	bool **adj;
	public:
		Grafo(int conteov);
		void agregarArista(int u,int v);
		void borrarArista(int u,int v);
		vector<int> DFS(int s);
		void DFSUtil(int s,vector<int> &dfs,vector<bool> &visitado);
};
Grafo::Grafo(int conteov){
	this->v = conteov;
	this->adj=new bool*[conteov];
	for(int i=0;i<conteov;i++)
		this->adj[i]=new bool[conteov];
	for(int i=0;i<conteov;i++)
		for(int j=0;j<conteov;j++)
			adj[i][j]=false;
}

void Grafo::agregarArista(int u,int w){
	this->adj[u][w]=true;
	this->adj[w][u]=true;
}

void Grafo::borrarArista(int u,int w){
	this->adj[u][w]=false;
	this->adj[w][u]=false;
}

void Grafo::DFSUtil(int s, vector<int> &dfs, vector<bool> &visitado){
	visitado[s]=true;
	dfs.push_back(s);
	for(int i=0;i<this->v;i++){
		if(this->adj[s][i]==true && visitado[i]==false)
			DFSUtil(i,dfs,visitado);
	}
}

vector<int> Grafo::DFS(int s){
	vector<bool> visitado(this->v);
	vector<int> dfs;
	DFSUtil(s,dfs,visitado);
	return dfs;
}

Algoritmo de Floyd Warshall

El algoritmo de Floyd Warshall es un gran algoritmo para encontrar la distancia más corta entre todos los vértices del grafo. Tiene un algoritmo muy conciso y complejidad del tiempo O(V^3) (donde V es el número de vértices). Puede ser usado con pesos negativos, aunque los ciclos de pesos negativos no deben estar presentes en el grafo.

Evaluación

Complejidad del Espacio: O(V^2)

Complejidad del Tiempo en el Peor de los Casos: O(V^3)

Implementación en Python

# Un valor grande como infinito
inf = 1e10 

def floyd_warshall(pesos):
    V = len(pesos)
    matriz_distancia = pesos
    for k in range(V):
        siguiente_matriz_distancia = [list(row) for row in matriz_distancia] # hacer una copia de matriz de distancia
        for i in range(V):
            for j in range(V):
                # Elegir si el vértice k puede funcionar como un camino con menor distancia
                siguiente_matriz_distancia[i][j] = min(matriz_distancia[i][j], matriz_distancia[i][k] + matriz_distancia[k][j])
        matriz_distancia = siguiente_matriz_distancia # actualizar
    return matriz_distancia

# Un grafo representado como matriz de adyacencia
grafo = [
    [0, inf, inf, -3],
    [inf, 0, inf, 8],
    [inf, 4, 0, -2],
    [5, inf, 3, 0]
]

print(floyd_warshall(grafo))

Búsqueda en Amplitud o Anchura (Breadth First Search, BFS)

Búsqueda en Amplitud o Anchura es uno de los algoritmos de grafos más sencillo. Recorre el grafo al primero comprobar el nodo actual y luego expandirlo al agregar sus sucesores al siguiente nivel. El proceso se repite para todos los nodos del nivel actual  antes de moverse al siguiente. Si se encuentra la solución, la búsqueda termina.

Visualización

Evaluación

Complejidad del Espacio: O(n)

Complejidad del Tiempo en el Peor de los Casos: O(n)

La Búsqueda en Amplitud o Anchura es completa en un conjunto finito de nodos y es óptima si el costo de moverse de un nodo a otro es constante.

Código C++ para la implementación de BFS

// Programa para imprimir el recorrido BFS desde un 
// vértice origen dado. BFS(int s) recorre los vértices  
// alcanzables desde s. 
#include<iostream> 
#include <list> 
  
using namespace std; 
  
// Esta clase representa un grafo dirigido
// utilizando la representación de listas de adyacencias 
class Grafo 
{ 
    int V;    // No. de vértices 
  
    // Puntero a un arreglo que contiene listas de adyacencia
    list<int> *adj;    
public: 
    Grafo(int V);  // Constructor 
  
    // función para agregar una arista al grafo
    void agregarArista(int v, int w);  
  
    // imprime el recorrido de BFS desde una fuente s dada
    void BFS(int s);   
}; 
  
Grafo::Grafo(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Grafo::agregarArista(int v, int w) 
{ 
    adj[v].push_back(w); // Agregar w a la lista de v.
} 
  
void Grafo::BFS(int s) 
{ 
    // Marcar todos los vértices como no visitados
    bool *visitado = new bool[V]; 
    for(int i = 0; i < V; i++) 
        visitado[i] = false; 
  
    // Crear una cola para BFS 
    list<int> cola; 
  
    // Marcar el nodo actual como visitado y ponerlo en cola
    visitado[s] = true; 
    cola.push_back(s); 
  
    // 'i' será usado para obtener todos los vértices
    // adyacentes de un vértice 
    list<int>::iterator i; 
  
    while(!cola.empty()) 
    { 
        // Sacar de la cola un vértice e imprimirlo
        s = cola.front(); 
        cout << s << " "; 
        cola.pop_front(); 
  
        // Obtener todos los vértices adyacentes del
        // vértice s sacado de la cola. Si un adyacente
        // no ha sido visitado, entonces marcarlo como 
        // visitado y ponerlo en la cola
        for (i = adj[s].begin(); i != adj[s].end(); ++i) 
        { 
            if (!visitado[*i]) 
            { 
                visitado[*i] = true; 
                cola.push_back(*i); 
            } 
        } 
    } 
} 
  
// Programa controlador para probar métodos de la clase grafo
int main() 
{ 
    // Crear un grafo como el del diagrama anterior
    Grafo g(4); 
    g.agregarArista(0, 1); 
    g.agregarArista(0, 2); 
    g.agregarArista(1, 2); 
    g.agregarArista(2, 0); 
    g.agregarArista(2, 3); 
    g.agregarArista(3, 3); 
  
    cout << "A continuación se muestra el recorrido en amplitud o anchura "
         << "(empezando desde el vértice 2) \n"; 
    g.BFS(2); 
  
    return 0; 
}

Algoritmo de Dijkstra

El Algoritmo de Dijkstra es un algoritmo de grafo presentado por E. W. Dijkstra. Encuentra el camino más corto de origen único en un grafo con aristas no negativas. (¿Por qué?)

Creamos dos arreglos: visitado y distancia, que registran si un vértice es visitado y cuál es la mínima distancia desde el vértice origen, respectivamente. Inicialmente, el arreglo visitado se asigna como falso y distancia como infinito.

Partimos del vértice origen. Dejemos que el vértice actual sea u y sus vértices adyacentes sean v. Ahora, por cada v que es adyacente a u, la distancia se actualiza si no ha sido visitado antes y la distancia desde u es menor que su distancia actual. Luego seleccionamos el siguiente vértice con la menor distancia y que no haya sido visitado.

La Cola de Prioridad se usa a menudo para cumplir este último requerimiento en el menor tiempo posible. Abajo se ve una implementación de la misma idea usando la cola de prioridad en Java.

import java.util.*;
public class Dijkstra {
    class Grafo {
	LinkedList<Pair<Integer>> adj[];
	int n; // Número de vertices.
	Grafo(int n) {
	    this.n = n;
	    adj = new LinkedList[n];
	    for(int i = 0;i<n;i++) adj[i] = new LinkedList<>();
	}
	// agregar una arista dirigida entre los vértices a y b con el costo como peso
	public void agregarAristaDirigida(int a, int b, int costo) {
	    adj[a].add(new Pair(b, costo));
	}
	public void agregarAristaNoDirigida(int a, int b, int costo) {
	    agregarAristaDirigida(a, b, costo);
	    agregarAristaDirigida(b, a, costo);
	}
    }
    class Pair<E> {
	E first;
	E second;
	Pair(E f, E s) {
	    first = f;
	    second = s;
	}
    }

    // Comparador para ordenar Pares en la Cola de Prioridad
    class ComparadorPar implements Comparator<Pair<Integer>> {
	public int comparar(Pair<Integer> a, Pair<Integer> b) {
	    return a.second - b.second;
	}
    }

    // Calcular el camino más corto para cada vértice del origen y devuelve la distancia
    public int[] dijkstra(Grafo g, int src) {
	int distancia[] = new int[g.n]; // la distancia más corta de cada vértice desde src
	boolean visitado[] = new boolean[g.n]; // el vértice es visitado o no
	Arrays.fill(distancia, Integer.MAX_VALUE);
	Arrays.fill(visitado, false);
	PriorityQueue<Pair<Integer>> pq = new PriorityQueue<>(100, new ComparadorPar());
        pq.add(new Pair<Integer>(src, 0));
	distancia[src] = 0;
	while(!pq.isEmpty()) {
	    Pair<Integer> x = pq.remove(); // Extraer el vértice con la distancia más corta desde src
	    int u = x.first;
	    visitado[u] = true;
	    Iterator<Pair<Integer>> iter = g.adj[u].listIterator();
	    // Iterar sobre los vecinos de u y actualizar sus distancias
	    while(iter.hasNext()) {
		Pair<Integer> y = iter.next();
		int v = y.first;
		int peso = y.second;
		// Comprobar si el vértice v no es visitado
		// Si el nuevo camino a través de u ofrece menos costo, entonces actualizar el arreglo de distancia y agregarlo a cp
		if(!visitado[v] && distancia[u]+peso<distancia[v]) {
		    distancia[v] = distancia[u]+peso;
		    pq.add(new Pair(v, distancia[v]));
		}
	    }
	}
	return distancia;
    }

    public static void main(String args[]) {
	Dijkstra d = new Dijkstra();
	Dijkstra.Grafo g = d.new Grafo(4);
	g.agregarAristaNoDirigida(0, 1, 2);
	g.agregarAristaNoDirigida(1, 2, 1);
	g.agregarAristaNoDirigida(0, 3, 6);
	g.agregarAristaNoDirigida(2, 3, 1);
	g.agregarAristaNoDirigida(1, 3, 3);

	int dist[] = d.dijkstra(g, 0);
	System.out.println(Arrays.toString(dist));
    }
}

Algoritmo de Ford  Fulkerson

El algoritmo de Ford Fulkerson resuelve el problema de grafo de flujo máximo. Encuentra la mejor organización del flujo mediante las aristas de grafos, de tal modo que obtienes el flujo máximo de salida en el otro extremo. La fuente tiene una tasa específica de entrada y cada arista tiene un peso asociado que es la sustancia máxima que puede pasar a través de esa arista.

Al algoritmo Ford Fulkerson también se le conoce como algoritmo Edmund-Karp, ya que fue provisto en especificación completa por Jack Edmonds y Richard Karp.

Trabaja creando caminos de aumento, es decir, caminos desde el origen hasta el sumidero que tienen flujo no cero. Pasamos el flujo a través de los caminos y actualizamos los límites. Esto puede llevar a una situación donde no tenemos más movimientos. Es aquí donde la habilidad 'deshacer' de este algoritmo juega un papel importante. En caso de quedarse atorado, disminuimos el flujo y abrimos la arista para pasar nuestra sustancia actual.

Pasos

1. Establecer flujo cero para todas las aristas.
2. Mientras haya un camino del origen al hundimiento hacer,
3. Hallar el peso mínimo en el camino, que sea el límite.
4. Para todas las aristas (u, v) en el camino hacer,
   1. Agregar límite al flujo de u a v. (Para el movimiento actual)
   2. Restar límite  al flujo de v a u. (Para deshacer en un movimiento posterior)

Evaluación

Complejidad del tiempo: O(V*E^2)

Implementación en Python

# Número grande como infinito
inf = 1e10

def flujo_maximo(grafo, fuente, destino):
  flujo_maximo = 0
  padre = bfs(grafo, fuente, destino)
  while camino:
    limite = inf
    v = destino
    while v != fuente:
        u = padre[s]
        flujo_camino = min(limite, grafo[u][v])
        v = padre[v]
    flujo_maximo += flujo_camino

    v = destino
    while v != fuente:
        u = padre[v]
        grafo[u][v] -= flujo_camino
        grafo[v][u] += flujo_camino
        v = padre[v]

    camino = bfs(grafo, fuente, destino)
  return flujo_maximo

¿Qué es un algoritmo de ordenación?

Los algoritmos de ordenación son un conjunto de instrucciones que toman un arreglo o lista como entrada y organizan los elementos en un orden particular.

Las ordenaciones suelen ser numéricas o una forma de orden alfabético (o lexicográfico), y pueden ser en orden ascendente (AZ, 0-9) o descendente (ZA, 9-0).

Por qué los algoritmos de ordenación son importantes

Dado que a menudo pueden reducir la complejidad de un problema, los algoritmos de ordenación son muy importantes en informática. Estos algoritmos tienen aplicaciones directas en algoritmos de búsqueda, algoritmos de bases de datos, métodos divide y vencerás, algoritmos de estructura de datos y muchos más.

Compensaciones de los algoritmos de ordenación

Al elegir un algoritmo de ordenación, se deben hacer algunas preguntas: ¿Cuán grande es la colección que se ordena? ¿Cuánta memoria hay disponible? ¿La colección necesita crecer?

Las respuestas a estas preguntas pueden determinar qué algoritmo funcionará mejor para cada situación. Algunos algoritmos como la ordenación por combinación pueden necesitar mucho espacio o memoria para ejecutarse, mientras que la ordenación por inserción no siempre es la más rápida, pero no requiere muchos recursos para ejecutarse.

Debes determinar cuáles son tus requisitos y considerar las limitaciones de tu sistema antes de decidir qué algoritmo de ordenación usar.

Algunos algoritmos de ordenación comunes

Algunos de los algoritmos de ordenación más comunes son:

• Selection sort (selección)
• Bubble sort (burbuja)
• Insertion sort (inserción)
• Merge sort (combinación)
• Quick sort (rápida)
• Heap sort (montón)
• Counting sort (conteo)
• Radix sort (raíz)
• Bucket sort (cubo)

Pero antes de entrar en cada uno de estos, aprendamos un poco más sobre qué clasifica a un algoritmo de ordenación.

Clasificación de un algoritmo de ordenación

Los algoritmos de ordenación se pueden clasificar en función de los siguientes parámetros:

1. La cantidad de intercambios o inversiones requeridas: Esta es la cantidad de veces que el algoritmo intercambia elementos para ordenar la entrada. La ordenación por selección requiere el número mínimo de intercambios.
2. El número de comparaciones: Este es el número de veces que el algoritmo compara elementos para ordenar la entrada. Usando la notación Big-O , los ejemplos de algoritmos de ordenación enumerados anteriormente requieren al menos O(nlogn)comparaciones en el mejor de los casos y O(n^2) comparaciones en el peor de los casos para la mayoría de los resultados.
3. Ya sea que usen recursividad o no: Algunos algoritmos de ordenación, como la ordenación rápida, usan técnicas recursivas para ordenar la entrada. Otros algoritmos de ordenación, como la ordenación por selección o la ordenación por inserción, utilizan técnicas no recursivas. Por último, algunos algoritmos de ordenación, como la ordenación por fusión, utilizan técnicas tanto recursivas como no recursivas para ordenar la entrada.
4. Ya sean estables o inestables: Los algoritmos de ordenación estables mantienen el orden relativo de los elementos con valores iguales o claves. Los algoritmos de ordenación inestables no mantienen el orden relativo de los elementos con valores/claves iguales.
   
   Por ejemplo, imagina que tienes el arreglo de entrada [1, 2, 3, 2, 4]. Y para ayudar a diferenciar entre los dos valores iguales, 2 actualicémoslos a 2a y 2b, creando el arreglo de entrada [1, 2a, 3, 2b, 4].
   
   Los algoritmos de ordenación estables mantendrán el orden de 2a y 2b, lo que significa que el arreglo de salida será [1, 2a, 2b, 3, 4]. Los algoritmos de ordenación inestables no mantienen el orden de los valores iguales y el arreglo de salida puede ser [1, 2b, 2a, 3, 4].
   
   La ordenación por inserción, la ordenación por fusión y la ordenación por burbuja son estables. La ordenación en montón y la ordenación rápida son inestables.
5. La cantidad de espacio adicional requerido: Algunos algoritmos de ordenación pueden ordenar una lista sin crear una lista completamente nueva. Estos se conocen como algoritmos de ordenación en el lugar y requieren un O(1) espacio adicional constante para la ordenación. Mientras tanto, los algoritmos de ordenación fuera de lugar crean una nueva lista durante la ordenación.
   
   La ordenación por inserción y la ordenación rápida son algoritmos de ordenación en el lugar, ya que los elementos se mueven alrededor de un punto de pivote y no usan un arreglo separado.
   
   Merge sort es un ejemplo de un algoritmo de ordenación fuera del lugar, ya que el tamaño de la entrada debe asignarse de antemano para almacenar la salida durante el proceso de ordenación, lo que requiere memoria adicional.

Bucket Sort (Ordenación de cubo)

La ordenación de cubos es un algoritmo de ordenación por comparación que opera en elementos dividiéndolos en diferentes cubos y luego ordenando estos cubos individualmente. Cada depósito se ordena individualmente utilizando un algoritmo de ordenación independiente, como la ordenación por inserción, o aplicando el algoritmo de ordenación de cubos de forma recursiva.

La ordenación de cubos es principalmente útil cuando la entrada se distribuye uniformemente en un rango. Por ejemplo, imagina que tienes una gran variedad de enteros de punto flotante distribuidos uniformemente entre un límite superior e inferior.

Puedes usar otro algoritmo de ordenación, como la ordenación por combinación, la ordenación por montones o la ordenación rápida. Sin embargo, esos algoritmos garantizan una complejidad de tiempo en el mejor de los casos de O(nlogn).

Usando la ordenación de cubos, la ordenación del mismo arreglo se puede completar a O(n)tiempo.

Pseudocódigo para ordenación de cubo:

void bucketSort(float[] a,int n)

{

    for(each floating integer 'x' in n)

    {
        insert x into bucket[n*x]; 
    }

    for(each bucket)

    {
        sort(bucket);
    }

}

Counting Sort (Ordenación de conteo)

El algoritmo de ordenación por conteo funciona creando primero una lista de los conteos u ocurrencias de cada valor único en la lista. Luego crea una lista ordenada final basada en la lista de conteos.

Una cosa importante que debes recordar es que la ordenación por conteo solo se puede usar cuando conoces de antemano el rango de valores posibles en la entrada.

Ejemplo:

Digamos que tienes una lista de números enteros del 0 al 5:
 
input = [2, 5, 3, 1, 4, 2]

Primero, debes crear una lista de recuentos para cada valor único en
la lista `entrada`. Como sabes que el rango de la `entrada` es de 0 a
5, puedes crear una lista con cinco marcadores de posición para los valores del 0 al 5, respectivamente:

count = [0, 0, 0, 0, 0, 0]
  # val: 0  1  2  3  4  5

Luego, revisas la lista `input` e iteras el índice para cada valor en uno.

Por ejemplo, el primer valor en la lista `input` es 2, por lo que agrega uno
al valor en el segundo índice de la lista `count`, que representa
el valor 2:

count = [0, 0, 1, 0, 0, 0]
  # val: 0  1  2  3  4  5
       
El siguiente valor en la lista `input` es 5, por lo que agrega uno al valor en el último índice de la lista `count`, que representa el valor 5:

count = [0, 0, 1, 0, 0, 1]
  # val: 0  1  2  3  4  5

Continúa hasta que tengas el recuento total de cada valor en la `entrada`
lista:

count = [0, 1, 2, 1, 1, 1]
  # val: 0  1  2  3  4  5

Finalmente, dado que sabes cuántas veces cada valor en la lista `input`
aparece, puedes crear fácilmente una lista de `salida` ordenada. Bucle a través de la lista `recuento`, y para cada recuento, agrega el valor correspondiente (0 - 5) al arreglo `output` tantas veces.

Por ejemplo, no había 0 en la lista de 'entradas', pero había una aparición del valor 1, por lo que agrega ese valor al arreglo `output`
una vez:

output = [1]

Luego hubo dos apariciones del valor 2, por lo que las agrega a la
lista `output`:

output = [1, 2, 2]

Y así sucesivamente hasta que tengas la lista final ordenada de "salida" (output):

output = [1, 2, 2, 3, 4, 5]

Propiedades

• Complejidad de espacio:O(k)
• Rendimiento del mejor caso:O(n+k)
• Rendimiento del caso promedio:O(n+k)
• Rendimiento en el peor de los casos:O(n+k)
• Estable: Sí ( kes el rango de los elementos en el arreglo)

Implementación en JavaScript

let numbers = [1, 4, 1, 2, 7, 5, 2];
let count = [];
let output =[];
let i = 0;
let max = Math.max(...numbers);

// inicializa el contador
for (i = 0; i <= max; i++) {
  count[i] = 0;
}

// inicializa el arreglo de salida
for (i = 0; i < numbers.length; i++) {
  output[i] = 0;
}

for (i = 0; i < numbers.length; i++) {
  count[numbers[i]]++;
}

for (i = 1; i < count.length; i++) {
  count[i] += count[i-1];
}

for (i = numbers.length - 1; i >= 0; i--) { 
  output[--count[numbers[i]]] = numbers[i];
}

// arreglo ordenado de salida
for (i = 0; i < output.length; i++) {
  console.log(output[i]);
}

Implementación de C++

#include <iostream>

#include <vector>

void countSort(int upperBound, int lowerBound, std::vector < int > numbersToSort) 
// Límites inferior y superior de los números en el vector
{
  int i;
  int range = upperBound - lowerBound; // Crea un rango lo suficientemente grande para obtener todos los números entre el mínimo y el máximo
  std::vector < int > counts(range + 1); // Inicializar conteos del tamaño del rango
  std::fill(counts.begin(), counts.end(), 0); // Rellenar vector de ceros
  std::vector < int > storedNumbers(numbersToSort.size()); // Inicializar los números almacenados del mismo tamaño que el vector de entrada
  std::fill(storedNumbers.begin(), storedNumbers.end(), 0); // Rellenar vector de números almacenados de ceros
  for (i = 0; i < numbersToSort.size(); i++) {
    int index = numbersToSort[i] - lowerBound; // Por ejemplo, si 5 es el límite inferior y numberToSort[i] es 5, el índice será 0 y el
    counts[index] += 1; // recuento de 5 se almacenará en recuentos[0]
  }

  for (i = 1; i < counts.size(); i++) {
    counts[i] += counts[i - 1];
  }

  for (i = numbersToSort.size() - 1; i >= 0; i--) { // Copiar elementos de numbersToSort a storedNumbers según el conteo
    storedNumbers[--counts[numbersToSort[i] - lowerBound]] = numbersToSort[i];
  }

  for (i = 0; i < storedNumbers.size(); i++) {
    std::cout << storedNumbers[i];
    if (i != storedNumbers.size() - 1)
      std::cout << ", ";
  }
  std::cout << std::endl;
}

Implementación en Swift

func countingSort(_ array: [Int]) {
  // Crea un arreglo para almacenar el conteo de cada elemento
  let maxElement = array.max() ?? 0
  var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
  
  for element in array {
    countArray[element] += 1
  }
  
  for i in 1 ..< countArray.count {
    countArray[i] += countArray[i-1];
  }
  
  var sortedArray = [Int](repeating: 0, count: array.count)
  
  // copia elementos del arreglo a sortedArray de acuerdo con el conteo
  for i in (0 ..< array.count) .reversed() {
    countArray[array[i]] -= 1
    sortedArray[countArray[array[i]]] = array[i];
  }
  
  print(sortedArray)
}

Insertion Sort (Ordenación de inserción)

La ordenación por inserción es un algoritmo de ordenación simple para una pequeña cantidad de elementos.

Ejemplo:

En la ordenación por inserción, compara el elemento key con los elementos anteriores. Si los elementos anteriores son mayores que el elemento key, mueve el elemento anterior a la siguiente posición.

Comienza desde el índice 1 hasta el tamaño del arreglo de entrada.

[ 8 3 5 1 4 2 ]

Paso 1 :

      key = 3 //a partir del 1er índice.

      Aquí `key`(clave) se comparará con los elementos anteriores.

      En este caso, `key` se compara con 8. como 8 > 3, mueve el elemento 8
      a la siguiente posición e inserta `key` en la posición anterior.

      Result: [ 3 8 5 1 4 2 ]

Paso 2 :

      key = 5 //2º índice

      8 > 5 // mueve 8 al segundo índice e inserta 5 en el primer índice.

      Result: [ 3 5 8 1 4 2 ]

Paso 3 :

      //3er índice

      8 > 1     => [ 3 5 1 8 4 2 ]  

      5 > 1     => [ 3 1 5 8 4 2 ]

      3 > 1     => [ 1 3 5 8 4 2 ]

      Result: [ 1 3 5 8 4 2 ]

Paso 4 :

      key = 4 // 4º índice

      8 > 4   => [ 1 3 5 4 8 2 ]

      5 > 4   => [ 1 3 4 5 8 2 ]

      3 > 4   ≠>  stop

      Result: [ 1 3 4 5 8 2 ]

Paso 5 :

      key = 2 // 5º índice

      8 > 2   => [ 1 3 4 5 2 8 ]

      5 > 2   => [ 1 3 4 2 5 8 ]

      4 > 2   => [ 1 3 2 4 5 8 ]

      3 > 2   => [ 1 2 3 4 5 8 ]

      1 > 2   ≠> stop

      Result: [1 2 3 4 5 8]

El algoritmo que se muestra a continuación es una versión ligeramente optimizada para evitar cambiar el elemento key  en cada iteración. Aquí, el elemento  key   se intercambiará al final de la iteración (paso).

    InsertionSort(arr[])
      for j = 1 to arr.length
         key = arr[j]
         i = j - 1
         while i > 0 and arr[i] > key
            arr[i+1] = arr[i]
            i = i - 1
         arr[i+1] = key

Aquí hay una implementación detallada en JavaScript:

function insertion_sort(A) {
    var len = array_length(A);
    var i = 1;
    while (i < len) {
        var x = A[i];
        var j = i - 1;
        while (j >= 0 && A[j] > x) {
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j+1] = x;
        i = i + 1;
    }
}

A continuación se muestra una implementación rápida en Swift:

  var array = [8, 3, 5, 1, 4, 2]

  func insertionSort(array:inout Array<Int>) -> Array<Int>{
      for j in 0..<array.count {
          let key = array[j]
          var i = j-1

          while (i > 0 && array[i] > key){
              array[i+1] = array[i]
              i = i-1
          }
          array[i+1] = key
      }
      return array
  }

El ejemplo de Java se muestra a continuación:

public int[] insertionSort(int[] arr)
      for (j = 1; j < arr.length; j++) {
         int key = arr[j]
         int i = j - 1
         while (i > 0 and arr[i] > key) {
            arr[i+1] = arr[i]
            i -= 1
         }
         arr[i+1] = key
      }
      return arr;

Y en c...

void insertionSort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       j = i-1;
       while (j >= 0 && arr[j] > key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   } 
} 

Propiedades:

• Complejidad de espacio: O(1)
• Complejidad de tiempo: O(n), O(n* n), O(n* n) para los mejores, promedios y peores casos respectivamente.
• Mejor caso: El arreglo ya está ordenado
• Caso promedio: El arreglo se ordena aleatoriamente
• En el peor de los casos: El arreglo se ordena de forma inversa.
• Ordenación en el lugar: Sí
• Estable: Sí

Heapsort (Ordenación por montones)

Heapsort es un algoritmo de ordenación eficiente basado en el uso de montones máximos/mínimos. Un montón es una estructura de datos basada en un árbol que satisface la propiedad del montón, es decir, para un montón máximo, la clave de cualquier nodo es menor o igual que la clave de su padre (si tiene un padre).

Esta propiedad se puede aprovechar para acceder al elemento máximo en el montón en tiempo O (logn) usando el método maxHeapify. Realizamos esta operación n veces, cada vez que movemos el elemento máximo en el montón a la parte superior del montón y lo extraemos del montón y lo colocamos en un arreglo ordenado. Por lo tanto, después de n iteraciones, tendremos una versión ordenada del arreglo de entrada.

El algoritmo no es un algoritmo en el lugar y requeriría que se construyera primero una estructura de datos de montón. El algoritmo también es inestable, lo que significa que al comparar objetos con la misma clave, no se conservará el orden original.

Este algoritmo se ejecuta en tiempo O(nlogn) y espacio adicional O(1) [O(n) incluido el espacio requerido para almacenar los datos de entrada] ya que todas las operaciones se realizan completamente en el lugar.

La complejidad de tiempo del caso mejor, peor y promedio de Heapsort es O (nlogn). Aunque heapsort tiene una mejor complejidad en el peor de los casos que quicksort, una ordenación rápida bien implementada se ejecuta más rápido en la práctica. Este es un algoritmo basado en la comparación, por lo que se puede usar para conjuntos de datos no numéricos en la medida en que se pueda definir alguna relación (propiedad del montón) sobre los elementos.

Una implementación en Java es como se muestra a continuación:

import java.util.Arrays;
public class Heapsort {

	public static void main(String[] args) {
		//test array
        //arreglo de prueba
		Integer[] arr = {1, 4, 3, 2, 64, 3, 2, 4, 5, 5, 2, 12, 14, 5, 3, 0, -1};
		String[] strarr = {"hope you find this helpful!", "wef", "rg", "q2rq2r", "avs", "erhijer0g", "ewofij", "gwe", "q", "random"};
		arr = heapsort(arr);
		strarr = heapsort(strarr);
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(strarr));
	}
	
	//O(nlogn) TIME, O(1) SPACE, NOT STABLE
    //O(nlogn) TIEMPO, O(1) ESPACIO, NO ESTABLE
	public static <E extends Comparable<E>> E[] heapsort(E[] arr){
		int heaplength = arr.length;
		for(int i = arr.length/2; i>0;i--){
			arr = maxheapify(arr, i, heaplength);
		}
		
		for(int i=arr.length-1;i>=0;i--){
			E max = arr[0];
			arr[0] = arr[i];
			arr[i] = max;
			heaplength--;
			arr = maxheapify(arr, 1, heaplength);
		}
		
		return arr;
	}
	
	//Creates maxheap from array
//Crea maxheap a partir de un arreglo
	public static <E extends Comparable<E>> E[] maxheapify(E[] arr, Integer node, Integer heaplength){
		Integer left = node*2;
		Integer right = node*2+1;
		Integer largest = node;
		
		if(left.compareTo(heaplength) <=0 && arr[left-1].compareTo(arr[node-1]) >= 0){
			largest = left;
		}
		if(right.compareTo(heaplength) <= 0 && arr[right-1].compareTo(arr[largest-1]) >= 0){
			largest = right;
		}	
		if(largest != node){
			E temp = arr[node-1];
			arr[node-1] = arr[largest-1];
			arr[largest-1] = temp;
			maxheapify(arr, largest, heaplength);
		}
		return arr;
	}
}

Implementación en C++

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; 
    int l = 2*i + 1;  
    int r = 2*i + 2;
    if (l < n && arr[l] > arr[largest]) 
        largest = l;
    if (r < n && arr[r] > arr[largest]) 
        largest = r;
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
  
        
        heapify(arr, n, largest); 
    } 
} 
  
 
void heapSort(int arr[], int n) 
{ 
    
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
  
    
    for (int i=n-1; i>=0; i--) 
    { 

        swap(arr[0], arr[i]); 
  
        
        heapify(arr, i, 0); 
    } 
} 
void printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; ++i) 
        cout << arr[i] << " "; 
    cout << "\n"; 
} 
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Sorted array is \n"; 
    printArray(arr, n); 
}

Ordenación Radix

Requisito previo: Ordenar por conteo

QuickSort, MergeSort y HeapSort son algoritmos de ordenación basados ​​en comparaciones. CountSort no lo es. Tiene la complejidad de O(n+k), donde k es el elemento máximo del arreglo de entrada. Entonces, si k es O(n), CountSort se convierte en una ordenación lineal, que es mejor que los algoritmos de ordenación basados ​​en comparación que tienen una complejidad de tiempo O(nlogn).

La idea es extender el algoritmo CountSort para obtener una mejor complejidad de tiempo cuando k pasa a O(n2). Aquí viene la idea de Radix Sort.

El algoritmo:

Para cada dígito i donde i varía del dígito menos significativo al dígito más significativo de un número, ordena el arreglo de entrada utilizando el algoritmo de ordenación de acuerdo con el i-ésimo dígito. Usamos la ordenación por conteo porque es una ordenación estable.

Ejemplo: Supón que el arreglo de entrada es:

10, 21, 17, 34, 44, 11, 654, 123

Según el algoritmo, ordenaremos el arreglo de entrada según el dígito de uno (dígito menos significativo).

0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:

Entonces, el arreglo se convierte en 10, 21, 11, 123, 24, 44, 654, 17.

Ahora, ordenaremos según el dígito de las decenas:

0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:

Ahora, el arreglo se convierte en: 10, 11, 17, 21, 123, 34, 44, 654.

Finalmente, ordenamos según el dígito de las centenas (dígito más significativo):

0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:

El arreglo se convierte en: 10, 11, 17, 21, 34, 44, 123, 654 que está ordenado. Así es como funciona nuestro algoritmo.

Una implementación en C:

void countsort(int arr[],int n,int place){

        int i,freq[range]={0};         //el rango de números enteros es 10 ya que los dígitos van del 0 al 9

        int output[n];

        for(i=0;i<n;i++)
                freq[(arr[i]/place)%range]++;

        for(i=1;i<range;i++)
                freq[i]+=freq[i-1];
        
        for(i=n-1;i>=0;i--){
                output[freq[(arr[i]/place)%range]-1]=arr[i];
                freq[(arr[i]/place)%range]--;
        }
        
        for(i=0;i<n;i++)
                arr[i]=output[i];
}

void radixsort(ll arr[],int n,int maxx){            //maxx es el elemento máximo en el arreglo

        int mul=1;
        while(maxx){
                countsort(arr,n,mul);
                mul*=10;
                maxx/=10;
        }
}

Selection Sort (Ordenación de selección)

Selection Sort es uno de los algoritmos de ordenación más simples. Este algoritmo recibe su nombre de la forma en que itera a través del arreglo: Selecciona el elemento más pequeño actual y lo cambia de lugar.

Así es como funciona:

1. Encuentra el elemento más pequeño en el arreglo y lo intercambia con el primer elemento.
2. Encuentra el segundo elemento más pequeño y lo intercambia con el segundo elemento del arreglo.
3. Encuentra el tercer elemento más pequeño y lo intercambia con el tercer elemento del arreglo.
4. Repite el proceso de encontrar el siguiente elemento más pequeño y cambiarlo a la posición correcta hasta que se ordene todo el arreglo.

Pero, ¿cómo escribirías el código para encontrar el índice del segundo valor más pequeño en un arreglo?

Una manera fácil es notar que el valor más pequeño ya se ha cambiado al índice 0, por lo que el problema se reduce a encontrar el elemento más pequeño en el arreglo que comienza en el índice 1.

La ordenación por selección siempre toma el mismo número de comparaciones clave — N(N − 1)/2.

Implementación en C/C++

El siguiente programa en C++ contiene una implementación iterativa y recursiva del algoritmo de ordenación por selección. Ambas implementaciones se invocan en la función  main().

#include <iostream>
#include <string>
using namespace std;

template<typename T, size_t n>
void print_array(T const(&arr)[n]) {
    for (size_t i = 0; i < n; i++)
        std::cout << arr[i] << ' ';
    cout << "\n";
}

int minIndex(int a[], int i, int j) {
    if (i == j)
        return i;
    int k = minIndex(a, i + 1, j);
    return (a[i] < a[k]) ? i : k;
}

void recurSelectionSort(int a[], int n, int index = 0) {
    if (index == n)
        return;
    int k = minIndex(a, index, n - 1);
    if (k != index)
        swap(a[k], a[index]);
    recurSelectionSort(a, n, index + 1);
}

void iterSelectionSort(int a[], int n) {
    for (int i = 0; i < n; i++)
    {
        int min_index = i;
        int min_element = a[i];
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < min_element)
            {
                min_element = a[j];
                min_index = j;
            }
        }
        swap(a[i], a[min_index]);
    }
}

int main() {
    int recurArr[6] = { 100,35, 500, 9, 67, 20 };
    int iterArr[5] = { 25, 0, 500, 56, 98 };

    cout << "Recursive Selection Sort"  << "\n";
    print_array(recurArr); // 100 35 500 9 67 20
    recurSelectionSort(recurArr, 6);
    print_array(recurArr); // 9 20 35 67 100 500

    cout << "Iterative Selection Sort" << "\n";
    print_array(iterArr); // 25 0 500 56 98
    iterSelectionSort(iterArr, 5);
    print_array(iterArr); // 0 25 56 98 500
}

Implementación en JavaScript

function selection_sort(A) {
    var len = A.length;
    for (var i = 0; i < len - 1; i = i + 1) {
        var j_min = i;
        for (var j = i + 1; j < len; j = j + 1) {
            if (A[j] < A[j_min]) {
                j_min = j;
            } else {}
        }
        if (j_min !== i) {
            swap(A, i, j_min);
        } else {}
    }
}

function swap(A, x, y) {
    var temp = A[x];
    A[x] = A[y];
    A[y] = temp;
}

Implementación en Python

def seletion_sort(arr):
         if not arr:
         return arr
    for i in range(len(arr)):
         min_i = i
         for j in range(i + 1, len(arr)):
              if arr[j] < arr[min_i]:
                  min_i = j
         arr[i], arr[min_i] = arr[min_i], arr[i]

Implementación en Java

public void selectionsort(int array[])
{
    int n = array.length;            // método para encontrar la longitud del arreglo
    for (int i = 0; i < n-1; i++)
    {
        int index = i;
        int min = array[i];                  // tomando el elemento min como i-ésimo elemento del arreglo
        for (int j = i+1; j < n; j++)
        {
            if (array[j] < array[index])
            {
                index = j;
                min = array[j];
            }
        }
        int t = array[index];         //Intercambiar los lugares de los elementos
        array[index] = array[i];
        array[i] = t;
    }
}

Implementación en MATLAB

function [sorted] = selectionSort(unsorted)
    len = length(unsorted);
    for i = 1:1:len
        minInd = i;
        for j = i+1:1:len
           if unsorted(j) < unsorted(minInd) 
               minInd = j;
           end
        end
        unsorted([i minInd]) = unsorted([minInd i]);    
    end
    sorted = unsorted;
end

Propiedades

• Complejidad espacial:   O(n)
• Complejidad del tiempo:   O(n2)
• Ordenación en el lugar:   Sí
• Estable:   No

Bubble Sort (Ordenación de burbuja)

Al igual que las burbujas se elevan desde el fondo de un vaso, la ordenación de burbujas es un algoritmo simple que ordena una lista, lo que permite que los valores más bajos o más altos aparezcan en la parte superior. El algoritmo atraviesa una lista y compara valores adyacentes, intercambiandolos si no están en el orden correcto.

Con una complejidad en el peor de los casos de O(n^2), la ordenación de burbujas es muy lenta en comparación con otros algoritmos de ordenación como la ordenación rápida. La ventaja es que es uno de los algoritmos de ordenación más fáciles de entender y codificar desde cero.

Desde una perspectiva técnica, la ordenación por burbuja es razonable para ordenar arreglos de tamaño pequeño o especialmente cuando se ejecutan algoritmos de ordenación en ordenadores con recursos de memoria notablemente limitados.

Ejemplo:

Primer paso por la lista:

• Comenzando con [4, 2, 6, 3, 9], el algoritmo compara los dos primeros elementos del arreglo, 4 y 2. Los intercambia porque 2 < 4:[2, 4, 6, 3, 9]
• Compara los siguientes dos valores, 4 y 6. Como 4 < 6, estos ya están en orden, y el algoritmo continúa:[2, 4, 6, 3, 9]
• Los siguientes dos valores también se intercambian porque 3 < 6:[2, 4, 3, 6, 9]
• Los dos últimos valores, 6 y 9, ya están en orden, por lo que el algoritmo no los intercambia.

Second pass through the list:
Segundo paso por la lista:

• 2 < 4, por lo que no hay necesidad de intercambiar posiciones:[2, 4, 3, 6, 9]
• El algoritmo intercambia los siguientes dos valores porque 3 < 4:[2, 3, 4, 6, 9]
• Sin intercambio porque 4 < 6:[2, 3, 4, 6, 9]
• De nuevo, 6 < 9, por lo que no se produce intercambio:[2, 3, 4, 6, 9]

La lista ya está ordenada, pero el algoritmo de ordenación de burbujas no se da cuenta de esto. Más bien, necesita completar una pasada completa a través de la lista sin intercambiar ningún valor para saber que la lista está ordenada.

Tercer paso por la lista:

• [2, 3, 4, 6, 9] => [2, 3, 4, 6, 9]
• [2, 3, 4, 6, 9] => [2, 3, 4, 6, 9]
• [2, 3, 4, 6, 9] => [2, 3, 4, 6, 9]
• [2, 3, 4, 6, 9] => [2, 3, 4, 6, 9]

Claramente, la ordenación por burbujas está lejos de ser el algoritmo de ordenación más eficiente. Aún así, es simple entenderlo e implementarlo por ti mismo.

Propiedades

• Complejidad del espacio: O(1)
• Rendimiento en el mejor caso: O(n)
• Rendimiento promedio de casos: O(n*n)
• Rendimiento en el peor de los casos: O(n*n)
• Estable: Sí

Vídeo Explicación (en inglés)

Algoritmo de ordenación de burbujas

Ejemplo en JavaScript

let arr = [1, 4, 7, 45, 7,43, 44, 25, 6, 4, 6, 9],
    sorted = false;

while(!sorted) {
  sorted = true;
  for(var i=0; i < arr.length; i++) {
    if(arr[i] < arr[i-1]) {
      let temp = arr[i];
      arr[i] = arr[i-1];
      arr[i-1] = temp;
      sorted = false;
    }
  }
}

Ejemplo en Java

public class BubbleSort {
    static void sort(int[] arr) {
        int n = arr.length;
        int temp = 0;
         for(int i=0; i < n; i++){
                 for(int x=1; x < (n-i); x++){
                          if(arr[x-1] > arr[x]){
                                 temp = arr[x-1];
                                 arr[x-1] = arr[x];
                                 arr[x] = temp;
                         }

                 }
         }

    }
    public static void main(String[] args) {

		for(int i=0; i < 15; i++){
			int arr[i] = (int)(Math.random() * 100 + 1);
		}

                System.out.println("array before sorting\n");
                for(int i=0; i < arr.length; i++){
                        System.out.print(arr[i] + " ");
                }
                bubbleSort(arr);
                System.out.println("\n array after sorting\n");
                for(int i=0; i < arr.length; i++){
                        System.out.print(arr[i] + " ");
                }

        }
}

Ejemplo en C++

// Implementación recursiva
void bubblesort(int arr[], int n)
{
	if(n==1)	//Initial Case  
//Caso inicial
		return;
	bool swap_flag = false;
	for(int i=0;i<n-1;i++)	//Después de este paso, el elemento más grande se moverá a la ubicación deseada.
	{
		if(arr[i]>arr[i+1])
		{
			int temp=arr[i];
			arr[i]=arr[i+1];
			arr[i+1]=temp;
			swap_flag = true;
		}
	}
               
// SI no se intercambiaron dos elementos en el ciclo, luego regresa, ya que el arreglo está ordenado
	if(swap_flag == false)
		return;
	bubblesort(arr,n-1);	//Recursividad para el arreglo restante
}

Ejemplo en Swift

func bubbleSort(_ inputArray: [Int]) -> [Int] {
    guard inputArray.count > 1 else { return inputArray } 
    // asegúrandose de que nuestro arreglo de entrada tenga más de 1 elemento
    var numbers = inputArray // los argumentos de la función son constantes por defecto en Swift, así que hacemos una copia
    for i in 0..<(numbers.count - 1) {
        for j in 0..<(numbers.count - i - 1) {
            if numbers[j] > numbers[j + 1] {
                numbers.swapAt(j, j + 1)
            }
        }
    }
    return numbers // devuelve el arreglo ordenado
} 

Ejemplo en Python

def bubbleSort(arr): 
    n = len(arr) 
    for i in range(n):
        for j in range(0, n-i-1):
                if arr[j] > arr[j+1] : 
                        arr[j], arr[j+1] = arr[j+1], arr[j]
    print(arr)

Ejemplo en PHP

function bubble_sort($arr) {
    $size = count($arr)-1;
    for ($i=0; $i<$size; $i++) {
        for ($j=0; $j<$size-$i; $j++) {
            $k = $j+1;
            if ($arr[$k] < $arr[$j]) {
                // Intercambiar elementos en índices: $j, $k
                list($arr[$j], $arr[$k]) = array($arr[$k], $arr[$j]);
            }
        }
    }
    return $arr; // devuelve el arreglo ordenado
}

$arr = array(1,3,2,8,5,7,4,0);
print("Antes de ordenar");
print_r($arr);

$arr = bubble_sort($arr);
print("Después de ordenar usando ordenación por burbujas");
print_r($arr);

Ejemplo en C

#include <stdio.h>

int BubbleSort(int array[], int n);

int main(void) {
  int arr[] = {10, 2, 3, 1, 4, 5, 8, 9, 7, 6};
  BubbleSort(arr, 10);

  for (int i = 0; i < 10; i++) {
    printf("%d", arr[i]);
  }
  return 0;
}
int BubbleSort(int array[], n)
{
for (int i = 0 ; i < n - 1; i++)
  {
    for (int j = 0 ; j < n - i - 1; j++)     //n es la longitud del arreglo
    {
      if (array[j] > array[j+1])      // Para uso en orden decreciente
      {
        int swap   = array[j];
        array[j]   = array[j+1];
        array[j+1] = swap;
      }
    }
  }
}

Ordenación rápida

Quick sort es un eficiente algoritmo de ordenación divide y vencerás. La complejidad de tiempo del caso promedio de Quick Sort es O (nlog (n)) y la complejidad de tiempo del peor caso es O (n ^ 2) dependiendo de la selección del elemento pivote, que divide el arreglo actual en dos sub arreglos.

Por ejemplo, la complejidad de tiempo de Quick Sort es aproximadamente O(nlog(n)) cuando la selección del pivote divide el arreglo original en dos subarreglos de tamaño casi igual.

Por otro lado, si el algoritmo, que selecciona el elemento pivote de los arreglos de entrada, genera consistentemente 2 subarreglos con una gran diferencia en términos de tamaños de arreglo, el algoritmo de ordenación rápida puede lograr la complejidad de tiempo del peor caso de O(n^2 ).

Los pasos involucrados en Quick Sort son:

• Elige un elemento para que sirva como pivote, en este caso, el último elemento del arreglo es el pivote.
• Particionamiento: Ordena el arreglo de tal manera que todos los elementos menores que el pivote estén a la izquierda y todos los elementos mayores que el pivote estén a la derecha.
• Llama a Quicksort de forma recursiva, teniendo en cuenta el pivote anterior para subdividir adecuadamente los arreglos izquierdo y derecho. (Se puede encontrar una explicación más detallada en los comentarios a continuación)

Implementaciones de ejemplo en varios lenguajes

Implementación en JavaScript:

const arr = [6, 2, 5, 3, 8, 7, 1, 4];

const quickSort = (arr, start, end) => {

  if(start < end) {

   // Puedes obtener información sobre cómo se deriva el valor de pivote en los comentarios a continuación
    let pivot = partition(arr, start, end);

   // Asegúrate de leer los comentarios a continuación para comprender por qué se usan pivote - 1 y pivote + 1
// Estas son las llamadas recursivas a quickSort
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
  } 

}

const partition = (arr, start, end) => { 
  let pivot = end;
    // Establece i en start - 1 para que puedas acceder al primer índice en caso de que el valor en arr[0] sea mayor que arr[pivot]
  // Los comentarios posteriores se expondrán sobre el comentario anterior
  let i = start - 1,
      j = start;

  // Incrementa j hasta el índice que precede al pivote
  while (j < pivot) {

    // If the value is greater than the pivot increment j
    // Si el valor es mayor que el pivote incrementa j
    if (arr[j] > arr[pivot]) {
      j++;
    }

    // Cuando el valor en arr[j] es menor que el pivote:
    // incrementa i (arr[i] será un valor mayor que arr[pivot]) e intercambia el valor en arr[i] y arr[j]
    else {
      i++;
      swap(arr, j, i);
      j++;
    }

  }

  //El valor de arr[i + 1] será mayor que el valor de arr[pivot]
  swap(arr, i + 1, pivot);

    //Devuelves i + 1, ya que los valores a la izquierda son menores que arr[i+1], y los valores a la derecha son mayores que arr[i + 1]
   // Como tal, cuando se llama a las ordenaciones rápidas recursivas, los nuevos subconjuntos no incluirán este valor de pivote utilizado anteriormente 
  return i + 1;
}

const swap = (arr, firstIndex, secondIndex) => {
  let temp = arr[firstIndex];
  arr[firstIndex] = arr[secondIndex];
  arr[secondIndex] = temp;
}

quickSort(arr, 0, arr.length - 1);
console.log(arr);

Implementación en C

#include<stdio.h>  
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
}
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];     
    int i = (low - 1);  
  
    for (int j = low; j <= high- 1; j++) 
    { 
        if (arr[j] <= pivot) 
        { 
            i++;    
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
}
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    {
        int pi = partition(arr, low, high); 
  
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 
  

void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("n"); 
} 
  

int main() 
{ 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    quickSort(arr, 0, n-1); 
    printf("Sorted array: n"); 
    printArray(arr, n); 
    return 0; 
} 

Implementación en Python3

import random

z=[random.randint(0,100) for i in range(0,20)]

def quicksort(z):
    if(len(z)>1):        
        piv=int(len(z)/2)
        val=z[piv]
        lft=[i for i in z if i<val]
        mid=[i for i in z if i==val]
        rgt=[i for i in z if i>val]

        res=quicksort(lft)+mid+quicksort(rgt)
        return res
    else:
        return z
        
ans1=quicksort(z)
print(ans1)

Implementación en MATLAB

a = [9,4,7,3,8,5,1,6,2];

sorted = quicksort(a,1,length(a));

function [unsorted] =  quicksort(unsorted, low, high)
    if low < high
        [pInd, unsorted] = partition(unsorted, low, high);
        unsorted = quicksort(unsorted, low, pInd-1);
        unsorted = quicksort(unsorted, pInd+1, high);
    end

end

function [pInd, unsorted] = partition(unsorted, low, high)
    i = low-1;
    for j = low:1:high-1
        if unsorted(j) <= unsorted(high)
            i = i+1;
            unsorted([i,j]) = unsorted([j,i]);
            
        end
    end
    unsorted([i+1,high]) = unsorted([high,i+1]);
    pInd = i+1;

end

La complejidad espacial de ordenación rápida es O(n). Esta es una mejora con respecto a otros algoritmos de ordenación de divide y vencerás, que ocupan espacio O(nlong(n)).

La ordenación rápida logra esto cambiando el orden de los elementos dentro del arreglo dado. Compara esto con el algoritmo de ordenación por combinación que crea 2 arreglos, cada longitud n/2, en cada llamada de función.

Sin embargo, existe el problema de que este algoritmo de ordenación es de tiempo O(n*n)si el pivote siempre se mantiene en el medio. Esto se puede superar utilizando un pivote aleatorio.

Complejidad

Mejor, promedio, peor, memoria: n log(n)n log(n)n 2log(n). No es un algoritmo estable, y la ordenación rápida generalmente se realiza en el lugar con el espacio de pila O (log (n)).

La complejidad espacial de ordenación rápida es O(n). Esta es una mejora con respecto a otros algoritmos de ordenación de divide y vencerás, que ocupan espacio O(n log(n)).

Timsort

Timsort es un algoritmo de ordenación rápido que funciona con una complejidad estable de O(N log(N)).

Timsort es una mezcla de Insertion Sort y Mergesort. Este algoritmo se implementa en Arrays.sort() de Java, así como en sorted() y sort() de Python. Las partes más pequeñas se ordenan mediante Ordenación por inserción y luego se fusionan mediante Mergesort.

Una implementación rápida en Python:

def binary_search(the_array, item, start, end):
    if start == end:
        if the_array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = round((start + end)/ 2)

    if the_array[mid] < item:
        return binary_search(the_array, item, mid + 1, end)

    elif the_array[mid] > item:
        return binary_search(the_array, item, start, mid - 1)

    else:
        return mid

"""
Ordenación por inserción que usa timsort si el tamaño del arreglo es pequeño o si el tamaño de la "carrera" es pequeño
"""
def insertion_sort(the_array):
    l = len(the_array)
    for index in range(1, l):
        value = the_array[index]
        pos = binary_search(the_array, value, 0, index - 1)
        the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]
    return the_array

def merge(left, right):
    """
  Toma dos listas ordenadas y devuelve una sola lista ordenada comparando los
    elementos de uno en uno.
    [1, 2, 3, 4, 5, 6]
    """
    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])

def timsort(the_array):
    runs, sorted_runs = [], []
    length = len(the_array)
    new_run = [the_array[0]]

    # para cada i en el rango de 1 a la longitud del arreglo
    for i in range(1, length):
        # si i está al final de la lista
        if i == length - 1:
            new_run.append(the_array[i])
            runs.append(new_run)
            break
        # si el i-ésimo elemento del arreglo es menor que el anterior
        if the_array[i] < the_array[i-1]:
            # si new_run se establece en Ninguno (NULL)
            if not new_run:
                runs.append([the_array[i]])
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                new_run = []
        # de lo contrario si es igual o mayor 
        else:
            new_run.append(the_array[i])

    # para cada elemento en las ejecuciones, agrégalo usando la ordenación por inserción
    for item in runs:
        sorted_runs.append(insertion_sort(item))
    
    # por cada ejecución en sorted_runs, fusionarlos

    sorted_array = []
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    print(sorted_array)

timsort([2, 3, 1, 5, 6, 7])

Complejidad:

Tim sort tiene una complejidad estable de O(N log(N)) y se compara muy bien con Quicksort. En este cuadro se puede encontrar una comparación de complejidades.

Merge Sort (Ordenar por fusión)

Merge Sort es un algoritmo Divide y vencerás. Divide el arreglo de entrada en dos mitades, se llama a sí mismo para las dos mitades y luego fusiona las dos mitades ordenadas. La mayor parte del algoritmo tiene dos matrices ordenadas, y tenemos que fusionarlas en un único arreglo ordenado. Todo el proceso de ordenar un arreglo de N enteros se puede resumir en tres pasos:

• Divide el arreglo en dos mitades.
• Ordena la mitad izquierda y la mitad derecha usando el mismo algoritmo recurrente.
• Combina las mitades ordenadas.

Hay algo conocido como el algoritmo de dos dedos que nos ayuda a fusionar dos arreglos ordenados. El uso de esta subrutina y la llamada a la función de ordenación por fusión en las mitades del arreglo de forma recursiva nos dará el arreglo ordenado final que estamos buscando.

Dado que este es un algoritmo basado en la recursión, tenemos una relación de recurrencia para él. Una relación de recurrencia es simplemente una forma de representar un problema en términos de sus subproblemas.

T(n) = 2 * T(n / 2) + O(n)

Poniéndolo en lenguaje sencillo, dividimos el subproblema en dos partes en cada paso y tenemos una cantidad lineal de trabajo que tenemos que hacer para unir las dos mitades ordenadas en cada paso.

Complejidad

La mayor ventaja de usar Merge sort es que la complejidad del tiempo es solo n*log(n) para ordenar un Array completo. Es mucho mejor que n ^ 2 tiempo de ejecución de ordenación de burbuja o ordenación de inserción.

Antes de escribir el código, comprendamos cómo funciona la ordenación por combinación o fusión con la ayuda de un diagrama.

• Inicialmente tenemos un arreglo de 6 enteros no ordenados Arr(5, 8, 3, 9, 1, 2)
• Dividimos el arreglo en dos mitades Arr1 = (5, 8, 3) y Arr2 = (9, 1, 2).
• De nuevo, los dividimos en dos mitades: Arr3 = (5, 8) and Arr4 = (3) and Arr5 = (9, 1) and Arr6 = (2)
• De nuevo, los dividimos en dos mitades: Arr7 = (5), Arr8 = (8), Arr9 = (9), Arr10 = (1) y Arr6 = (2)
• Ahora compararemos los elementos en estos subconjuntos para fusionarlos.

Propiedades:

• Complejidad espacial: O(n)
• Complejidad temporal: O(n*log(n)). La complejidad del tiempo para Merge Sort podría no ser obvia a primera vista. El factor log(n) que entra se debe a la relación de recurrencia que hemos mencionado antes.
• Ordenar en el lugar: No en una implementación típica
• Estable: Sí
• Paralelizable: sí (varias variantes paralelas se analizan en la tercera edición de Introducción a los algoritmos de Cormen, Leiserson, Rivest y Stein).

Implementación de C++

void merge(int array[], int left, int mid, int right)
{
    int i, j, k;

    // Tamaño de la sublista izquierda
int size_left = mid - left + 1;

// Tamaño de la sublista derecha
int size_right =  right - mid;

/* crea arreglos temporales */
int Left[size_left], Right[size_right];

/* Copiar datos a arreglos temporales L[] y R[] */
for(i = 0; i < size_left; i++)
{
    Left[i] = array[left+i];
}

for(j = 0; j < size_right; j++)
{
    Right[j] = array[mid+1+j];
}

// Combinar los arreglos temporales de nuevo en arr[left..right]
i = 0; // Índice inicial del subarreglo izquierdo
j = 0; // Índice inicial del subarreglo derecho
k = left; // Índice inicial del subarreglo fusionado

while (i < size_left && j < size_right)
{
    if (Left[i] <= Right[j])
    {
        array[k] = Left[i];
        i++;
    }
    else
    {
        array[k] = Right[j];
        j++;
    }
    k++;
}

// Copia los elementos restantes de Left[]
while (i < size_left)
{
    array[k] = Left[i];
    i++;
    k++;
}

// Copiar el resto de elementos de Right[]
while (j < size_right)
{
    array[k] = Right[j];
    j++;
    k++;
}
}

void mergeSort(int array[], int left, int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;

        // Ordenar la primera y la segunda mitad
    mergeSort(array, left, mid);
    mergeSort(array, mid+1, right);

    // Finalmente fusionarlas
    merge(array, left, mid, right);
}
}

Implementación de JavaScript

function mergeSort (arr) {
  if (arr.length < 2) return arr;
  var mid = Math.floor(arr.length /2);
  var subLeft = mergeSort(arr.slice(0,mid));
  var subRight = mergeSort(arr.slice(mid));
  return merge(subLeft, subRight);
}

Primero verificamos la longitud del arreglo. Si es 1, simplemente devolvemos el arreglo. Este sería nuestro caso base. De lo contrario, encontraremos el valor medio y dividiremos el arreglo en dos mitades. Ahora ordenaremos ambas mitades con llamadas recursivas a la función MergeSort.

function merge (a,b) {
    var result = [];
    while (a.length >0 && b.length >0)
        result.push(a[0] < b[0]? a.shift() : b.shift());
    return result.concat(a.length? a : b);
}

Cuando fusionamos las dos mitades, almacenamos el resultado en un arreglo auxiliar. Compararemos el elemento inicial del arreglo izquierdo con el elemento inicial del arreglo derecho. Cualquiera que sea menor se insertará en el arreglo de resultados y lo eliminaremos de los arreglos respectivos usando el operador [shift()]. Si aún terminamos con valores en el arreglo izquierdo o derecho, simplemente los concatenaremos al final del resultado. Aquí está el resultado ordenado:

var test = [5,6,7,3,1,3,15];
console.log(mergeSort(test));

>> [1, 3, 3, 5, 6, 7, 15]

Un tutorial de YouTube de ordenación por combinación

Aquí hay un buen video de YouTube que explica el tema en detalle .

Implementación en JS

const list = [23, 4, 42, 15, 16, 8, 3]

const mergeSort = (list) =>{
  if(list.length <= 1) return list;
  const middle = list.length / 2 ;
  const left = list.slice(0, middle);
  const right = list.slice(middle, list.length);
  return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
  var result = [];
  while(left.length || right.length) {
    if(left.length && right.length) {
      if(left[0] < right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    } else if(left.length) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
  return result;
}

console.log(mergeSort(list)) // [ 3, 4, 8, 15, 16, 23, 42 ]

Implementación en C

#include<stdlib.h> 
#include<stdio.h>
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    
    int L[n1], R[n2]; 
  
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j];
    i = 0; 
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    {  
        int m = l+(r-l)/2; 
  
        
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
}
void printArray(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
  
    printf("Given array is \n"); 
    printArray(arr, arr_size); 
  
    mergeSort(arr, 0, arr_size - 1); 
  
    printf("\nSorted array is \n"); 
    printArray(arr, arr_size); 
    return 0; 

Implementación en C++

Consideremos el arreglo A = {2,5,7,8,9,12,13} y el arreglo B = {3,5,6,9,15} y queremos que el arreglo C también esté en orden ascendente.

void mergesort(int A[],int size_a,int B[],int size_b,int C[])
{
     int token_a,token_b,token_c;
     for(token_a=0, token_b=0, token_c=0; token_a<size_a && token_b<size_b; )
     {
          if(A[token_a]<=B[token_b])
               C[token_c++]=A[token_a++];
          else
               C[token_c++]=B[token_b++];
      }
      
      if(token_a<size_a)
      {
          while(token_a<size_a)
               C[token_c++]=A[token_a++];
      }
      else
      {
          while(token_b<size_b)
               C[token_c++]=B[token_b++];
      }

}

Implementación en Python

def merge(left,right,compare):
	result = [] 
	i,j = 0,0
	while (i < len(left) and j < len(right)):
		if compare(left[i],right[j]):
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	while (i < len(left)):
		result.append(left[i])
		i += 1
	while (j < len(right)):
		result.append(right[j])
		j += 1
	return result

def merge_sort(arr, compare = lambda x, y: x < y):
    #Utilizando la función lambda para ordenar el arreglo en orden (creciente y decreciente).
     #Por defecto ordena el arreglo en orden creciente
	if len(arr) < 2:
		return arr[:]
	else:
		middle = len(arr) // 2
		left = merge_sort(arr[:middle], compare)
		right = merge_sort(arr[middle:], compare)
		return merge(left, right, compare) 

arr = [2,1,4,5,3]
print(merge_sort(arr))

Implementación en Java

public class mergesort {

	public static int[] mergesort(int[] arr,int lo,int hi) {
		
		if(lo==hi) {
			int[] ba=new int[1];
			ba[0]=arr[lo];
			return ba;
		}
		
		int mid=(lo+hi)/2;
		int arr1[]=mergesort(arr,lo,mid);
		int arr2[]=mergesort(arr,mid+1,hi);
		return merge(arr1,arr2);
	}
	
	public static int[] merge(int[] arr1,int[] arr2) {
		int i=0,j=0,k=0;
		int n=arr1.length;
		int m=arr2.length;
		int[] arr3=new int[m+n];
		while(i<n && j<m) {
			if(arr1[i]<arr2[j]) {
				arr3[k]=arr1[i];
				i++;
			}
			else {
				arr3[k]=arr2[j];
				j++;
			}
			k++;
		}
		
		while(i<n) {
			arr3[k]=arr1[i];
			i++;
			k++;
		}
		
		while(j<m) {
			arr3[k]=arr2[j];
			j++;
			k++;
		}
		
		return arr3;
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[]= {2,9,8,3,6,4,10,7};
		int[] so=mergesort(arr,0,arr.length-1);
		for(int i=0;i<arr.length;i++)
			System.out.print(so[i]+" ");
	}

}

Ejemplo en Java

public class mergesort {
  public static int[] mergesort(int[] arr, int lo, int hi) {
    if (lo == hi) {
      int[] ba = new int[1];
      ba[0] = arr[lo];
      return ba;
    }
    int mid = (lo + hi) / 2;
    int arr1[] = mergesort(arr, lo, mid);
    int arr2[] = mergesort(arr, mid + 1, hi);
    return merge(arr1, arr2);
  }

  public static int[] merge(int[] arr1, int[] arr2) {
    int i = 0, j = 0, k = 0;
    int n = arr1.length;
    int m = arr2.length;
    int[] arr3 = new int[m + n];
    while (i < n && j < m) {
      if (arr1[i] < arr2[j]) {
        arr3[k] = arr1[i];
        i++;
      } else {
        arr3[k] = arr2[j];
        j++;
      }
      k++;
    }
    while (i < n) {
      arr3[k] = arr1[i];
      i++;
      k++;
    }
    while (j < m) {
      arr3[k] = arr2[j];
      j++;
      k++;
    }
    return arr3;
  }

  public static void main(String[] args) {
    int arr[] = {2, 9, 8, 3, 6, 4, 10, 7};
    int[] so = mergesort(arr, 0, arr.length - 1);
    for (int i = 0; i < arr.length; i++)
      System.out.print(so[i] + " ");
  }
}

Antes de empezar, hablemos de qué es el problema de la Torre de Hanoi. Bueno, este es un divertido juego de rompecabezas en el que el objetivo es mover una pila completa de discos desde la posición de origen a otra posición. Se siguen tres reglas simples:

1.Solo se puede mover un disco a la vez.
2.Cada movimiento consiste en tomar el disco superior de una de las pilas y colocarlo encima de otra pila. En otras palabras, un disco solo se puede mover si es el disco superior de una pila.
3.No se puede colocar un disco más grande encima de un disco más pequeño.

Ahora, intentemos imaginar un escenario. Supongamos que tenemos una pila de tres discos. Nuestro trabajo es mover esta pila del origen A al destino C. ¿Cómo hacemos esto?

Antes de que podamos llegar allí, imaginemos que hay un punto intermedio B.

Podemos usar a B como ayudante para terminar este trabajo. Ahora estamos listos para seguir adelante. Veamos cada uno de los pasos:

Mueve el primer disco de A a C
Mover el primer disco de A a B
Mueva el primer disco de C a B
Mueve el primer disco de A a C
Mueva el primer disco de B a A
Mueva el primer disco de B a C
Mueve el primer disco de A a C
¡Excelente! Hemos resuelto nuestro problema.

Puedes ver la imagen animada de arriba para una mejor comprensión.

Ahora, intentemos construir el algoritmo para resolver el problema. Espera, tenemos una nueva palabra aquí: "Algoritmo". ¿Qué es eso? ¿Alguna idea? No hay problema, vamos a ver.

¿Qué es un algoritmo?

Un algoritmo es uno de los conceptos más importantes para un desarrollador de software. De hecho, creo que no solo es importante para el desarrollo o la programación de software, sino para todos. Los algoritmos nos afectan en nuestra vida cotidiana. Veamos cómo.

Supongamos que trabaja en una oficina. Así que cada mañana haces una serie de tareas en secuencia: primero te levantas, luego vas al baño, desayunas, te preparas para la oficina, sales de casa, luego puedes tomar un taxi o un autobús o empezar a caminar hacia la oficina y, después de un tiempo determinado, llega a su oficina. Puedes decir que todos esos pasos forman un algoritmo.

En términos simples, un algoritmo es un conjunto de tareas. Espero que no hayas olvidado los pasos que hicimos para mover tres pilas de discos de A a C. También puedes decir que esos pasos son el algoritmo para resolver el problema de la Torre de Hanoi.

En Matemáticas y Ciencias de la Computación; un algoritmo es una especificación inequívoca de cómo resolver una clase de problemas. Los algoritmos pueden realizar tareas de cálculo, procesamiento de datos y razonamiento automatizado. —

Si observas esos pasos, puedes ver que estábamos haciendo la misma tarea varias veces: mover discos de una pila a otra. Podemos denominar a estos pasos como recursión.

Recursión

Recursion es estar llamando a la misma acción desde esa acción. Al igual que en la imagen de arriba.

Entonces, hay una regla para hacer cualquier trabajo recursivo: debe haber una condición para detener la ejecución de esa acción. Espero que entiendas los conceptos básicos sobre la recursividad.

Ahora, intentemos construir un procedimiento que nos ayude a resolver el problema de la Torre de Hanoi. Estamos tratando de construir la solución usando pseudocódigo. El pseudocódigo es un método para escribir código de computadora utilizando el idioma inglés.

torre(disco, origen, intermedio, destinacion)
{

}

Este es el esqueleto de nuestra solución. Tomamos el número total de discos como argumento. Luego, debemos pasar el origen, el lugar intermedio y el destino para que podamos entender el mapa que usaremos para completar el trabajo.

Ahora necesitamos encontrar un estado terminal. El estado terminal es el estado en el que ya no vamos a llamar a esta función.

IF disco is igual 1

En nuestro caso, este sería nuestro estado terminal. Porque cuando haya un disco en nuestra pila, entonces es fácil hacer ese paso final y luego nuestra tarea estará completa. No te preocupes si no te queda claro. Cuando lleguemos al final, este concepto será más claro.

Muy bien, hemos encontrado nuestro punto de estado terminal donde movemos nuestro disco al destino de esta manera:

mover disco desde el origen a nuestra destinación

Ahora volvemos a llamar a nuestra función pasando estos argumentos. En ese caso, dividimos la pila de discos en dos partes. El disco más grande (disco n) está en una parte y todos los demás discos (n-1) están en la segunda parte. Allí llamamos al método dos veces para -(n-1).

torre(disco - 1, origen, destinacion, intermedio)

Ahora pasaremos a un ejemplo de pseudocódigo más realista. Usaremos total_discos_on_stack — 1 como un argumento. Después de ello, procedemos a mover nuestro disco nuevamente de esta forma:

mover disco desde el origen a la destinación

Después de eso, volvemos a llamar a nuestro método así:

torre(disco - 1, intermedio, origen, destinacion)

Veamos el pseudocódigo:

torre(disco, origen, inter, dest)

IF disco is equal 1, THEN
       mover disco desde el origen a la destinación
   ELSE
       torre(disco- 1, origen, destinacion, intermedio)   // Step 1
       mover disco desde el origen a la destinación       // Step 2
       torre(disco - 1, intermedio, origen, destinacion)  // Step 3
   END IF
   
END

Este es el árbol para tres discos:

Este es el código completo en Ruby:

def tower(disk_numbers, source, auxilary, destination)
  if disk_numbers == 1
    puts "#{source} -> #{destination}"
    return
  end
  tower(disk_numbers - 1, source, destination, auxilary)
  puts "#{source} -> #{destination}"
  tower(disk_numbers - 1, auxilary, source, destination)
  nil
end

Empleamos tower(3, 'source','aux','dest')

Resultado:

source -> dest
source -> aux
dest -> aux
source -> dest
aux -> source
aux -> dest
source -> dest

Se necesitaron siete pasos para que tres discos llegaran al destino. A esto lo llamamos un método recursivo.

Cálculos en la complejidad del tiempo y el espacio

Complejidad Temporal

Cuando ejecutamos código o una aplicación en nuestra máquina, lleva tiempo: ciclos de CPU. Pero no es lo mismo para todas las computadoras. Por ejemplo, el tiempo de procesamiento de un core i7 y de un dual core no es el mismo. Para resolver este problema existe un concepto utilizado en informática llamado complejidad temporal.

La complejidad del tiempo es un concepto en informática que se ocupa de la cuantificación de la cantidad de tiempo que tarda un conjunto de código o algoritmo en procesarse o ejecutarse en función de la cantidad de entrada.

En otras palabras, la complejidad del tiempo es esencialmente eficiencia, o cuánto tarda una función de programa en procesar una entrada determinada.

La complejidad temporal de los algoritmos se expresa más comúnmente utilizando la Cota superior asintótica. Una notación asintótica para representar la complejidad del tiempo.

Ahora, el tiempo requerido para mover n discos es T(n). Hay dos llamadas recursivas para (n-1). Hay una operación de tiempo constante para mover un disco desde el origen hasta el destino, sea m1. Por lo tanto:

T(n) = 2T(n-1) + m1    ..... eq(1)

Y también:

T(0) = m2, a constant   ...... eq(2)
From eq (1)
T(1) = 2T(1-1) + m1
     = 2T(0)+m1
     = 2m2 + m1 ..... eq(3) [From eq 2]
T(2) = 2T(2-1) + m1
     = 2T(1) + m1
     = 4m2 + 2m1 + m1 .... eq(4) [From eq(3)]
T(3) = 2T(3-1) + m1
     = 2T(2) + m1
     = 8m2 + 4m1 + 2m1 + m1  [From eq(4)]

A partir de estos patrones, eq(2) hasta el último, podemos decir que la complejidad temporal de este algoritmo es O(2^n) u O(a^n) donde a es una constante mayor que 1. Por lo tanto, tiene una exponencial complejidad del tiempo. Para el aumento único del tamaño del problema, el tiempo requerido es el doble del anterior. Esto es computacionalmente muy costoso. La mayoría de los programas recursivos toman un tiempo exponencial, y por eso es muy difícil escribirlos iterativamente.

Complejidad Espacial

Después de la explicación del análisis de la complejidad del tiempo, creo que ahora puedes adivinar qué es esto... Este es el cálculo del espacio requerido en RAM para ejecutar un código o una aplicación.

En nuestro caso, el espacio para el parámetro de cada llamada es independiente de n, lo que significa que es constante. Que sea J. Cuando hacemos la segunda llamada recursiva, la primera ha terminado. Eso significa que podemos reutilizar el espacio después de terminar el primero. Por eso:

Por tanto:

T(n) = T(n-1) + k .... eq(1)
T(0) = k, [constant] .... eq(2)
T(1) = T(1-1) + k
     = T(0) + k
     = 2K
T(2) = 3k
T(3) = 4k

Entonces la complejidad del espacio es O(n).

Después de estos análisis, podemos ver que la complejidad temporal de este algoritmo es exponencial, pero la complejidad espacial es lineal.

Conclusión
A partir de este artículo, espero que ahora puedas entender el rompecabezas de la Torre de Hanoi y cómo resolverlo. Además, traté de brindarle una comprensión básica sobre los algoritmos, su importancia, recursividad, pseudocódigo, complejidad temporal y complejidad espacial.

Complejidad

La complejidad es un factor involucrado en un proceso complejo. Con respecto a los algoritmos y las estructuras de datos; esto puede ser por tiempo o espacio (espacio en disco) necesario para realizar una tarea específica (buscar, clasificar o acceder a los datos) en una estructura de datos determinada. La eficiencia del rendimiento de una tarea depende del número de operaciones requeridas para completarla.

Sacar la basura puede requerir 3 pasos (atar, sacar y tirar en el basurero). Sacar la basura puede ser simple, pero si la vas a sacar después de una larga semana, es posible que no puedas completar la tarea debido a la falta de espacio en el basurero.

Aspirar una habitación puede requerir muchos pasos repetitivos (encender la aspiradora, aspirar repetidamente los espacios de la habitación y apagarla). Mientras más grande sea la habitación, más tiempo llevará aspirar la habitación.

Entonces, existe una relación entre el número de operaciones realizadas y el número de elementos operados. Tener mucha basura (elementos) requiere sacarla muchas veces. Esto puede generar un problema de complejidad espacial (space complexity). Tener una gran cantidad metros cuadrados (elementos) requiere aspirar muchas veces. Esto puede dar lugar a un problema de complejidad en tiempo (time complexity).

Ya sea que esté sacando la basura o aspirando una habitación, podría decir que el orden de la operación (O) incrementa exactamente con el número de elementos (n). Si tengo 1 bolsa de basura, tengo que sacar la basura una vez. Si tengo 2 bolsas de basura, tengo que hacer la misma tarea dos veces, asumiendo que físicamente no puedo levantar más de una bola a la vez. Entonces, the Big-O de estas tareas es O = n o O = function(n) o O(n). Esto es una complejidad lineal (linear complexity) (una línea recta entre 1 operación: 1 elemento). Entonces, 30 operaciones equivalen a 30 elementos (línea amarilla del gráfico anterior).

Esto es similar a lo que sucede cuando se consideran algoritmos y estructuras de datos

Búsquedas

Búsqueda lineal

origen

El mejor caso para buscar un elemento en una lista ordenada, es uno después del otro. Es una constante O(1), asumiendo que es el primer elemento en tu lista. Por lo tanto, si el elemento que estás buscando siempre aparece primero en la lista, independientemente del tamaño de la lista, encontrarás el elemento inmediatamente. La complejidad de la búsqueda es constante con el tamaño de la lista. El peor caso de este tipo de busqueda es de complejidad lineal o O(n). En otras palabras, para n elementos, tengo que buscar n veces antes de encontrar mi elemento, por eso es una búsqueda lineal.

Búsqueda binaria

origen

Para búsqueda binaria, el mejor caso es O(1), esto significa que el elemento que buscas se encuentra en el centro. El peor caso es log base 2 of n o:

Logaritmo o log es la manera de expresar un exponente a una base dada. Entonces, si hay 16 elementos (n = 16), esto tomará, en el peor caso, 4 pasos para encontrar el número 15 (exponente = 4).

o simplemente: O(log n)

Ordenamiento

Ordenamiento Burbuja (Bubble)

origen

En el ordenamiento burbuja, cada elemento es comparado con el resto de la colección para determinar el máximo valor. Por esta razón, el peor caso es de complejidad O(n²). Pensemos en un bucle dentro de otro bucle.

Entonces, por cada elemento necesitas compararlo con el resto de la colección, un total de 16 comparaciones para 4 elementos (4² = 16). En el mejor de los casos la colección ya esta ordenada, excepto por un solo elemento. Esto equivale a una sola ronda de comparaciones. Es decir, se requiren cuatro comparaciones, que es una complejidad de O(n).

Selección

origen

A diferencia del ordenamiento burbuja, en lugar de intercambiar el valor más alto, intercambia el valor más bajo. El ordenamiento por selección selecciona el valor más bajo para intercambiarlo con las primeras posiciones. Pero, como requiere comparar cada elemento con el resto de la colección también tiene una complejidad O(n²).

Inserción

origen

A diferencia de los ordenamientos burbuja y selección, el ordenamiento por inserción inserta los elementos en su posición correcta. Pero, igual que el ordenamiento anterior requiere comparar cada elemento con el resto de la colección, por lo tanto, tiene una complejidad de orden O(n²). Al igual que el ordenamiento burbuja, si solo queda un elemento por ordenar, solo se requiere una ronda de comparaciones para insertar el elemento en su posición correcta. Es decir, en su mejor caso tiene una complejidad O(n).

Estructuras de datos

Arreglos

Debido a que se necesita un solo paso para acceder a los elementos de un arreglo usando su índice, o agregar/eliminar un elemento al final del arreglo, la complejidad para acceder, añadir o eliminar un valor de un arreglo es O(1). Considerando, buscar linealmente a través de un arreglo usando su índice, como lo vimos antes, tiene una complejidad de O(n).

Además, debido a que un cambio de un valor hacia o desde el inicio de una matriz (shift o unshift) requiere volver a generar los índices(es decir, eliminar un elemento en el índice 0 requiere volver a etiquetar el elemento del índice 1 como índice 0, y así sucesivamente). Tiene una complejidad O(n) ya que la generación de los índices se realiza desde el inicio hasta el final del arreglo.

clave — Valor

Acceder, insertar o remover un valor usando la clave es instantáneo, por lo que se entiende complejidad O(1). Buscando en un "depósito" un elemento específico usando todas las claves disponibles es en esencia una busqueda lineal, y tiene una complejidad O(n).

Conclusión

Complejidad es más que un tema para discutir en algoritmos y estructuras de datos. Si se usa con prudencia, puede ser útil para medir la eficiencia del trabajo que se realiza y el código que se crea para resolver problemas.

Referencia

https://www.udemy.com/js-algorithms-and-data-structures-masterclass/

Traducido del artículo de Yung L. Leung - The complexity of simple algorithms and data structures in JS

Divide y vencerás es un paradigma algorítmico (a veces llamado por error Divide y Concurrir - una adaptación en broma), similar a los paradigmas de programación Dinámica y Algoritmos ávidos o glotones. Un algoritmo Divide y Vencerás típico resuelve un problema siguiendo estos 3 pasos.

1. Dividir: Descomponer el problema en sub-problemas del mismo tipo. Este paso involucra descomponer el problema original en pequeños sub-problemas. Cada sub-problema debe representar una parte del problema original. Por lo general, este paso emplea un enfoque recursivo para dividir el problema hasta que no es posible crear un sub-problema más.
2. Vencer:  Resolver los sub-problemas recursivamente. Este paso recibe un gran conjunto de sub-problemas a ser resueltos. Generalmente a este nivel, los problemas se resuelven por sí solos.
3. Combinar: Combinar las respuestas apropiadamente. Cuando los sub-problemas son resueltos, esta fase los combina recursivamente hasta que estos formulan la solución al problema original. Este enfoque algorítmico trabaja recursivamente y los pasos de conquista y fusión trabajan tan a la par que parece un sólo paso.

Usualmente este método nos permite hacer una reducción bastante significativa en la complejidad tiempo del algoritmo a emplear.

Por ejemplo, el método de la burbuja conlleva una complejidad de  O(n^2), mientras que el quicksort (una aplicación de Dividir y Vencer) reduce la complejidad a O(nlog(n)). La búsqueda linear tiene una complejidad de O(n), mientras que la búsqueda binaria(otra aplicación de dividir y vencer) reduce la complejidad a  O(log(n)).

A continuación algunos de los algoritmos estándar de la variedad dividir y vencer

Búsqueda Binaria, es un algoritmo de búsqueda. En cada paso, el algoritmo compara el parámetro de entrada (x) con el valor del elemento en la mitad del arreglo. Si los valores coinciden, retorna el índice del elemento medio. De lo contrario, si x es mejor al elemento medio, el algoritmo recurre a la mitad izquierda del elemento medio, de lo contrario retorna la mitad a la derecha del elemento medio.

Quicksort, es un algoritmo de ordenamiento. El algoritmo elige un elemento pivote, reordena los elementos del arreglo de forma que todos los elementos de menor valor al del elemento pivote se mueven hacia su izquierda y los elementos de mayor valor hacia su derecha. Finalmente, el algoritmo ordena los sub-arreglos recursivamente hacia la izquierda y derecha del elemento pivote.

Merge Sort, es también un algoritmo de ordenamiento. Este algoritmo divide el arreglo en dos partes, ordenada cada una de ellas recursivamente, y finalmente une las dos partes ya ordenadas. El tiempo de complejidad de este algoritmo es de  O(nLogn), en el mejor caso, caso medio y en el peor de los casos. La complejidad de tiempo puede ser entendida fácilmente recurriendo a la ecuación: T(n) = 2T(n/2) + n.

Par de puntos más cercanos, El problema es encontrar el par de puntos más cercano a otra par dado en el plano XY. Este problema puede ser resuelto en un tiempo O(n^2) calculando la distancia de cada par de puntos y comparando las distancias hasta encontrar la menor. El algoritmo de tipo Dividir y Vencer resuelve este problema en un tiempo  O(nLogn).

Algoritmo de Strassen es un algoritmo eficiente para multiplicar dos matrices. Un método simple para multiplicar dos matrices requiere 3 bucles anidados lo que nos da una complejidad de  O(n^3).  El algoritmo de Strassen multiplica dos matrices en un tiempo de  O(n^2.8974).

El Algoritmo Cooley–Tukey de Transformación Rápida de Fourier (FFT) es el algoritmo más común de FFT (Transformación Rápida de Fourier en inglés). Es un algoritmo de tipo Dividir y Vencer que opera en un tiempo de O(nlogn).

El algortimo de Karatsuba, este fue el primer algoritmo de multiplicación más rápido asintóticamente que el algoritmo cuadrático clásico de multiplicación. Este algoritmo consigue reducir la multiplicación de dos números de n dígitos a como máximo de  n^1.585( que es la aproximación del logaritmo de 3 en base 2) multiplicaciones de un dígito. Por lo tanto es más rápido que el algoritmo clásico que requiere el producto de n^2 de números de un dígito.

Dividir y vencer (D & V) vs programación dinámica (DP)

Ambos paradigmas (D & V y PD) dividen un problema cualquiera en sub problema y resuelve cada uno de ellos. ¿Cómo elegir uno de ellos para un problema? Dividir y Vencer debe ser empleado cuando los sub problemas no son evaluados muchas veces. De lo contrario programación dinámica o memoización debería emplearse en su lugar.

Por ejemplo, la Búsqueda Binaria es un algoritmo Dividir y Vencer, nunca evaluaremos los sub problema más de una vez. Por otro lado, el cálculo del Número Fibonacci se debe preferir la aplicación de Programación Dinámica.

Traducción del Artículo - Divide and Conquer Algorithm Meaning: Explained with Examples