அடுக்குகளைப் பயன்படுத்தி வரிசை வரிசைப்படுத்துதல்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் கோல்ட்மேன் சாக்ஸ் ஐபிஎம் குலிசா யாகூ
வரிசையாக்க ஸ்டேக்

சிக்கல் அறிக்கை

“அடுக்குகளைப் பயன்படுத்தி வரிசைகளை வரிசைப்படுத்துதல்” சிக்கல் உங்களுக்கு ஒரு தரவு அமைப்பு வழங்கப்படுவதாகக் கூறுகிறது வரிசை a [] அளவு n. வரிசைப்படுத்த பயன்படுத்தி கொடுக்கப்பட்ட வரிசையின் கூறுகள் ஸ்டாக் தரவு அமைப்பு.

அடுக்குகளைப் பயன்படுத்தி வரிசை வரிசைப்படுத்துதல்

உதாரணமாக

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

விளக்கம்: உறுப்புகள் ஏறுவரிசையில் வரிசைப்படுத்தப்படுகின்றன.

2 3 1 8 6
1 2 3 6 8

அடுக்குகளைப் பயன்படுத்தி வரிசைகளை வரிசைப்படுத்துவதற்கான அணுகுமுறை

கொடுக்கப்பட்ட உள்ளீட்டு வரிசையின் அனைத்து கூறுகளையும் சேமிக்க ஒரு அடுக்கு தரவு கட்டமைப்பை உருவாக்கவும் []. அதன் பிறகு, அசல் ஒன்றை வரிசைப்படுத்த மற்றொரு தற்காலிக அடுக்கை உருவாக்கவும். அசல் அடுக்கு வழியாகச் சொல்லுங்கள், ஒவ்வொரு உறுப்புக்கும் மேலே பாப் செய்து தற்காலிக மாறியில் சேமிக்கவும். இதேபோல், தற்காலிக அடுக்கின் மேல் உள்ள உறுப்பு அசல் அடுக்கின் மேல்புறத்தை விட குறைவாக இருக்கும்போது தற்காலிக அடுக்கின் வழியாக மீண்டும் இயக்கவும். அசல் அடுக்கில் தற்காலிக அடுக்கின் மேல் உறுப்பைச் செருகவும், அதை தற்காலிக அடுக்கிலிருந்து அகற்றவும். அசல் அடுக்கின் பாப் செய்யப்பட்ட மேற்புறத்தை தற்காலிக அடுக்கில் தள்ளவும். முடிவில், தற்காலிக அடுக்கில் வரிசைப்படுத்தப்பட்ட வரிசையில் கூறுகள் இருக்கும். இந்த சிக்கல் ஒரு சிறிய மாற்றமாகும் தற்காலிக அடுக்கைப் பயன்படுத்தி அடுக்கி வைக்கவும்.

அல்காரிதம்

  1. அளவு n இன் [] ஒரு வரிசையைத் தொடங்கவும்.
  2. ஒரு அடுக்கு தரவு கட்டமைப்பை உருவாக்கவும். வரிசை ஒரு [] வழியாக பயணித்து, அணியின் அனைத்து உறுப்புகளையும் ஒரு [] அடுக்கில் தள்ளுங்கள்.
  3. இதேபோல், மற்றொரு தற்காலிக அடுக்கை உருவாக்கவும்.
  4. அசல் அடுக்கின் அளவு 0 ஆக இருக்கும்போது பயணிக்கவும். ஒரு மாறி tmp ஐ உருவாக்கி, அதில் அசல் அடுக்கின் மேற்புறத்தில் உறுப்பை சேமித்து அசல் அடுக்கிலிருந்து பாப் செய்யவும்.
  5. தற்காலிக அடுக்கு காலியாக இல்லாதபோது மீண்டும் பயணிக்கவும், தற்காலிக அடுக்கின் மேற்புறத்தில் உள்ள உறுப்பை மாறி tmp ஐ விட குறைவாக இருக்கும் வரை பாப் செய்யவும். தற்காலிக அடுக்கிலிருந்து வெளியேறும் போது, ​​அசல் அடுக்கில் தற்காலிக அடுக்கின் மேல் உறுப்பை அழுத்தவும்.
  6. மாறி tmp ஐ ஒரு தற்காலிக அடுக்கில் தள்ளவும்.
  7. 0 முதல் n-1 வரை பயணித்து தற்காலிக அடுக்கின் மேல் உறுப்பை தற்போதைய குறியீட்டில் ஒரு [] வரிசையில் சேமித்து, தற்காலிக அடுக்கிலிருந்து உறுப்பை பாப் / நீக்கவும்.
  8. இறுதியாக, 0 முதல் n-1 வரை பயணித்து வரிசையை அச்சிடுங்கள் [].

குறியீடு

அடுக்குகளைப் பயன்படுத்தி வரிசைகளை வரிசைப்படுத்துவதற்கான சி ++ நிரல்

#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) n உறுப்புகளுக்கு தற்காலிக அடுக்கு இடத்தைப் பயன்படுத்தினோம். அசல் அடுக்கினால் பயன்படுத்தப்படும் இடம் வழிமுறைக்கு கணக்கிடப்படவில்லை.