តម្រៀបជង់ដោយប្រើជង់បណ្តោះអាសន្ន


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន IBM គុលលីហ្សា ក្រុមហ៊ុន Yahoo
តម្រៀប ជង់

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា "តម្រៀបជង់ដោយប្រើជង់បណ្តោះអាសន្ន" បញ្ជាក់ថាអ្នកត្រូវបានផ្តល់ឱ្យ ជង់ រចនាសម្ព័ន្ធទិន្នន័យ។ តម្រៀបធាតុនៃជង់ដែលបានផ្តល់ឱ្យដោយប្រើជង់បណ្តោះអាសន្ន។

តម្រៀបជង់ដោយប្រើជង់បណ្តោះអាសន្ន

ឧទាហរណ៍

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

ឧទាហរណ៍

សូមជង់ = [៩ ៤ ២-១ ៦ ២០] និងជង់បណ្តោះអាសន្ន = []

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]

នៅពេលជង់ទទេហើយជង់បណ្តោះអាសន្នត្រូវបានតម្រៀបបោះពុម្ពជង់បណ្តោះអាសន្នចាប់ផ្តើមពីកំពូលរបស់វា។

ដូច្នេះលទ្ធផល៖ ២០ ៩ ៦ ៤ ២-១

ក្បួនដោះស្រាយដើម្បីតម្រៀបជង់ដោយប្រើជង់បណ្តោះអាសន្ន

  1. ចាប់ផ្តើមរចនាសម្ព័ន្ធទិន្នន័យជង់និងបញ្ចូល / រុញធាតុនៅក្នុងវា។
  2. បន្ទាប់ពីនោះបង្កើតតម្រៀបមុខងារ () ដែលទទួលយកជង់ដែលជាប៉ារ៉ាម៉ែត្ររបស់វា។ ចាប់ផ្តើមជង់បណ្តោះអាសន្ន / ជំនួយបន្ថែមមួយផ្សេងទៀតនៅក្នុងវា។
  3. ឆ្លងកាត់ខណៈពេលដែលជង់ដើមមិនទទេបង្កើត tmp អថេរនិងរក្សាទុកកំពូលនៃជង់ដើមនៅក្នុងវា។ បន្ទាប់ពីនោះលេចឡើងកំពូលនៃជង់ដើម។
  4. ជាថ្មីម្តងទៀត Traverse ខណៈពេល tmpStack មិនទទេហើយកំពូលនៃ tmpStack មានន័យថាជង់បណ្តោះអាសន្នធំជាងមិនតិចជាងឬស្មើ tmp អថេររុញកំពូលនៃជង់បណ្តោះអាសន្ននៅក្នុងជង់ដើមហើយបញ្ចូលកំពូលនៃជង់បណ្តោះអាសន្ន។
  5. ជំរុញអថេរ tmp នៅក្នុងជង់បណ្តោះអាសន្ន។
  6. ខណៈពេលដែលជង់បណ្តោះអាសន្នមិនទទេបោះពុម្ពវាកំពូលហើយលេចឡើងវានៅខាងលើ។

លេខកូដ

កម្មវិធី C ++ ដើម្បីតម្រៀបជង់ដោយប្រើការហៅខ្លួនឯង

#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 ។ ទំហំដែលប្រើដោយជង់ដើមមិនត្រូវបានរាប់សម្រាប់ក្បួនដោះស្រាយទេ។