Skip to Content
CTRL K

Preparing for Merge Sort

Explicación

Simular simplemente el proceso descrito es potencialmente O(N2)\mathcal{O}(N^2), así que no podemos hacer eso. ¿Y si, en lugar de hallar las secuencias de a una, las hallamos todas al mismo tiempo?

Imaginemos que ya conocemos las secuencias de los primeros i−1i - 1 números y queremos insertar el ii-ésimo número en una de las secuencias.

¿En qué secuencia deberíamos insertar este número? Deberíamos insertarlo en la primera secuencia cuyo último número sea menor que el ii-ésimo número.

La observación clave de este problema es que los últimos números de las secuencias existentes forman una secuencia no creciente. (Para demostrarlo, usamos una demostración por contradicción: ¿qué pasaría si hubiera un aumento en algún punto?)

Esto significa que podemos simplemente hacer búsqueda binaria de la secuencia en la que deberíamos insertar el ii-ésimo número.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N \log N)

#include <iostream>
#include <vector>
 
using std::vector;
 
int main() {
	int n;
	std::cin >> n;
	vector<vector<int>> sequences;
 
	for (int i = 0; i < n; i++) {
		int a;
		std::cin >> a;
		int lo = 0, hi = (int)sequences.size();
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (sequences[mid].back() < a) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
 
		if (lo == (int)sequences.size()) {
			sequences.push_back({a});
		} else {
			sequences[lo].push_back({a});
		}
	}
 
	for (vector<int> i : sequences) {
		for (int j : i) { std::cout << j << " "; }
		std::cout << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class PreparingForMergeSort {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		List<List<Integer>> sequences = new ArrayList<>();
 
		for (int i = 0; i < n; i++) {
			int a = io.nextInt();
			int lo = 0, hi = sequences.size();
			while (lo < hi) {
				int mid = (lo + hi) / 2;
				if (sequences.get(mid).get(sequences.get(mid).size() - 1) < a) {
					hi = mid;
				} else {
					lo = mid + 1;
				}
			}
 
			if (lo == sequences.size()) {
				sequences.add(new ArrayList<>(Collections.singletonList(a)));
			} else {
				sequences.get(lo).add(a);
			}
		}
 
		for (List<Integer> i : sequences) {
			for (int j : i) { io.print(j + " "); }
			io.println();
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}
n = int(input().strip())
numbers = [int(x) for x in input().strip().split()]
 
sequences = []
for num in numbers:
	l = 0
	r = len(sequences)
	while l != r:
		mid = (l + r) // 2
		if sequences[mid][-1] < num:
			r = mid
		else:
			l = mid + 1
	if l == len(sequences):
		sequences.append([num])
	else:
		sequences[l].append(num)
 
for sub in sequences:
	print(*sub)
Fundamentos