동일한 대기열을 사용하여 대기열 정렬

Question

나는이 질문을 받았으며, 행할 수 있다고 생각하지만, 이렇게하기 위해 알고리즘을 생각해 내는데 어려움이 있습니다. 제한 사항은 다른 데이터 구조를 사용하거나 다른 큐를 작성할 수 없다는 것입니다. 또한 enqueue, dequeue 및 peek (우선 순위 대기열이 아님) 만 사용할 수 있습니다.

고맙습니다이 :)

Answer 1

Sort(Q,n): 

    for i = 0 to n-1 
    min = findMin(Q, n-i, n) 
    reorder(Q, min, n) 
    end for 

findMin(Q, k, n): 

    min = infinity 

    for i = 1 to n 
    curr = dequeue(Q) 
    if curr < min && i<=k 
     min = curr 
    end if 
    enqueue(Q,curr) 
    end for 

    return min 

reorder(Q, min, n): 

    for i = 1 to n 
    curr = dequeue(Q) 
    if (curr != min) // I'm assuming that there is a way to differentiate between any two items, this isn't hard to enforce 
     enqueue(Q, curr) 
    end if 
    end for 

    enqueue(Q,min) 

오름차순 정렬을 기여하기위한 공간 O에서 O에서 (N^2) 시간을 실행 (1) (즉 큐 (n)은 공간 및 여유 공간 O 필요 알고리즘에 의해 O (1))

설명 :

는 본질적으로, 우리는 큐 N 번 반복 비용 2N마다 반복.

각 반복마다 대기열 전체를 살펴보고 관련 항목 수에서 최소값을 선택합니다. 그래서 우리는 최소값을 원하기 때문에 관련 항목의 수는 n입니다. 다음 반복에서는 첫 번째 n-1 개 항목의 최소값을, 그 다음 n-2 개 항목 등을 원합니다. 알고리즘은 이러한 최소값을 끝에 쌓을 것이기 때문입니다.

최소값을 찾았 으면 전체 스택을 반복하여 끝에 걸러 스택에 넣어야합니다.

여기서 핵심 아이디어는 같은 요소를 큐에 넣고 대기열에 넣고 대기열을 반복하고 순서를 유지하면서 최소값/최대 값을 확인할 수 있다는 것입니다. 큐를 사용하여

Answer 2

거품 정렬 : 당신이 할 수 있다면

가

n <- size of queue 
repeat n times 
    x <- dequeue item 
    repeat (n-1) times 
    y <- dequeue item 
    if x < y then 
     enqueue y 
    else 
     enqueue x 
     x <- y 
    enqueue x