एक ही कतार

Question

का उपयोग कर कतार को सॉर्ट करना मुझे यह प्रश्न पूछा गया है और मुझे लगता है कि यह करने योग्य है, हालांकि मुझे ऐसा करने के लिए एक एल्गोरिदम के साथ कठिन समय आ रहा है। प्रतिबंध यह है कि आप किसी भी अन्य डेटा संरचना का उपयोग नहीं कर सकते हैं और न ही एक और कतार बना सकते हैं। इसके अलावा आप केवल एनक्यू, डेक्यू और पिक (प्राथमिकता कतार नहीं) का उपयोग कर सकते हैं।

Thanx :)

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) 

आरोही तरह योगदान के लिए, हे में (एन^2) समय, स्थान हे में चलता है (1) (यानी कतार हे है (एन) जगह है, और अतिरिक्त जगह की आवश्यकता एल्गोरिथ्म द्वारा हे है (1))

स्पष्टीकरण:

अनिवार्य रूप से, हम कतार n बार, हर समय यात्रा लागत 2n के माध्यम से पुनरावृति।

प्रत्येक पुनरावृत्ति पर, हम पूरी कतार के माध्यम से जाते हैं और न्यूनतम संख्या में वस्तुओं को चुनते हैं। तो सबसे पहले वस्तुओं की प्रासंगिक संख्या n है, क्योंकि हम उनमें से कम से कम चाहते हैं। अगली पुनरावृत्ति हम न्यूनतम एन -1 आइटम, और फिर एन -2 आइटम आदि का न्यूनतम चाहते हैं। चूंकि एल्गोरिदम अंत में इन न्यूनतम सीमाओं को ढेर करेगा।

एक बार हमें न्यूनतम मिला, तो हमें इसे छीनने और अंत में इसे ढेर करने के लिए फिर से पूरे ढेर पर फिर से शुरू करने की आवश्यकता है।

यहां मुख्य विचार यह है कि उसी तत्व के एक एनक्यू के बाद एक डेक्यू हमें कतार पर फिर से चालू करने और आदेश को संरक्षित करते समय न्यूनतम/अधिकतम जांचने की अनुमति देगा।

Answer 2

BubbleSort एक कतार का उपयोग कर:

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