තාවකාලික තොගයක් භාවිතයෙන් තොගයක් වර්ග කරන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් ගෝල්ඩ්මන් සැක්ස් IBM ආයතනය කුලීසා යාහූ
වර්ග කිරීම අඩුක්කුව

ගැටළු ප්රකාශය

“තාවකාලික තොගයක් භාවිතයෙන් තොගයක් වර්ග කරන්න” යන ගැටලුවේ සඳහන් වන්නේ ඔබට ලබා දී ඇති බවයි අඩුයි දත්ත ව්‍යුහය. ලබා දී ඇති තොගයේ මූලද්‍රව්‍ය තාවකාලික තොගයක් ලෙස වර්ග කරන්න.

තාවකාලික තොගයක් භාවිතයෙන් තොගයක් වර්ග කරන්න

උදාහරණයක්

9 4 2 -1 6 20
20 9 6 4 2 -1
2 1 4 3 6 5
6 5 4 3 2 1

උදාහරණයක් ලෙස

Stack = [9 4 2 -1 6 20] සහ තාවකාලික සිරස් = []

Steps for sorting -
1.Top of stack = 20
Stack = [9 4 2 -1 6]
Temporary stack = [20]

2. Top of stack = 6
Stack = [9 4 2 -1 20]
Temporary stack = [6]

3. Top of stack = 20
Stack = [9 4 2 -1]
Temporary stack = [6 20]

4. Top of stack = -1
Stack = [9 4 2 20 6]
Temporary stack = [-1]

5. Top of stack = 6
Stack = [9 4 2 20]
Temporary stack = [-1 6]

6. Top of stack = 20
Stack = [9 4 2]
Temporary stack = [-1 6 20]

7. Top of stack = 2
Stack = [9 4 20 6]
Temporary stack = [-1 2]

8. Top of stack = 6
Stack = [9 4 20]
Temporary stack = [-1 2 6]

9. Top of stack = 20
Stack = [9 4]
Temporary stack = [-1 2 6 20]

10. Top of stack = 4
Stack = [9 20 6]
Temporary stack = [-1 2 4]

11. Top of stack = 6
Stack = [9 20]
Temporary stack = [-1 2 4 6]

12. Top of stack = 20
Stack = [9]
Temporary stack = [-1 2 4 6 20]

13. Top of stack = 9
Stack = [20]
Temporary stack = [-1 2 4 6 9]

14. Top of stack = 20
Stack = []
Temporary stack = [-1 2 4 6 9 20]

තොගය හිස්ව ඇති අතර තාවකාලික තොගය වර්ග කර ඇති බැවින්, එහි ඉහළ සිට ආරම්භ වන තාවකාලික තොගය මුද්‍රණය කරන්න.

එබැවින් නිමැවුම්: 20 9 6 4 2 -1

තාවකාලික තොගයක් භාවිතා කරමින් තොගයක් වර්ග කිරීමට ඇල්ගොරිතම

  1. තොග දත්ත ව්‍යුහයක් ආරම්භ කර එහි ඇති අංග ඇතුළු කරන්න / තල්ලු කරන්න.
  2. ඊට පසු ශ්‍රිත වර්ගයක් සාදන්න () එය පරාමිතියක් ලෙස තොගයක් පිළිගනී. එහි තවත් තාවකාලික / සහායක තොගයක් tmpStack ආරම්භ කරන්න.
  3. මුල් තොගය හිස් නොවන අතර ගමන් කරන්න, විචල්ය tmp එකක් සාදා එහි මුල් තොගයේ මුදුන ගබඩා කරන්න. ඊට පසු මුල් තොගයේ මුදුන පොප් කරන්න.
  4. TmpStack හිස් නොවන අතර tmpStack හි මුදුන එනම් තාවකාලික තොගය විචල්ය tmp ට වඩා අඩු හෝ සමාන නොවේ නම්, මුල් තොගයේ තාවකාලික තොගයේ ඉහළට තල්ලු කර තාවකාලික තොගයේ ඉහළට පොප් කරන්න.
  5. තාවකාලික තොගයේ විචල්ය tmp තල්ලු කරන්න.
  6. තාවකාලික තොගය හිස් නොවූවත්, එය ඉහළින් මුද්‍රණය කර එහි ඉහළට පොප් කරන්න.

කේතය

පුනරාවර්තනය භාවිතා කරමින් තොගයක් වර්ග කිරීම සඳහා සී ++ වැඩසටහන

#include <iostream> 
#include <stack>
using namespace std; 
  
stack<int> sort(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; 
} 
  
int main(){ 
    stack<int> input; 
    
    input.push(20); 
    input.push(6); 
    input.push(-1); 
    input.push(2); 
    input.push(4); 
    input.push(9); 
  
    stack<int> tmpStack = sort(input); 
    
    while (!tmpStack.empty()){ 
        cout << tmpStack.top()<< " "; 
        tmpStack.pop(); 
    } 
}
20 9 6 4 2 -1

පුනරාවර්තනය භාවිතා කරමින් තොගයක් වර්ග කිරීමට ජාවා වැඩසටහන

import java.util.*; 
  
class SortStack{ 
    
    public static Stack<Integer> sort(Stack<Integer> input){
        
        Stack<Integer> tmpStack = new Stack<Integer>(); 
        
        while(!input.isEmpty()){ 
            int tmp = input.pop(); 
          
            while(!tmpStack.isEmpty() && tmpStack.peek() > tmp){ 
                input.push(tmpStack.pop()); 
            } 
              
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    public static void main(String args[]){
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        input.add(20); 
        input.add(6); 
        input.add(-1); 
        input.add(2); 
        input.add(4); 
        input.add(9); 
      
        Stack<Integer> tmpStack=sort(input); 
        
        while (!tmpStack.empty()){ 
            System.out.print(tmpStack.pop()+" "); 
        }  
    } 
}
20 9 6 4 2 -1

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (n ^ 2) මෙහි n යනු තොගයේ ඇති මූලද්‍රව්‍ය ගණන වේ. තාවකාලික තොගයේ මුදුන තල්ලු කළ යුතු මූලද්‍රව්‍යයට වඩා අඩු නම් අපි තාවකාලික තොගයේ සිට මුල් සිරස් තලයට මූලද්‍රව්‍ය පසුපසට තල්ලු කරන්නෙමු. වඩා හොඳ අවබෝධයක් සඳහා, අවරෝහණ අනුපිළිවෙලක් සලකා බලා ඇල්ගොරිතම ක්‍රියාත්මක කිරීමට උත්සාහ කරන්න.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) අපි n මූලද්‍රව්‍ය සඳහා තාවකාලික සිරස් ඉඩ භාවිතා කළ නිසා. මුල් තොගය භාවිතා කරන අවකාශය ඇල්ගොරිතම සඳහා ගණනය නොකෙරේ.