Массивдерди Stacks аркылуу иреттөө


Кыйынчылык деңгээли орто
Көп суралган Amazon Goldman Sachs IBM Кулиза Yahoo
сорттоо чөмөлө

Көйгөйдү айтуу

Массивди "Стектерди колдонуп сорттоо" көйгөйү сизге маалымат структурасы берилгенин билдирет согуштук тизме n [өлчөмү] [[. түр берилген массивдин элементтерин колдонуу чөмөлө маалыматтардын структурасы.

Массивдерди Stacks аркылуу иреттөө

мисал

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

Түшүндүрүү: элементтер өсүү тартибинде иреттелген.

2 3 1 8 6
1 2 3 6 8

Стекстин жардамы менен массивди сорттоо ыкмасы

Берилген a [] массивинин бардык элементтерин сактоо үчүн стек маалыматтар структурасын түзүңүз. Андан кийин, оригиналын сорттоо үчүн дагы бир убактылуу стек түзүңүз. Түпнуска стекти кайталаңыз жана ар бир элементтин үстүнкү жагын ачып, убактылуу өзгөрмөчөдө сактаңыз. Ошо сыяктуу эле, убактылуу десте аркылуу кайталаңыз, ал эми убактылуу стектин жогору жагындагы элемент баштапкы стектин үстүнкү жагына караганда аз. Убакыт стектин үстүңкү элементин түпнуска ставкага салып, убактылуу дестеден чыгарып салыңыз. Баштапкы стектин үстүңкү бөлүгүн убактылуу үймөгө түртүп салыңыз. Акыр-аягы, убактылуу стек элементтерди иреттелген тартипте камтыйт. Бул көйгөй бир аз өзгөртүүгө байланыштуу үймөктү колдонуу.

Algorithm

  1. N көлөмүндөгү [[] массивин инициализациялоо.
  2. Стек структурасын түзүңүз. A [] массивин аралап өтүп, a [] массивинин бардык элементтерин стекке түртүп салыңыз.
  3. Ошо сыяктуу эле, дагы бир убактылуу стек түзүү.
  4. Баштапкы стектин көлөмү 0 болбогондо өтүңүз. Өзгөрүлмө tmp түзүп, андагы баштапкы стектин жогору жагындагы элементти сактап, баштапкы стектен калкып чыгыңыз.
  5. Убакыт стек бош эмес, дагы бир жолу өтүңүз жана tmp өзгөрмөсүнөн аз болгонго чейин, элементтин үстүнкү жагына поп. Убактылуу үймөктөн чыгып жатканда, түпкү үймөктөгү убактылуу стектин үстүңкү элементин түртүп салыңыз.
  6. Tmp өзгөрмөсүн убактылуу стекке түртүп салыңыз.
  7. 0 ден n-1 ге чейин өтүңүз жана убактылуу стектин үстүңкү элементин учурдагы индексте [] массивинде сактап, элементти убактылуу үймөдөн калкып / жок кылыңыз.
  8. Акырында 0 дан n-1 ге чейин өтүп, [[массивин] басып чыгарыңыз.

коду

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 программасы

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 элементтер үчүн убактылуу стек мейкиндигин колдондук. Алгоритм үчүн баштапкы стек колдонулган мейкиндик эсептелбейт.