Counting Sort | Ordenamiento por conteo
Vložit
- čas přidán 23. 07. 2024
- Counting Sort o el Ordenamiento por Cuentas, es un método de ordenamiento donde no aplicamos comparaciones para determinar la posición final de nuestros elementos, en su lugar usamos un arreglo auxiliar donde vamos contando cuántos elementos de cada valor hay y lo usamos para ordenar.
Código:
pastebin.com/XXhRKbxB
Contenido:
0:00 Intro
0:46 Idea de Counting Sort
2:22 Ejemplo visual
5:10 Código
6:45 Análisis
8:06 Otros Detalles
Libros recomendados:
kit.co/schiob
Únete como miembro para apoyar al canal y acceder a sus beneficios:
/ @chiocode
Apóyame con una pizza:
www.buymeacoffee.com/schiob
Para contenido atrás de cámara y fotos de comida sígueme en:
/ schiob
/ schiob
github.com/schiob
Excelente explicación
Justo estoy haciendo un ejercicio sobre este algoritmo y no tiene mucho que acabas de subir la explicación. Gracias master 🤙🏼
excelente!
👍
(No hate) Porfa haz un video de punteros en C me urge para poder resolver problemas complicados de programación y a casi ningún tutorial le agarro porfa
Super interesante este canal! Cómo sería si queremos tener claves únicas? Podemos extender el algoritmo para hacer un merge de los duplicados?
Lo que se me ocurre es al principio del algoritmo, cuando estamos contando las instancias de cada número, si nos topamos con los repetidos, simplemente no agregarlo a la cuenta, pero definitivamente me faltan detalles por ahí :)
Hola como estas!? vos sabes que quise agregar este video a mi lista de reproduccion de youtube y no me aparece la opcion. por que sera?
Entendi en minutos lo que no entendi en 2 horas de clase, ahora solo me falta saber como se ordena de mayor a menor
reverse al final
Lo hice para números negativos, pero creo que se puede mejorar
```
import numpy as np
def find_low(x, arr, minim):
if x < minim or x is None:
return None
num = arr.get(x - 1)
if not (num is None):
return x - 1
else:
return find_low(x - 1, arr, minim)
def countingSort(numbers):
minim = min(numbers)
maxim = max(numbers)
ordering = np.zeros(numbers.shape, dtype=int)
print(f' * Numbers : {numbers}')
print(f' * lower : {minim}')
print(f' * upper : {maxim}')
asd = {}
for num in numbers:
asd[num] = asd.get(num, 0) + 1
for num in np.arange(minim + 1, maxim + 1):
up = asd.get(num)
if not up is None:
low = find_low(num, asd, minim)
asd[num] = asd[low] + asd[num]
for num in numbers:
idx = asd[num]
asd[num] -= 1
ordering[idx - 1] = num
return list(ordering)
numbers = np.random.randint(-10, 10, 10)
print(f' * Ordered : {countingSort(numbers)}')
```
Aquí la versión corta para números negativos y el cero
import numpy as np
def countingSort(numbers):
minim = min(numbers)
maxim = max(numbers)
ordering = np.zeros(numbers.shape, dtype=int)
print(f' * Numbers : {numbers}')
print(f' * lower : {minim}')
print(f' * upper : {maxim}')
asd = {}
for num in numbers:
asd[num] = asd.get(num, 0) + 1
for num in np.arange(minim, maxim + 1):
up = asd.get(num)
if up is None:
asd[num] = 0
for num in np.arange(minim + 1, maxim + 1):
up = asd[num]
asd[num] = asd[num - 1] + asd[num]
for num in numbers:
idx = asd[num]
asd[num] -= 1
ordering[idx - 1] = num
return list(ordering)
numbers = np.random.randint(-10, 10, 10)
print(f' * Ordered : {countingSort(numbers)}')