대기열을 다른 대기열로 정렬

Question

크기 N의 대기열과 크기가 다른 대기열을 사용하여 크기가 N 인 대기열을 정렬하려면 어떻게해야합니까?

순진한 구현 - 대기열의 최소값을 찾고 빈 대기열로 밀어 넣은 다음 새로운 최소값을 찾고 밀어 넣는 등 O (n^2)입니다. 더 효율적인 알고리즘이 있습니까?

Answer 1

순진한 구현이 효과가 없을 것이라고 생각합니다. 그것은 큐이므로, 큐의 끝에 있지 않으면 가장 작은 요소를 제거 할 수 없습니다.

내가 생각할 수있는 유일한 방법은 다음과 같습니다. 항상 2 번째 큐를 정렬하십시오. 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

는 여기가 작동 할 수 있습니다 생각하는 방법이다 : -

알고리즘은 큐를 정렬하는 재귀를 사용합니다. 때 우리 처음

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); 

} 

} 
} 

- :

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(); 
    } 

} 

주요 분류 기능 도시로 -이 :

우리는 다음과 같이 다른 큐에 걸쳐 하나의 큐 복사 할 수있는 기능 copy_from이 있다고 가정 sort 함수를 호출하면 다음과 같이 호출 할 수 있습니다. -

Queue Q, Q2; 

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

6> 4-> 9> 2-> 1이면 결과는 9 -> 6-> 4-> 2-> 1이됩니다.