Introducción al ordenamiento

El ordenamiento (sorting) consiste en disponer elementos en un orden particular.

Métodos de ordenamiento

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	HR	Bubble Sort	Muy fácil	Sorting	—

Recursos
Fuente	Recurso	Notas
CPH	3.1 - Sorting Theory	ordenamiento de burbuja, mergesort, ordenamiento por conteo
CSA	Sorting	ordenamiento por selección, por inserción, de burbuja, mergesort

Ordenamiento de librería

Aunque por lo general no hace falta saber cómo está implementado el ordenamiento, sí hay que saber usar los métodos incorporados.

C++JavaPython

Recursos
Fuente	Recurso	Notas
CPH	3.2 - Sorting in C++	se puede parar antes de los structs definidos por el usuario, que se cubren en Plata
CPP	std::sort	referencia
CF	C++ Tricks	los dos primeros relacionados con ordenamiento

Recursos
Fuente	Recurso	Notas
tutorialspoint	Java sorting	Cubre el ordenamiento de arreglos
Oracle	Arrays.sort	API para ordenar arreglos estáticos
Oracle	Collections.sort	API para ordenar arreglos dinámicos

Recursos
Fuente	Recurso	Notas
PY	Sorting HOW TO	referencia

C++JavaPython

Arreglos estáticos

Para ordenar arreglos estáticos se usa sort(arr, arr + N), donde $N$ es la cantidad de elementos a ordenar. El rango también se puede indicar reemplazando arr y arr + N por el rango deseado. Por ejemplo, sort(arr + 1, arr + 4) ordena los índices $[1, 4)$ .


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int arr[] = {5, 1, 3, 2, 4};
	int N = 5;
	sort(arr, arr + N);
	for (int i = 0; i < N; i++) cout << arr[i] << " ";  // 1 2 3 4 5
	cout << endl;
 
	int arr2[] = {5, 1, 3, 2, 4};
	sort(arr2 + 1, arr2 + 4);
	for (int i = 0; i < N; i++) cout << arr2[i] << " ";  // 5 1 2 3 4
}

Arreglos estáticos

Para ordenar un arreglo estático se usa Arrays.sort(arr).


import java.util.*;
 
class Main {
	public static void main(String[] args) {
		int arr[] = {5, 1, 3, 2, 4};
		Arrays.sort(arr);
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i] + " ");  // 1 2 3 4 5
	}
}

Arreglos estáticos

Para crear un arreglo estático en Python se usa el módulo array. Python no tiene un método de ordenamiento incorporado para arrays, pero se puede usar la función sorted(), que ordena el arreglo como lista y devuelve una lista. Luego se convierte la lista de nuevo en un array.


from array import array
 
# "i" indica que los elementos del array son enteros
arr = array("i", [5, 1, 3, 2, 4])
 
print(arr)  # Imprime el arreglo original
print(sorted(arr))  # Imprime el arreglo ordenado, convertido a lista
 
arr = array("i", sorted(arr))  # Ordenar y convertir de nuevo a array
print(arr)

Arreglos dinámicos

C++JavaPython

Para ordenar un arreglo dinámico se usa sort(v.begin(), v.end()) (o sort(begin(v),end(v))). La función de ordenamiento por defecto ordena el arreglo en orden ascendente. De forma similar, se puede indicar el rango. Por ejemplo, sort(v.begin() + 1, v.begin() + 4) ordena los índices $[1, 4)$ .


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	vector<int> v{5, 1, 3, 2, 4};
	sort(v.begin(), v.end());
	// Imprime 1 2 3 4 5
	for (int i : v) { cout << i << " "; }
	cout << endl;
 
	v = {5, 1, 3, 2, 4};
	sort(v.begin() + 1, v.begin() + 4);
	// Imprime 5 1 2 3 4
	for (int i : v) { cout << i << " "; }
	cout << endl;
}

Para ordenar un arreglo dinámico se usa Collections.sort(list). Esta función ordena el arreglo en orden ascendente por defecto.


import java.util.*;
 
class Main {
	public static void main(String[] args) {
		List<Integer> arr = new ArrayList<Integer>(Arrays.asList(5, 1, 3, 2, 4));
		Collections.sort(arr);
		System.out.println(arr);  // Imprime [1, 2, 3, 4, 5]
	}
}

Hay dos formas principales de ordenar una lista en Python. Se puede usar sorted(arr), que devuelve una lista nueva y no modifica la anterior, o arr.sort(), que ordena la lista in situ.


arr = [5, 1, 3, 2, 4]
print(sorted(arr))  # Imprime [1, 2, 3, 4, 5]
print(arr)  # Imprime el arreglo original
 
arr.sort()
print(arr)  # Imprime [1, 2, 3, 4, 5]

Para más sobre ordenamiento en Python, ver este enlace .

Arreglos (dinámicos) de pares y tuplas

C++JavaPython

Por defecto, los pares de C++ se ordenan por el primer elemento y, en caso de empate, por el segundo.


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	vector<pair<int, int>> v{{1, 5}, {2, 3}, {1, 2}};
	sort(v.begin(), v.end());
 
	/*
	 * Imprime:
	 * 1 2
	 * 1 5
	 * 2 3
	 */
	for (pair<int, int> p : v) { cout << p.first << " " << p.second << endl; }
}

Las tuplas se ordenan de forma similar.

Hay que definir un comparador personalizado. Esto se cubre en Plata.

Por defecto, las tuplas de Python se ordenan por el primer elemento, luego el segundo, y así sucesivamente en caso de empates sucesivos.


arr = [(1, 5), (2, 3), (1, 2)]
arr = sorted(arr)
print(arr)  # Imprime [(1, 2), (1, 5), (2, 3)]

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	★ Distinct Numbers	Fácil	Sorting	Solución
CF	Playing in a Casino	Fácil	Sorting	Solución
CF	★ Kayaking	Normal	Sorting, Greedy	Solución
Bronze	Why Did the Cow Cross the Road III	Normal	Sorting, Simulation	Solución
Bronze	Cow College	Normal	Sorting	Solución
Bronze	Angry Cows	Difícil	Simulation, Sorting	Solución
CF	Permutator	Difícil	Greedy, Sorting	Solución

Nota: hay más problemas de ordenamiento en el módulo Introducción a conjuntos.

Comprobar la comprensión

Pregunta 1/4

¿Cómo quedaría el arreglo

[7, 2, 6, 3, 1]

después de 1 pasada de ordenamiento de burbuja?