តម្រៀបពពុះដោយប្រើជង់ពីរ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon Capgemini ដេលីវ៉ាយ MAQ
អារេ តម្រៀប

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

បញ្ហា“ តម្រៀបពពុះដោយប្រើជង់ពីរ” បញ្ជាក់ថាអ្នកត្រូវបានផ្តល់ឱ្យ អារេ a [] នៃទំហំ n ។ បង្កើតមុខងារដើម្បីតម្រៀបអារេដែលបានផ្តល់ឱ្យដោយប្រើគំរូតម្រៀបពពុះដែលមានរចនាសម្ព័ន្ធទិន្នន័យជង់ពីរ។

តម្រៀបពពុះដោយប្រើជង់ពីរ

ឧទាហរណ៍

a[ ] = {15, 12, 44, 2, 5, 10}
2 5 10 12 15 44
a[ ] = {5, 6, 4, 2, 3, 1}
1 2 3 4 5 6

ក្បួនដោះស្រាយ

  1. ផ្តួចផ្តើមមួយ អារេ a [] នៃទំហំ n ។
  2. បង្កើតមុខងារទៅ ជោគវាសនា អារេដែលបានផ្តល់អោយប្រើដោយ តម្រៀបពពុះ គំរូជាមួយពីរ ជង់ រចនាសម្ព័ន្ធទិន្នន័យដែលទទួលយកអារេហើយវាមានទំហំដូចដែលវាជាប៉ារ៉ាម៉ែត្រ។
  3. បង្កើតរចនាសម្ព័ន្ធទិន្នន័យជង់នៃ integer ប្រភេទ។ ឆ្លងកាត់អារេដែលបានផ្តល់ហើយរុញធាតុទាំងអស់នៃអារេនៅក្នុងជង់។
  4. ស្រដៀងគ្នានេះដែរបង្កើតរចនាសម្ព័ន្ធទិន្នន័យជង់មួយទៀតនៃប្រភេទចំនួនគត់។
  5. បន្ទាប់ពីនោះឆ្លងកាត់ពី 0 ទៅ n-1 ។ ពិនិត្យមើលថាតើសន្ទស្សន៍សន្ទស្សន៍បច្ចុប្បន្ន ២ ស្មើ ០, ឆ្លងកាត់ម្តងទៀតនៅពេលដែលជង់ទីមួយមិនទទេ។
  6. បង្កើតអថេរចំនួនគត់ហើយបញ្ចូលធាតុនៅខាងលើជង់ដំបូងហើយផ្ទុកវា។
  7. ពិនិត្យមើលថាតើជង់ទីពីរទទេរុញ / បញ្ចូលអថេរចំនួនគត់នៅក្នុងជង់ទីពីរ។ ពិនិត្យមើលថាតើធាតុនៅខាងលើជង់ទីពីរធំជាងអថេរចំនួនគត់បង្កើតអថេរបណ្តោះអាសន្នលេចឡើងធាតុនៅខាងលើជង់ទីពីរហើយរក្សាទុកវាក្នុងអថេរបណ្តោះអាសន្ន។ រុញអថេរចំនួនគត់ក្នុងជង់ទីពីរ។ បន្ទាប់ពីនោះរុញអថេរបណ្តោះអាសន្ននៅក្នុងជង់ទីពីរ។
  8. ផ្សេងទៀតប្រសិនបើធាតុនៅខាងលើនៃជង់ទីពីរតិចជាងឬស្មើទៅនឹងអថេរចំនួនគត់រុញអថេរចំនួនគត់នៅក្នុងជង់។
  9. លោតផ្នែកខាងលើនៃជង់ទីពីរហើយទុកវានៅក្នុងជួរអា [] នៅសន្ទស្សន៍ n-1-index បច្ចុប្បន្ន។
  10. ផ្សេងទៀតប្រសិនបើសន្ទស្សន៍បច្ចុប្បន្ន Mod ២ ស្មើ ០, ឆ្លងកាត់ខណៈជង់ទី ២ មិនទទេ។
  11. បង្កើតអថេរចំនួនគត់ហើយបញ្ចូលធាតុនៅខាងលើនៃជង់ទីពីរហើយផ្ទុកនៅក្នុងនោះ។
  12. ពិនិត្យគឺជង់ទីមួយទទេរុញ / បញ្ចូលអថេរចំនួនគត់នៅក្នុងជង់ដំបូង។ ពិនិត្យមើលថាតើធាតុនៅខាងលើនៃជង់ទីមួយធំជាងអថេរចំនួនគត់បង្កើតអថេរបណ្តោះអាសន្នលេចឡើងធាតុនៅខាងលើនៃជង់ដំបូងហើយរក្សាទុកវាក្នុងអថេរបណ្តោះអាសន្ន។ រុញអថេរចំនួនគត់ក្នុងជង់ទីមួយ។ បន្ទាប់ពីនោះរុញអថេរបណ្តោះអាសន្ននៅក្នុងជង់ដំបូង។
  13. ផ្សេងទៀតប្រសិនបើធាតុនៅខាងលើនៃជង់ទីមួយគឺតិចជាងឬស្មើទៅនឹងអថេរចំនួនគត់រុញអថេរចំនួនគត់នៅក្នុងជង់។
  14. លោតផ្នែកខាងលើនៃជង់ដំបូងហើយរក្សាទុកវាក្នុងជួរអា [] នៅសន្ទស្សន៍ n-1-index បច្ចុប្បន្ន។
  15. បោះពុម្ពអារេដែលបានតម្រៀប។

លេខកូដ

កម្មវិធី C ++ ដើម្បីអនុវត្តការតម្រៀបពពុះដោយប្រើជង់ពីរ

#include <bits/stdc++.h>
using namespace std;

void bubbleSortStack(int a[], int n){ 
    stack<int> s1;
      
    for(int i = 0; i < n; i++){ 
        s1.push(a[i]);
    }
      
    stack<int> s2;
      
    for(int i = 0; i < n; i++){ 
        
        if(i % 2 == 0){ 
            while (!s1.empty()){ 
                int t = s1.top();
                s1.pop(); 
                  
                if(s2.empty()){ 
                    s2.push(t);  
                }
                
                else{ 
                    
                    if(s2.top() > t){ 
                        int temp = s2.top(); 
                        s2.pop(); 
                        s2.push(t); 
                        s2.push(temp); 
                    } 
                    
                    else{ 
                        s2.push(t); 
                    } 
                } 
            } 
            a[n-1-i] = s2.top();
            s2.pop(); 
        }     
        
        else{
            
            while(!s2.empty()){ 
                int t = s2.top();
                s2.pop();
                  
                if (s1.empty()){ 
                    s1.push(t); 
                }
                  
                else{ 
                    
                    if (s1.top() > t){ 
                        int temp = s1.top();
                        s1.pop(); 
                          
                        s1.push(t); 
                        s1.push(temp); 
                    } 
                    
                    else{
                        s1.push(t); 
                    }
                } 
            } 
              
            a[n-1-i] = s1.top();
            s1.pop(); 
        } 
    }
    
    for(int i = 0; i < n; i++){
        cout<< a[i] << " "; 
    }
} 
  
int main() {
  int a[] = {15, 12, 44, 2, 5, 10};
  int n = sizeof(a)/sizeof(a[0]);
    
  bubbleSortStack(a, n); 
    
  return 0;
}
2 5 10 12 15 44

កម្មវិធីចាវ៉ាដើម្បីអនុវត្តប្រភេទពពុះដោយប្រើជង់ពីរ

import java.util.Arrays; 
import java.util.Stack; 
  
class Sort{ 
    
    static void bubbleSortStack(int a[], int n){ 
        Stack<Integer> s1 = new Stack<>(); 
          
        for(int num : a){ 
            s1.push(num);
        }
          
        Stack<Integer> s2 = new Stack<>(); 
          
        for(int i = 0; i < n; i++){ 
            
            if(i % 2 == 0){ 
                while (!s1.isEmpty()){ 
                    int t = s1.pop(); 
                      
                    if(s2.isEmpty()){ 
                        s2.push(t);  
                    }
                    
                    else{ 
                        
                        if(s2.peek() > t){ 
                            int temp = s2.pop(); 
                            s2.push(t); 
                            s2.push(temp); 
                        } 
                        
                        else{ 
                            s2.push(t); 
                        } 
                    } 
                } 
                a[n-1-i] = s2.pop(); 
            }     
            
            else{
                
                while(!s2.isEmpty()){ 
                    int t = s2.pop(); 
                      
                    if (s1.isEmpty()){ 
                        s1.push(t); 
                    }
                      
                    else{ 
                        
                        if (s1.peek() > t){ 
                            int temp = s1.pop(); 
                              
                            s1.push(t); 
                            s1.push(temp); 
                        } 
                        
                        else{
                            s1.push(t); 
                        }
                    } 
                } 
                  
                a[n-1-i] = s1.pop(); 
            } 
        }
        
        for(int i = 0; i < n; i++){
            System.out.print(a[i]+" "); 
        }
    } 
      
    public static void main(String[] args){
        
        int a[] = {15, 12, 44, 2, 5, 10};
        
        bubbleSortStack(a, a.length); 
    } 
}
2 5 10 12 15 44

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (n ^ 2) ដែល n ជាចំនួនគត់នៅក្នុងអារេដែលបានផ្តល់ a [] ។ នេះគឺជាពេលវេលាស្មុគស្មាញដែលទាមទារដោយពពុះ។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ពីព្រោះយើងប្រើចន្លោះសម្រាប់ធាតុ n ។ ការផ្ទុកនេះត្រូវបានទាមទារសម្រាប់ជង់។