តំរៀបជួរដោយប្រើជង់


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

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

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

តំរៀបជួរដោយប្រើជង់

ឧទាហរណ៍

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

ការពន្យល់ៈធាតុត្រូវបានតម្រៀបតាមលំដាប់ឡើង។

2 3 1 8 6
1 2 3 6 8

វិធីសាស្រ្តសម្រាប់ការតម្រៀបអារេដោយប្រើជង់

បង្កើតរចនាសម្ព័ន្ធទិន្នន័យជង់ដើម្បីផ្ទុកធាតុទាំងអស់នៃអារេបញ្ចូលដែលបានផ្តល់ a [] ។ បន្ទាប់ពីនោះបង្កើតជង់បណ្តោះអាសន្នមួយទៀតសម្រាប់ការតម្រៀបដើម។ ច្របាច់តាមរយៈជង់ដើមហើយសម្រាប់ធាតុនីមួយៗលេចឡើងផ្នែកខាងលើហើយផ្ទុកវានៅក្នុងអថេរបណ្តោះអាសន្ន។ ស្រដៀងគ្នានេះដែរវាឆ្លងកាត់ជង់បណ្តោះអាសន្នខណៈពេលដែលធាតុនៅខាងលើជង់បណ្តោះអាសន្នតិចជាងផ្នែកខាងលើនៃជង់ដើម។ បញ្ចូលធាតុខាងលើនៃជង់បណ្តោះអាសន្ននៅក្នុងជង់ដើមហើយយកវាចេញពីជង់បណ្តោះអាសន្ន។ រុញផ្នែកខាងលើនៃជង់ដើមដែលមាននៅក្នុងជង់បណ្តោះអាសន្ន។ នៅចុងបញ្ចប់ជង់បណ្តោះអាសន្ននឹងមានធាតុតាមលំដាប់លំដោយ។ បញ្ហានេះគឺជាការកែប្រែបន្តិចបន្តួចលើការតម្រៀបក ជង់ដោយប្រើជង់បណ្តោះអាសន្ន.

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

  1. ចាប់ផ្តើមអារេ a [] នៃទំហំ n ។
  2. បង្កើតរចនាសម្ព័ន្ធទិន្នន័យជង់។ ឆ្លងកាត់អារេ a [] ហើយរុញធាតុទាំងអស់នៃអារេ [] នៅក្នុងជង់។
  3. ស្រដៀងគ្នានេះដែរបង្កើតជង់បណ្តោះអាសន្នមួយទៀត។
  4. ឆ្លងកាត់ខណៈពេលដែលទំហំនៃជង់ដើមគឺមិនមែន ០ ។ បង្កើតអថេរ tmp ហើយរក្សាទុកធាតុនៅខាងលើជង់ដើមនៅក្នុងវាហើយលោតវាចេញពីជង់ដើម។
  5. ឆ្លងកាត់ម្តងទៀតខណៈពេលដែលជង់បណ្តោះអាសន្នមិនទទេហើយបញ្ចូលធាតុនៅខាងលើជង់បណ្តោះអាសន្នរហូតដល់វាតិចជាងអថេរ tmp ។ នៅពេលលោតចេញពីជង់បណ្តោះអាសន្នរុញធាតុខាងលើនៃជង់បណ្តោះអាសន្ននៅក្នុងជង់ដើម។
  6. រុញអថេរ tmp នៅក្នុងជង់បណ្តោះអាសន្ន។
  7. ឆ្លងកាត់ពី 0 ដល់ n-1 ហើយផ្ទុកធាតុខាងលើនៃជង់បណ្តោះអាសន្នក្នុងជួរអារេ [] នៅសន្ទស្សន៍បច្ចុប្បន្នហើយលេចឡើង / លុបធាតុពីជង់បណ្តោះអាសន្ន។
  8. ចុងបញ្ចប់ Traverse ពី 0 ដល់ n-1 ហើយបោះពុម្ពអារេ a [] ។

លេខកូដ

កម្មវិធី C ++ សម្រាប់តម្រៀបអារេដោយប្រើជង់

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