Комментарии 23
Похоже, что вы изобрели Selection Sort.
Допишу вдогонку.
Попробуйте еще глянуть такие вещи, как:
И если уж совсем заморочиться, то есть in-place bottom-up quicksort, которая обычно еще быстрее, но имеет ряд неочевидных подводных камней вроде деградации до O(N^2) на неудачных наборах данных. Впрочем, все подводные камни обходятся.
Всё это будет стоить вам O(1) по памяти.
Попробуйте еще глянуть такие вещи, как:
- Insertion Sort с O(1) на уже отсортированных данных
- Heap Sort c гарантированным O(n log n).
И если уж совсем заморочиться, то есть in-place bottom-up quicksort, которая обычно еще быстрее, но имеет ряд неочевидных подводных камней вроде деградации до O(N^2) на неудачных наборах данных. Впрочем, все подводные камни обходятся.
Всё это будет стоить вам O(1) по памяти.
1) сортируете одну очередь руками с использование свободной переменной
2) сортируете вторую очередь руками с использование свободной переменной
3) делаете слияние двух очередей
2) сортируете вторую очередь руками с использование свободной переменной
3) делаете слияние двух очередей
Недавно столкнулся с такой задачей: «Объединить две очереди таким образом, чтобы суммарная очередь была отсортирована».
Мне кажется или статья о другом
Как отсортировать очередь используя O(1) дополнительной памяти:
На каждом шаге:
Нашли максимум в очереди за O(N) (пробегаем по очереди, пропуская элементы, добавленные в п.3, всегда знаем сколько их на текущем шаге)
Удалили этот максимум из очереди за O(N) (пробегаем по очереди, пропуская элементы, добавленные в п.3, всегда знаем сколько их на текущем шаге)
Добавили его в конец очереди
Делаем N таких шагов. Итого, отсортировали за O(N^2) с доп. памятью O(1)
Остался один вопрос: что значит «пробегаем по очереди». В качестве ответа псевдокод ниже
for i = 1..q.size()
tmp = q.pop()
// do something with element
q.push(tmp)
После исполнения данного кода получаем такое же состояние очереди, как и до исполнения.
Мне кажется или статья о другом
Как отсортировать очередь используя O(1) дополнительной памяти:
На каждом шаге:
Нашли максимум в очереди за O(N) (пробегаем по очереди, пропуская элементы, добавленные в п.3, всегда знаем сколько их на текущем шаге)
Удалили этот максимум из очереди за O(N) (пробегаем по очереди, пропуская элементы, добавленные в п.3, всегда знаем сколько их на текущем шаге)
Добавили его в конец очереди
Делаем N таких шагов. Итого, отсортировали за O(N^2) с доп. памятью O(1)
Остался один вопрос: что значит «пробегаем по очереди». В качестве ответа псевдокод ниже
for i = 1..q.size()
tmp = q.pop()
// do something with element
q.push(tmp)
После исполнения данного кода получаем такое же состояние очереди, как и до исполнения.
Для этой задачи есть уже давно было придумано более изящное, на мой взгляд решение. Стандартная реализация очереди с приоритетом (ваш случай когда весами элементов являются сами элементы) отлично реализуется на структуре heap, где элементы хранятся в сплошном массиве и каждый новый элемент становится в свою позицию простыми обменами не более чем за O(log N). Собственно всем известный heapsort как раз так и реализован. Для слияния нужно просто одну очередь по-поэлементно влить в другую.
Действительно, я тоже не понял, зачем заниматься ерундой, когда очередь с приоритетами (как идея) существует не один десяток лет. С другой стороны, в силу некорректности формулировки задания, нельзя точно сказать, с каких данных мы начинаем и что считать дополнительной памятью. На месте исполнителя я требовал бы более чёткой формулировки (что именно дано и в каком виде оно перед нами изначально). Потому что если очереди уже даны в некотором виде (например, в виде списков), то я не вижу каких-то способов использовать heap без нарушения правила одной переменной, тогда придётся извращаться. Если данные даны абстрактно, то можем считать, что они даны в массиве. Дальше всё зависит от того, в одном они массиве или в двух...
Короче, обычно когда задачу формулируют именно так, я возвращаю её автору со словами "сам решай", потому что так задачи не ставятся, когда от трактовки формулировки зависит метод решения.
Кроме того, неплохо было бы понимать, для чего вообще даются подобные задачи. Одно дело для разминки, а другое, когда есть реальная необходимость экономить память. В первом случае это может представлять интерес, конечно, а во втором случае память нужно начинать экономить, например, тем, что не писать сообщения типа "queue is full!", не писать на Python и всё-таки хранить данные иначе.
Короче, обычно когда задачу формулируют именно так, я возвращаю её автору со словами "сам решай", потому что так задачи не ставятся, когда от трактовки формулировки зависит метод решения.
Кроме того, неплохо было бы понимать, для чего вообще даются подобные задачи. Одно дело для разминки, а другое, когда есть реальная необходимость экономить память. В первом случае это может представлять интерес, конечно, а во втором случае память нужно начинать экономить, например, тем, что не писать сообщения типа "queue is full!", не писать на Python и всё-таки хранить данные иначе.
Опасная конструкция:
def get_list(self):
return self.queue
Отдаете ссылку на приватный атрибут, т.е. можно изменять очередь вне класса
лучше так сделать:
return list(self.queue)
def get_list(self):
return self.queue
Отдаете ссылку на приватный атрибут, т.е. можно изменять очередь вне класса
лучше так сделать:
return list(self.queue)
Причём требование для сортировки такое: не использовать никаких промежуточных объектов, кроме одной переменной, каким бы медленным алгоритм ни был.
Так ведь steps это вторая переменная. Получается, это требование нарушено?
Получается, что так. Либо можно что-нибудь посчитать, либо запомнить (или переставить) элементы в очереди — но не одновременно.
С другой стороны, ничто не запрещает нам добавить новый пустой элемент в очередь и использовать его для сортировки пузырьком?
С другой стороны, ничто не запрещает нам добавить новый пустой элемент в очередь и использовать его для сортировки пузырьком?
Нет, ну переменные счётчика использовать можно. Главное не использовать дополнительных очередей, списков, массивов — таких вот объектов. То есть только одну промежуточную переменную можно использовать, но не больше.
Без счётчиков, но с дополнительным пустым элементом в очереди:
queue.Push(new Item());
for(;;){
for(;;){
temp=queue.Pop();
if(queue.Get()==Item.Empty) goto _1;
if(queue.Get()<=temp) break;
queue.Push(temp);
}
for(;;){
if(queue.Get()==Item.Empty){
queue.Push(temp);
queue.Push(queue.Pop());
break;
}
if(queue.Get()<temp) queue.Push(queue.Pop());
else{
queue.Push(temp);
temp=queue.Pop();
}
}
}
_1:
queue.Pop();
Почему бы не сделать проще:
Слить две очереди в одну.
Отсортировать с учетом требований.
Слить две очереди в одну.
Отсортировать с учетом требований.
На питоне можно было проще — на голых списках без создания собственного класса. list.append(x) и list.pop(0)
Ну и более чистый (имхо) код выглядит так
А можно и не вставками, а обменами
Ну и более чистый (имхо) код выглядит так
def sort(q):
n = len(q)
for k in range(1,n): # start with 1, because 1 item is always sorted
# n-k items not sorted yet, then k items sorted
x = pop(q)
# n-k-1 not sorted yet, k sorted
for i in range(n-k-1):
roll(q)
# k sorted, n-k-1 not yet
pushed = False
for i in range(k):
y = pop(q)
if not pushed and x < y:
push(q, x)
pushed = True
push(q, y)
if not pushed:
push(q, x)
# k+1 sorted (including x), n-k-1 not yetА можно и не вставками, а обменами
def sort(q):
n = len(q)
if n < 2:
return
retry = True
while retry:
retry = False
x = pop(q)
for i in range(n-1):
y = pop(q)
if x <= y:
push(q, x)
x = y
else:
push(q, y)
retry = True # reordered
push(q, x)Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сортировка очереди без использования дополнительных ресурсов