Сортировка очереди с другой очередью

Question

Как я могу сортировать очередь размера N, используя только очередную очередь размера N и конечное число переменных?

наивная реализация - поиск минимума очереди и толкание ее в пустую очередь, затем поиск нового минимального и нажатие и т. Д. O (n^2). есть ли более эффективный алгоритм?

Answer 1

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

Единственный способ, которым я могу думать, это: Держать вторую очередь отсортированной всегда. 1. Удалить элемент из q1. 2. Если этот элемент> = последний элемент q2, вставьте его в q2. (Таким образом, q2 все еще сортируется). 3. Еще раз, верните его в q1. Продолжайте повторять вышеуказанные шаги до тех пор, пока q1 не будет пустым.

Answer 2

мой алго:

let the Q size = n, 
1 save = getRearValue(1stQ) 
2 pop the element from 1st Q and insert it into 2nd Q. 
3 if getFrontValue(1stQ) > getRearValue(2ndQ) 
4  then goto step 2. 
5 else 
6  pop the element from 1st Q and insert back into the same Q (1st Q). 
7  if (save != getRearValue(1stQ)) goto step 3. 
8 if (1st Q not sorted OR getFrontValue(1stQ) > getFrontValue(2ndQ)) 
9   then 
10   pop all elements of 2nd Q and insert into 1st Q (One by one). 
11   goto step 1. 
12 else 
13  pop all elements of 2nd Q and insert into 1st Q (One by one). 
14  return 1stQ 

Answer 3

Вот простая логика, что я придумал из верхней части моей головы. Наихудшим временем выполнения будет O (N^2), в идеале лучшим может быть O (N). Я думаю, что сложность может быть дополнительно уменьшена с помощью импровизированной логики.

Синтаксис Javascript, но хорошо прокомментирован, чтобы быть понятным.

Надеюсь, это поможет.

// SORT A QUEUE USING ANOTHER QUEUE 
function sortQueueUsingQueue(uq) { 
    // instantiate required variables 
    var sq = new Queue(); 
    var t = null, last = null; 
    // copy the items to a temp queue 
    // so as not to destroy the original queue 
    var tq = new Queue(uq); 
    // loop until input is not empty 
    while(!tq.isEmpty()) { 
     t = tq.dequeue(); 
     if (last && last <= t) { 
      // new element will be at the end of the queue, and we don't have to 
      // process any further - short-circuit scenario 
      // this is the best case scenario, constant time operation per new item 
      sq.enqueue(t); 
      // also keep track of the last item in the queue, 
      // which in this case is the new item 
      last = t; 
     } else { 
      // other scenario: linear time operation per new item 
      // new element will be somewhere in the middle (or beginning) so, 
      // take elements from the beginning which are less or equal to new item, 
      // and put them at the back 
      while(!sq.isEmpty() && sq.peek() <= t) { 
       sq.enqueue(sq.dequeue()); 
      } 
      // when that is done, now put the new element into the queue, 
      // i.e the insertion into the proper place 
      sq.enqueue(t); 
      // following which, shift the rest elements to the back of the queue, 
      // to reconstruct the sorted order, 
      // thus always keeping the second queue sorted per insertion 
      while(sq.peek() > t) { 
       // meanwhile, also keep a track of the last (highest) item in the queue 
       // so that we may perform a short-circuit if permitted 
       last = sq.dequeue(); 
       sq.enqueue(last); 
      } 
     } 

    } 
    return sq; 
} 

Вы можете просмотреть весь рабочий код в GitHub сути здесь: https://gist.github.com/abhishekcghosh/049b50b22e92fefc5124

Answer 4

Вот метод, который я думаю, может работать: -

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

Предположим, что мы имеем функцию 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(Q,front); // sort the remaining queue. 

int sorted_front = Q.front(); //get front element of sorted queue 
if(element<sorted_front){ 

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

} 
else{ 
    // dequeue all elements from the queue which are lesser than element and put it into new queue. 
    // Then enqueue the new element 
    // Then enqueue whatevers bigger than element into the queue. 

     Q2.enqueue(sorted_front); 
     Q.dequeue(); 

     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; 

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

Если бы у нас был вход как 6-> 4-> 9> 2-> 1, результатом будет 9-> 6-> 4-> 2-> 1.