მასივის დალაგება სტეკების გამოყენებით  


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Goldman Sachs IBM კულიზა Yahoo
დახარისხება დასტის

პრობლემის განცხადება  

პრობლემა "მასივის დახარისხება სტეკების გამოყენებით" აცხადებს, რომ თქვენ გეძლევათ მონაცემთა სტრუქტურა მასივი a [] ზომა n. დალაგება მოცემული მასივის ელემენტები გამოყენებით დასტის მონაცემთა სტრუქტურა.

მასივის დალაგება სტეკების გამოყენებითPin

მაგალითი  

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

განმარტება: ელემენტები დალაგებულია ზრდადობით.

2 3 1 8 6
1 2 3 6 8

მასივის დახარისხების მიდგომა Stacks– ის გამოყენებით  

შექმენით მონაცემთა დასტის სტრუქტურა მოცემული შეყვანის მასივის ყველა ელემენტის შესანახად a []. ამის შემდეგ, შექმენით კიდევ ერთი დროებითი დასტა ორიგინალის დასალაგებლად. გაიმეორეთ ორიგინალი სტეკი და თითოეული ელემენტისთვის გამოდით ზედა ნაწილში და შეინახეთ იგი დროებით ცვლადში. ანალოგიურად, გაიმეორეთ დროებითი დასტის საშუალებით, ხოლო დროებითი დასტის თავზე არსებული ელემენტი ნაკლებია, ვიდრე თავდაპირველი დასტის გამოჩენილი ზედა. ჩადეთ დროებითი დასტის ზედა ელემენტი თავდაპირველ სტეკში და ამოიღეთ იგი დროებითი დასტისგან. ჩაუშვით ორიგინალი დასტის ჩამოსხმული ზედა დროებითი დასტა. საბოლოო ჯამში, დროებითი დასტა შეიცავს ელემენტებს დალაგების მიზნით. ეს პრობლემა არის მცირედი ცვლილებები a ტიპის მიხედვით დასტის დროებითი დასტის გამოყენებით.

ალგორითმი  

  1. Ar [] ზომის n მასივის ინიციალიზაცია.
  2. შექმენით მონაცემთა დასტის სტრუქტურა. გადაკვეთეთ a [] მასივიდან და დააჭირეთ მასივის a [] ყველა ელემენტს დასტაში.
  3. ანალოგიურად, შექმენით კიდევ ერთი დროებითი დასტა.
  4. გადაკვეთა, ხოლო ორიგინალი სტეკის ზომა არ არის 0. შექმენით ცვლადი tmp და შეინახეთ მასში ორიგინალი სტეკის ზედა ნაწილში არსებული ელემენტი და გამოუშვით ორიგინალი სტეკიდან.
  5. დროებითი სტეკი ცარიელი არ არის და კვლავ გაიტანეთ დროებითი დასტის ზედა ნაწილში ელემენტი, სანამ ის არ იქნება tmp ცვლადზე ნაკლები. დროებითი დასტისგან გამოსვლისას, დააყენეთ დროებითი დასტის ზედა ელემენტი თავდაპირველ სტეკში.
  6. დააყენეთ ცვლადი tmp დროებითი დასტისკენ.
  7. გაიარეთ 0 – დან n – 1 – მდე და შეინახეთ დროებითი სტეკის ზედა ელემენტი მასივში [] მიმდინარე ინდექსში და ამოიღეთ / წაშალეთ ელემენტი დროებითი დასტიდან.
  8. დაბოლოს, გადაკვეთეთ 0-დან n-1-მდე და დაბეჭდეთ მასივი a [].
იხილეთ ასევე
იპოვნეთ სამი სტეკის მაქსიმალური ტოლი ტოლი ჯამი

კოდი  

C ++ პროგრამა მასივის დახარისხებისთვის Stacks– ის გამოყენებით

#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

Java პროგრამა მასივის დასალაგებლად Stacks– ის გამოყენებით

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 არის ელემენტთა რაოდენობა სტეკში. მას შემდეგ, რაც ჩვენ ვაძვრებით ელემენტებს დროებითი დასხიდან თავდაპირველ სტეკზე, იმ შემთხვევაში, თუ დროებითი დასტის ზემო მხარე უფრო მცირეა ვიდრე განდევნის ელემენტი. უკეთესი გაგებისთვის, გაითვალისწინეთ დაღმავალი მიმდევრობის თანმიმდევრობა და შეეცადეთ გაუშვათ ალგორითმი.

სივრცის სირთულე

O (n) რადგან ჩვენ ვიყენეთ დროებითი დასტის სივრცე n ელემენტისთვის. ორიგინალი სტეკის მიერ გამოყენებული სივრცე არ ითვლება ალგორითმისთვის.