Out of Sorts

Solución en video

Por I-Chen Chou

Nota: La solución en video podría no ser la misma que las otras soluciones. Código en C++ y Java.

Solución

Explicación

Para cualquier $i$ , el valor $i - a_i$ representa una cota inferior del número total de pasadas de burbuja necesarias para ordenar el arreglo. Si $i - a_i$ es positivo, indica que el elemento necesita moverse a la izquierda al menos esa cantidad. Si es negativo, sigue siendo una cota inferior válida ya que el elemento no necesita moverse más a la izquierda.

Para entender por qué max( $i - a_i$ ) es correcto, consideremos cualquier elemento $a_i$ donde $i - a_i$ es positivo (es decir, está a la derecha de su posición correcta). Para que esto ocurra, debe haber algún elemento mayor a la izquierda de $a_i$ . Por cómo funciona el ordenamiento de burbuja, $a_i$ necesariamente se moverá a la izquierda en cada pasada hasta llegar a su posición correcta, y su valor $i - a_i$ disminuye en $1$ con cada pasada.

Ahora consideremos un elemento $a_i$ donde $i - a_i$ vale $0$ (el elemento ya está en su posición correcta). Un elemento así puede o no moverse a la izquierda, pero no se moverá a la derecha. Para que se mueva a la derecha, el elemento inmediatamente a su derecha tendría que ser menor, lo que implica que hay un elemento mayor a su izquierda, haciendo que $a_i$ se mueva a la izquierda en su lugar. Así, $i - a_i$ igual a $0$ se mantiene o disminuye.

Como resultado, max( $i - a_i$ ), si es positivo, disminuye en $1$ durante cada iteración del ordenamiento de burbuja. Tras contar el número de iteraciones necesarias para ordenar el arreglo, sumamos $1$ para tener en cuenta la iteración final que realiza el algoritmo, como se indica en el pseudocódigo.

Implementación

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

C++JavaPython


#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
struct Entry {
	int val;
	int index;
};
 
int main() {
	std::ifstream read("sort.in");
	int n;
	read >> n;
	vector<Entry> entries(n);
	for (int i = 0; i < n; i++) {
		read >> entries[i].val;
		entries[i].index = i;
	}
 
	std::sort(entries.begin(), entries.end(), [](const Entry &e1, const Entry &e2) {
		return e1.val == e2.val ? e1.index < e2.index : e1.val < e2.val;
	});
 
	// contamos la cantidad de burbujas necesarias para ordenar el arreglo
	int moo_amt = 1;
	for (int i = 0; i < n; i++) {
		// sumamos 1 para tener en cuenta la iteración final del algoritmo
		moo_amt = std::max(moo_amt, 1 + entries[i].index - i);
	}
 
	std::ofstream("sort.out") << moo_amt << endl;
}


import java.io.*;
import java.util.*;
 
public class Sort {
	// BeginCodeSnip{Array Element Class}
	static class Entry implements Comparable<Entry> {
		public int val;
		public int index;
 
		public Entry(int v, int i) {
			val = v;
			index = i;
		}
 
		public int compareTo(Entry other) {
			if (this.val == other.val) { return this.index - other.index; }
			return this.val - other.val;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio("sort");
		int n = io.nextInt();
		Entry[] entries = new Entry[n];
		for (int i = 0; i < n; i++) { entries[i] = new Entry(io.nextInt(), i); }
 
		Arrays.sort(entries);
 
		int mooAmt = 1;
		// contamos la cantidad de burbujas necesarias para ordenar el arreglo
		for (int i = 0; i < entries.length; i++) {
			// sumamos 1 para tener en cuenta la iteración final del algoritmo
			mooAmt = Math.max(mooAmt, 1 + entries[i].index - i);
		}
 
		io.println(mooAmt);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


from typing import NamedTuple
from functools import cmp_to_key
 
 
class Entry(NamedTuple):
	val: int
	index: int
 
 
with open("sort.in") as read:
	entries = []
	for i in range(int(read.readline())):
		entries.append(Entry(int(read.readline()), i))
 
cmp = lambda e1, e2: e1.index - e2.index if e1.val == e2.val else e1.val - e2.val
entries.sort(key=cmp_to_key(cmp))
 
moo_amt = 1
# contamos la cantidad de burbujas necesarias para ordenar el arreglo
for i in range(len(entries)):
	# sumamos 1 para tener en cuenta la iteración final del algoritmo
	moo_amt = max(moo_amt, 1 + entries[i].index - i)
 
print(moo_amt, file=open("sort.out", "w"))