Si encuentras alguna parte que te causa duda nos puedes dejar un comentario y haremos todo lo necesario de ayudarte rápidamente.
Solución:
Voy a interpretar “Quicksort con la partición de Lomuto” como una referencia al algoritmo de aquí (diapositivas 21 y 22).
Este algoritmo es inestable en el array [a, b, c] dónde C < a = b.
Encontré este contraejemplo al implementar el algoritmo Quicksort en Python para que (como el ordenamiento integrado de Python) se necesita un key función. Al proporcionar un adecuado key función, puedo hacer que el género piense que ciertos elementos son idénticos, pero aún puedo distinguirlos. Entonces solo es cuestión de probar muchas permutaciones y detectar la inestabilidad. El siguiente código ciertamente no agota las posibles pruebas (es posible que desee probar más de dos elementos idénticos o múltiples conjuntos de elementos idénticos), pero fue lo suficientemente bueno en este caso.
def lomuto(A, key=lambda x:x):
def partition(A, p, r):
i = p - 1
pivot = A[r]
for j in range(p, r):
if key(A[j]) <= key(pivot):
i += 1
A[i], A[j] = A[j], A[i]
A[i+1], A[r] = A[r], A[i+1]
return i + 1
def quicksort(A, p, r):
if p < r:
q = partition(A, p, r)
quicksort(A, p, q-1)
quicksort(A, q+1, r)
quicksort(A, 0, len(A) - 1)
def test_stability(f, n):
"""Try to discover if the sorting function f is stable on n inputs;
printing the first counterexample found, if any."""
import itertools
for i in range(n - 1):
def order(P): return P.index((i, 0)) < P.index((i, 1))
array = [(j, 0) for j in range(n - 1)] + [(i, 1)]
for P in map(list, itertools.permutations(array)):
Q = P[:] # take a copy
f(Q, key=lambda x: x[0])
if order(P) != order(Q):
print(P, '->', Q)
return
>>> test_stability(lomuto, 3)
[(1, 0), (1, 1), (0, 0)] -> [(0, 0), (1, 1), (1, 0)]
Si entiendes que te ha sido de ayuda nuestro artículo, nos gustaría que lo compartas con el resto entusiastas de la programación de esta manera nos ayudas a extender este contenido.