Una solución sin usar ninguna librería:
def frequency_sort(lista):
salida = []
for valor in lista:
for i in range(len(salida)):
if valor == salida[i][0]:
salida[i] = (valor, salida[i][1] + 1)
break
else:
salida.append((valor, 1))
resultado = []
for valor, cuenta in salida:
resultado.extend([valor] * cuenta)
return resultado
La lista salida
contiene pares (valor, cuenta)
, con el valor encontrado y las veces que aparece.
Esta lista se construyendo recorriendo la primera lista. Por cada elemento, se recorre salida
buscando un par correspondiente a ese valor.
Si se encuentra el valor, se calcula una nueva tupla y se reemplaza la existente en la lista.
Si no se encuentra el valor, se genera una nueva tupla (valor, 1)
y se agrega a la salida.
Esto asegura que en la lista salida
los items aparezcan en el mismo orden de la entrada.
El paso final es recorrer salida
transformando cada tupla (valor, cuenta)
en la correspondiente repetición de valores valor, valor, .., valor
para extender la lista resultado
.
Demo
def frequency_sort(lista):
salida = []
for valor in lista:
for i in range(len(salida)):
if valor == salida[i][0]:
salida[i] = (valor, salida[i][1] + 1)
break
else:
salida.append((valor, 1))
resultado = []
for valor, cuenta in salida:
resultado.extend([valor] * cuenta)
return resultado
lista = [4, 6, 2, 2, 6, 4, 4, 4] # ff
print(frequency_sort(lista))
produce:
[4, 4, 4, 4, 6, 6, 2, 2]
Process finished with exit code 0
Edición
El algoritmo genera la lista final expandida.