Сортировка очереди с помощью рекурсии

Question

Вопрос такой:

Вам нужно отсортировать очередь новым методом-членом void sort(), который вы добавляете в очередь.

Правила таковы:

• Вы не можете использовать любые петли. Допускается только рекурсия.
• Вы можете создать столько приватных методов, сколько пожелаете.
• Вы можете создавать и использовать две вспомогательные очереди одного вида (назовите это Queue - имеет конструктор по умолчанию).
• Вы ничего не знаете о внутренней структуре очереди.
• Вам даны только следующие методы: bool empty(), Data peek(), Data dequeue(), void enqueue(Data d)
• dequeue() возвращает ноль, если список пуст, enqueue() игнорирует нулевые значения.
• Порядок сортировки должен быть возрастающим (передняя часть очереди должна иметь наименьшее значение).
• Сравнимое значение находится в целых числах внутри структуры Data, называемой x.

Я знаю, что это можно решить. Я еще не нашел ответ на это. Любые идеи будут оценены.

Answer 1

Начать сортировку очереди из N = 2 элементов.

Теперь - после решения этой проблемы - улучшите решение для сортировки N + 1 элементов, если N элементов отсортированы.

---

update:

Теперь, после того как вы решилидомашнее задание, я могу показать альтернативное решение в Scala:

   private def insert (a: Int): Unit = {
     if (isEmpty || a <= peek) enqueue (a)
     else {
       val h = dequeue 
       insert (a)
       enqueue (h)
     }
   }

   def sort (): Unit = 
    if (! isEmpty) {
      val head = dequeue
      sort 
      insert (head)
    }

Это работает без явной второй очереди.Вставка является сортированной вставкой.

val q = new Queue (List (4))
q.enqueue (7)
q.enqueue (9)
q.enqueue (8)
q.enqueue (2)
q.enqueue (3)

val x = q.debug 
x: List[A] = List(3, 2, 8, 9, 7, 4)

q.sort 
val x = q.debug 
x: List[A] = List(2, 3, 4, 7, 8, 9)

Я использовал List для реализации очереди, но использую его только для создания новой очереди и в целях отладки.Избегать этого не будет большой проблемой, но это было быстрее, и я хотел начать с сортировки.:)

Answer 2

Прежде всего, спасибо за ответы.Они указали мне на правильное решение.Я проголосовал за них, чтобы отдать должное, но, поскольку мне удалось решить этот вопрос, я приму свой собственный ответ (по крайней мере, пока не придет лучший).

Итак, прежде всего, домашняя работа была о "Такси "(вы знаете, как домашняя работа ...) и TaxiQueue на Java.

Решение было:

public void sort() {
    sort(this);
}

private void sort(TaxiQueue toSort) {
    // Prepare split parts for later merging   
    TaxiQueue m1 = new TaxiQueue(), m2 = new TaxiQueue();

    // Return if there's only 1 element in the queue
    // since it's essentially "sorted".
    if(singleItem(toSort))
        return;

    // Split toSort into 2 parts
    split(toSort, m1, m2);
    // Sort each part recursively (by splitting and merging)
    sort(m1);
    sort(m2);
    // Merge each part into 1 sorted queue
    merge(toSort,  m1, m2);
}

private boolean singleItem(TaxiQueue tq) {
    Taxi temp = tq.dequeue();
    boolean retVal = tq.empty();
    tq.enqueue(temp);
    return retVal;
}

private void merge(TaxiQueue toSort, TaxiQueue m1, TaxiQueue m2) {
    // Notice that m1 and m2 are already sorted, and now we need
    // to merge them.
    // In the case that one of them is empty and the other one isn't,
    // simply append all remaining "higher" values into toSort.
    if(m1.empty()) {
        appendQueue(m2, toSort);
        return;
    }
    else if (m2.empty()) {
        appendQueue(m1, toSort);
        return;
    }
    // The critical comparison part...
    if(m1.peek().getId() < m2.peek().getId())
        toSort.enqueue(m1.dequeue());
    else
        toSort.enqueue(m2.dequeue());
    // Continue merging elements into toSort.
    merge(toSort, m1, m2);
}

// Split toSort into m1 and m2 as equally as possible
private void split(TaxiQueue toSort, TaxiQueue m1, TaxiQueue m2) {
    if(toSort.empty())
        return;
    m1.enqueue(toSort.dequeue());
    split(toSort,  m2, m1);
}

// Enqueue everything in src to dest.
private void appendQueue(TaxiQueue src, TaxiQueue dest) {
    if (src.empty())
        return;
    dest.enqueue(src.dequeue());
    appendQueue(src, dest);
}

Я надеюсь, что другие студенты могут найти это полезным в один прекрасный день!

Answer 3

посмотрите на сортировку слиянием.Он был использован для сортировки данных на лентах.Я полагаю, что вы можете принять его за очередь.

Answer 4

Следующий метод будет направлен на решение этой проблемы с использованием только одной дополнительной очереди.

Алгоритм использует Recursion для сортировки очереди.

Предположим, у нас есть функция copy_from, которая может копировать из одной очереди в другую очередь следующим образом: -

  void copy_from (ArrayQueue&Q_from,ArrayQueue& Q_to){

       while(!Q_from.empty()){

       int t= Q_from.front();
       Q_to.enqueue(t);
       Q_from.dequeue();
     }
  }

Основная функция сортировки выглядит так: -

void sort(ArrayQueue &Q, int element, ArrayQueue& Q2){

if(Q.size()==1){

    if(Q.front()>element){

         int front = Q.front();
         Q.dequeue();
         Q.enqueue(element);
         Q.enqueue(front);      
    }
    else{
        Q.enqueue(element);
    }

}
else{

 int front = Q.front();
 Q.dequeue();
 sort_v2(Q,front,Q2);

 int sorted_front = Q.front();
 if(element<sorted_front){

    Q2.enqueue(element);
    copy_from(Q,Q2);
    copy_from(Q2,Q);     

 }
 else{

      Q2.enqueue(sorted_front);
      Q.dequeue();
      //push into Q2 those elements which are smaller than element in Q.
      while(!Q.empty()&&Q.front()<element){
         Q2.enqueue(Q.front());
         Q.dequeue();
      }

      Q2.enqueue(element);
      copy_from(Q,Q2);
      copy_from(Q2,Q);

 }

}
}

Когда мы первоначально вызываем функцию сортировки, мы можем вызвать ее следующим образом: -

 Queue Q, Q2; //Assume Q is the queue we want to sort and Q2 is an empty queue.
int front = Q.front();
Q.dequeue();
sort(Q,front,Q2);

Answer 5

@ Ям Маркович: Ваш ответ в порядке. Хотя в итоге вы создаете столько очередей, сколько есть элементов в исходной очереди. Может быть, это то, что вы не хотели бы делать. Вместо этого вы можете попробовать более простой подход, когда вам нужно будет создать всего 2 новые очереди (назовите их originalQ, Q1, Q2).

Я опишу рекурсивный шаг.

• Предположим, что в Q1 уже отсортировано n1 элементов.
• пусть новый элемент из originalQ будет s. Если s не может быть правильно размещен в Q одной операцией постановки в очередь, тогда продолжайте выталкивать элементы из Q1 (сравните их с s) и поместите их правильно в Q2
• Теперь ваш Q2 отсортирован по n1 + 1 элементам, Q1 пуст. originalQ имеет на один элемент меньше. Продолжайте повторять вышеописанные шаги.