चढ़ते क्रम में एक ढेर छंटनी?

Question

के लिए आरोही क्रम में एक ढेर सॉर्टिंग करने के लिए सबसे अच्छी विधि क्या है? I इस साक्षात्कार के प्रश्न में आया, और मैं सबसे अच्छे और सबसे कुशल समाधान के लिए कुछ समस्याओं में भाग रहा था।

दो विधियां हैं जिन्हें मैं सोच सकता हूं।

1. ढेर की सभी सामग्री पॉप करने के लिए और उन्हें एक सरणी में स्टोर, और फिर
   O(nLog n) में सरणी सॉर्ट और फिर धक्का सामग्री ढेर वापस। नहीं सबसे अच्छा तरीका है ....

2. छँटाई यह

void sort(stack) 
{ 
    type x; 

    if (!isEmpty(stack)) { 
     x = pop(stack); 
     sort(stack); 
     insert(x, stack); 
    }   
} 

void insert(x, stack) 
{ 
    type y; 

    if (!isEmpty(stack) && top(stack) < x) { 
     y = pop(stack); 
     insert(x, stack); 
     push(y, stack); 
    } 
    else { 
     push(x, stack); 
    } 
} 

लेकिन 2 विधि भी कई पुनरावर्ती कॉल और भूमि के ऊपर बनाने जा रहा है के लिए ढेर के पुनरावर्ती कार्यान्वयन करें यदि स्टैक वास्तव में बड़ा होता है तो एक समस्या होगी।

क्या इस समस्या को सर्वोत्तम स्थान और समय की जटिलता के लिए बेहतर तरीके से हल करना संभव है?

इतने सारे रिकर्सिव कॉल हैं, (सबप्रोबैम्स ओवरलैपिंग), क्या यह dynamic programming समस्याओं के प्रकार के लिए एक प्रतियोगी है?

इसे हल करने का सबसे अच्छा तरीका क्या होगा? ?

Answer 1

यह एक ढेर है। आप शीर्ष मूल्य के अलावा कुछ भी नहीं देख सकते हैं। आपको कम से कम एक बार सबकुछ पॉप करना होगा, और कम से कम एक बार सब कुछ दबाएं। पहली विधि ठीक है।

यदि स्टैक ऑपरेशंस महंगे हैं लेकिन आपके पास समय सीमा है, तो आप पॉपिंग के रूप में सम्मिलन प्रकार का उपयोग करें और जैसे ही आपका अंतिम पॉप किया जाता है, आप धक्का दे सकते हैं। लेकिन आप कह रहे हैं कि यह सी ++ में है इसलिए मुझे संदेह है कि हम इस तरह के परिदृश्य पर विचार कर रहे हैं।

Answer 2

आप रिकर्सन को समाप्त कर हल कर सकते हैं। इसके लिए आप बस एक खाली होने तक एक ढेर के नीचे एक लूप का उपयोग करें।

उदाहरण के लिए

, छद्म कोड:

Linekd Stack stack = new List(); 

while stack is not empty then 

    element <- stack removes peek 

    // Recursiong 
    push new elements on stack 

end 

Answer 3

यह समस्या नहीं कर सकते जटिलता कम हे की तुलना में (एन^2) है। आगे के संदर्भ के लिए here