- 1
IT Оффтоп #233
Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
0
IT Оффтоп #233
#203: https://govnokod.ru/28954 https://govnokod.xyz/_28954
#204: https://govnokod.ru/28971 https://govnokod.xyz/_28971
#205: https://govnokod.ru/28986 https://govnokod.xyz/_28986
#206: https://govnokod.ru/28991 https://govnokod.xyz/_28991
#207: https://govnokod.ru/29002 https://govnokod.xyz/_29002
#208: https://govnokod.ru/29060 https://govnokod.xyz/_29060
#209: https://govnokod.ru/29070 https://govnokod.xyz/_29070
#210: https://govnokod.ru/29079 https://govnokod.xyz/_29079
#211: https://govnokod.ru/29092 https://govnokod.xyz/_29092
#212: https://govnokod.ru/29093 https://govnokod.xyz/_29093
#213: https://govnokod.ru/29104 https://govnokod.xyz/_29104
#214: https://govnokod.ru/29114 https://govnokod.xyz/_29114
#215: https://govnokod.ru/29125 https://govnokod.xyz/_29125
#216: https://govnokod.ru/29132 https://govnokod.xyz/_29132
#217: https://govnokod.ru/29147 https://govnokod.xyz/_29147
#218: https://govnokod.ru/29156 https://govnokod.xyz/_29156
#219: https://govnokod.ru/29166 https://govnokod.xyz/_29166
#220: https://govnokod.ru/29181 https://govnokod.xyz/_29181
#221: https://govnokod.ru/29185 https://govnokod.xyz/_29185
#222: https://govnokod.ru/29190 https://govnokod.xyz/_29190
#223: https://govnokod.ru/29203 https://govnokod.xyz/_29203
#224: https://govnokod.ru/29211 https://govnokod.xyz/_29211
#225: https://govnokod.ru/29212 https://govnokod.xyz/_29212
#226: https://govnokod.ru/29218 https://govnokod.xyz/_29218
#227: https://govnokod.ru/29220 https://govnokod.xyz/_29220
#228: https://govnokod.ru/29230 https://govnokod.xyz/_29230
#229: https://govnokod.ru/29235 https://govnokod.xyz/_29235
#230: https://govnokod.ru/29241 https://govnokod.xyz/_29241
#231: https://govnokod.ru/29246 https://govnokod.xyz/_29246
#232: https://govnokod.ru/29249 https://govnokod.xyz/_29249
0
Counting Sort - O(n + k)
Counting Sort O(n + k) O(n + k) O(n + k) O(k) ✅ Маленький диапазон значений
def counting_sort(nums):
count = defaultdict(int)
minVal, maxVal = min(nums), max(nums)
for val in nums:
count[val] += 1
index = 0
for val in range(minVal, maxVal + 1):
while count[val] > 0:
nums[index] = val
index += 1
count[val] -= 1
from collections import defaultdict
def stable_counting_sort(nums):
if not nums:
return nums
# 1. Считаем сколько раз встретилось каждое число
count = defaultdict(int)
for val in nums:
count[val] += 1
# 2. Получаем отсортированные ключи
sorted_keys = sorted(count.keys())
# 3. Считаем префиксные суммы (позиции для стабильности)
positions = {}
total = 0
for key in sorted_keys:
positions[key] = total
total += count[key]
# 4. Создаём массив результата
output = [0] * len(nums)
for val in nums:
index = positions[val]
output[index] = val
positions[val] += 1 # увеличиваем позицию для следующего одинакового элемента
return output