Телеграмм чат группы mediatube

Переслано от mr.slavik

можно ли выполнить сортировку массива целых uint32 например за O(n) всегда

12:51пожаловаться #1

m

Переслано от mr.slavik

пузырьковая сортировка например O(n^2)
а qsort O(nlog(n)) в лучшем случае
но они не используют доп память
а сортируют за счет перестановок
а если у тебя есть память - можно ли за O(n) отсортировать?

12:51пожаловаться #2

m

Переслано от mr.slavik

но на самом деле - если подумать то получается ведь столбцы - это по сути переменные

12:51пожаловаться #3

m

Переслано от mr.slavik

счетчики

12:51пожаловаться #4

m

Переслано от mr.slavik

так что можно свести к тому что мы выделяем массив от 0 до 255
и инкрементируем соответствующие числа
когда встречаем
ну а потом в соответствии со значениями счетчиков в конце - выписываем массив

12:51пожаловаться #5

SK

Sergey Kaluzhskiy in MediaTube HCF

индексная сортировка или как она там

12:51пожаловаться #6

SK

Sergey Kaluzhskiy in MediaTube HCF

когда значение используется как индекс

12:52пожаловаться #7

k

mr.slavik

Переслано от mr.slavik

так что можно свести к тому что мы выделяем массив от 0 до 255
и инкрементируем соответствующие числа
когда встречаем
ну а потом в соответствии со значениями счетчиков в конце - выписываем массив

Помню, я ж её написал

12:52пожаловаться #8

k

Всё, прошёл собеседование, где ты там работаешь

12:52пожаловаться #9

m

меньше чем за n сортировок не бывает

12:52пожаловаться #10

m

так что не ляпни про log(n)

12:52пожаловаться #11

k

mr.slavik

меньше чем за n сортировок не бывает

А если изначально известно, что часть уже отсортирована, то можно)

12:52пожаловаться #12

m

это значит ты сортируешь элементы не обращаясь даже к ним
так как ты к каждому как минимум 1 раз должен обратиться

12:52пожаловаться #13

m

ну если бы да кабы - обычно если не оговорено другое - данные произвольные на входе
разные структуры данных позволяют и за константу разные вещи делать

12:54пожаловаться #14

k

А есть по тому способу работать из собеседования - время же тратится на append, будет ли это выгоднее, даже при условии, что всего n операций?

Артем Кирьянов in MediaTube HCF

12:58пожаловаться #15

АК

Хорошо я DevOps)))), а то вы тут ругаетесь со своими сортировками, веревками. Выгодней будет если работа рядом с домом.