ढेर का उपयोग कर छँटाई सरणी


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना गोल्डमैन सैक्स आईबीएम कुलिजा याहू
छंटाई धुआँरा

समस्या का विवरण

समस्या "स्टैक का उपयोग करके सॉर्टिंग सरणी" बताती है कि आपको डेटा संरचना दी गई है सरणी [a] आकार n। तरह दिए गए सरणी के तत्वों का उपयोग कर धुआँरा डेटा संरचना।

ढेर का उपयोग कर छँटाई सरणी

उदाहरण

2 30 -5 43 100
-5 2 30 43 100

स्पष्टीकरण: तत्वों को आरोही क्रम में क्रमबद्ध किया जाता है।

2 3 1 8 6
1 2 3 6 8

ढेर का उपयोग कर सरणी को क्रमबद्ध करने के लिए दृष्टिकोण

दिए गए इनपुट सरणी के सभी तत्वों को संग्रहीत करने के लिए स्टैक डेटा संरचना बनाएँ []। उसके बाद, मूल को छांटने के लिए एक और अस्थायी स्टैक बनाएं। मूल स्टैक के माध्यम से Iterate करें और प्रत्येक तत्व के लिए शीर्ष को पॉप करें और इसे एक अस्थायी चर में संग्रहीत करें। इसी प्रकार, अस्थायी स्टैक के माध्यम से पुनरावृति करते हैं, जबकि अस्थायी स्टैक के शीर्ष पर स्थित तत्व मूल स्टैक के पॉप्ड टॉप से ​​कम होता है। मूल स्टैक में अस्थायी स्टैक के शीर्ष तत्व को डालें और इसे अस्थायी स्टैक से हटा दें। अस्थायी स्टैक में मूल स्टैक के शीर्ष पर पॉपअप पुश करें। अंत में, अस्थायी स्टैक में सॉर्ट किए गए क्रम में तत्व शामिल होंगे। यह समस्या एक तरह से मामूली संशोधन है अस्थायी स्टैक का उपयोग करना.

कलन विधि

  1. आकार n की एक सरणी [] को आरम्भ करें।
  2. स्टैक डेटा संरचना बनाएँ। सरणी [] के माध्यम से पार करें और ढेर में सरणी [] के सभी तत्वों को धक्का दें।
  3. इसी तरह, एक और अस्थायी स्टैक बनाएं।
  4. पारगमन जबकि मूल स्टैक का आकार 0. नहीं है। एक वैरिएबल टीएमपी बनाएं और उसमें मूल स्टैक के शीर्ष पर तत्व को संग्रहीत करें और इसे मूल स्टैक से पॉप करें।
  5. फिर से पीछे की ओर जबकि अस्थायी स्टैक खाली नहीं है और अस्थायी स्टैक के शीर्ष पर तत्व को तब तक पॉप करें जब तक कि यह वैरिएबल टैम्प से कम न हो। अस्थायी स्टैक से पॉपिंग करते समय, मूल स्टैक में अस्थायी स्टैक के शीर्ष तत्व को धक्का दें।
  6. एक अस्थायी ढेर में चर tmp पुश।
  7. 0 से n-1 तक के पार और वर्तमान सूचकांक पर [[] सरणी में अस्थायी स्टैक के शीर्ष तत्व को स्टोर करें और अस्थायी स्टैक से तत्व को हटा दें।
  8. अंत में, 0 से n-1 तक ट्रैव करें और सरणी को प्रिंट करें []।

कोड

ढेर का उपयोग करके सरणी को क्रमबद्ध करने के लिए C ++ प्रोग्राम

#include <iostream>
#include <stack> 
using namespace std; 
  
stack<int> sortStack(stack<int> input){ 
    stack<int> tmpStack; 
    while(!input.empty()){ 
        int tmp = input.top(); 
        input.pop(); 
  
        while (!tmpStack.empty() && tmpStack.top() < tmp){ 
            input.push(tmpStack.top()); 
            tmpStack.pop(); 
        } 
  
        tmpStack.push(tmp); 
    } 
  
    return tmpStack; 
} 
  
void sortUsingStack(int arr[], int n){ 
     
    stack<int> input; 
    for(int i=0; i<n; i++){ 
       input.push(arr[i]); 
    }
  
    stack<int> tmpStack = sortStack(input); 
  
    for(int i=0; i<n; i++){ 
        arr[i] = tmpStack.top(); 
        tmpStack.pop(); 
    } 
} 
  
int main(){ 
    int a[] = {2, 30, -5, 43, 100}; 
    int n = sizeof(a)/sizeof(a[0]); 
  
    sortUsingStack(a, n); 
  
    for(int i=0; i<n; i++) 
       cout << a[i] << " "; 
  
    return 0; 
}
-5 2 30 43 100

ढेर का उपयोग करके सरणी को क्रमबद्ध करने के लिए जावा प्रोग्राम

import java.io.*; 
import java.util.*; 
  
class SortArrayWithStack{ 
    
    static Stack<Integer> sortStack(Stack<Integer> input){ 
        Stack<Integer> tmpStack = new Stack<Integer>(); 
      
        while(!input.empty()){ 
            int tmp = input.peek(); 
            input.pop(); 
      
            while(!tmpStack.empty() && tmpStack.peek() < tmp){ 
                input.push(tmpStack.peek()); 
                tmpStack.pop(); 
            } 
      
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    static void sortUsingStack(int []arr, int n){ 
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        for(int i = 0; i < n; i++){ 
            input.push(arr[i]); 
        }
      
        Stack<Integer> tmpStack = sortStack(input); 
      
        for(int i = 0; i < n; i++){ 
            arr[i] = tmpStack.peek(); 
            tmpStack.pop(); 
        } 
    } 
      
    public static void main(String args[]){
        
        int []a = {2, 30, -5, 43, 100};
        int n = a.length; 
      
        sortUsingStack(a, n); 
      
        for(int i = 0; i < n; i++){ 
            System.out.print(a[i] + " "); 
        }    
    } 
}
-5 2 30 43 100

जटिलता विश्लेषण

समय जटिलता

O (n ^ 2) जहाँ n ढेर में तत्वों की संख्या है। चूंकि हम अस्थायी स्टैक से वापस मूल स्टैक तक तत्वों को वापस ला रहे हैं, तो अस्थायी स्टैक के शीर्ष को धक्का दिए जाने वाले तत्व की तुलना में कम है। बेहतर समझ के लिए, एक अवरोही क्रम अनुक्रम पर विचार करें और एल्गोरिथ्म को चलाने का प्रयास करें।

अंतरिक्ष जटिलता

पर) क्योंकि हमने n तत्वों के लिए अस्थायी स्टैक स्पेस का उपयोग किया है। एल्गोरिथ्म के लिए मूल स्टैक द्वारा उपयोग किए जाने वाले स्थान की गणना नहीं की जाती है।