Сортування черзі без використання додаткових ресурсів

Нещодавно зіткнувся з таким завданням: «Об'єднати дві черги таким чином, щоб сумарна чергу була відсортована». Причому вимога для сортування таке: не використовувати ніяких проміжних об'єктів, крім однієї змінної, яким би повільним алгоритм не був. Перші спроби скласти алгоритм сортування черзі приводили до питання про те, як вийти з нескінченного циклу, але в кінцевому підсумку я отримав необхідний алгоритм, про який і піде мова.

Для початку визначимо реалізацію черзі, я зроблю це на мові Python, використовуючи стандартні списки:

class EmptyQueueError(Exception):
@staticmethod
def message():
return 'queue is empty!'


class FullQueueError(Exception):
@staticmethod
def message():
return 'queue is full!'


class Queue:
def __init__(self, max_size=None):
self.__queue = []
self.__max_size = max_size

def get_size(self):
return len(self.__queue)

def get_list(self):
return self.__queue

def push(self, item):
if len(self.__queue) != self.__max_size or self.__max_size is None:
self.__queue.append(item)
else:
raise FullQueueError

def pop(self):
if len(self.__queue):
item = self.__queue[0]
del self.__queue[0]
return item
else:
raise EmptyQueueError

def get_head(self):
if len(self.__queue):
return self.__queue[0]
else:
raise EmptyQueueError

Набір методів самий стандартний. Чергу може бути фіксованого розміру, тоді в конструктор потрібно передати числовий параметр, що визначає розмір, в іншому випадку чергу вийде нескінченною. Метод get_list() небезпечний, оскільки повертає посилання на внутрішній список, і зміна його ззовні зовсім не рекомендується. Але для налагодження він може стати в нагоді.

За контроль порожнечі/повноти черзі відповідають класи винятків EmptyQueueError та FullEmptyError відповідно.

Ну а тепер перейдемо до найцікавішого — сортування черги. Сортування відбувається від найменшого елемента до більшого. Ми маємо можливість використовувати одну змінну для тимчасового зберігання елемента з черги. Також в нашому розпорядженні є метод get_head(), який просто повертає елемент з голови черги. Основа алгоритму сортування полягає в тому, що ми поміщаємо в змінну temp черговий елемент, використовуючи метод pop(). Далі в циклі ми будемо порівнювати голову черги з цим temp, і якщо головний елемент виявиться більше, то поміщаємо temp в кінець черги, а потім присвоюємо йому наступний елемент з голови (pop()). Якщо ж головний елемент виявиться не більше, то поміщаємо його в хвіст, а temp не чіпаємо, тобто робимо «перемотування» черги на один елемент.

Але питання: коли цикл слід зупинити?

Коли алгоритм знаходить максимум, необхідно прокрутити чергу повністю, щоб упевнитися, що в черзі немає більшого значення. Значить, промотка повинна виконуватися стільки разів, скільки елементів знаходиться в черзі. Для цього потрібна змінна лічильника (steps). Після промотки можна сміливо заштовхнути в чергу temp і повторити операцію.

А у разі знаходження нового максимуму в черзі скидаємо лічильник промотки в 0.

Так що спочатку вважаємо steps = 0, і якщо наступний максимум не виявлено, збільшуємо на 1.

Але так як після виконання цього циклу чергу навряд чи отсортируется, необхідно повторити операцію стільки разів, скільки елементів у черзі без одного, тобто длина_очереди — 1.

def my_sorting(queue):
for i in range(queue.get_size() - 1):
temp = queue.pop()
steps = 0

while steps < queue.get_size():
print(temp, queue.get_list())

if temp < queue.get_head():
queue.push(temp)
temp = queue.pop()
steps = 0
else:
queue.push(queue.pop())
steps += 1

queue.push(temp)

print(queue.get_list())

return queue

Результат: черга відсортована без використання додаткових ресурсів.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.