Ҷудокунии массив бо истифода аз стакҳо


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Голдман Sachs IBM Кулиза Yahoo
Sorting тӯда

Изҳороти мушкилот

Масъалаи "Ҷобаҷогузории массив бо истифода аз Stacks" изҳор медорад, ки ба шумо сохтори маълумот дода шудааст асал а [] андозаи n. Sort унсурҳои массиви додашуда истифода мебаранд яхдон сохтори маълумот.

Ҷудокунии массив бо истифода аз стакҳо

мисол

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

Шарҳ: Элементҳо бо тартиби афзоиш ҷудо карда мешаванд.

2 3 1 8 6
1 2 3 6 8

Равиш барои ҷобаҷогузории массив бо ёрии стакҳо

Барои нигоҳ доштани ҳамаи унсурҳои массиви додашудаи a [] структураи стеки маълумотро созед. Пас аз он, барои ҷобаҷогузории анбори аслӣ стаки дигари муваққатӣ эҷод кунед. Аз стеки аслӣ тағир диҳед ва барои ҳар як унс попро боло кунед ва онро дар тағирёбандаи муваққатӣ нигоҳ доред. Ба ҳамин монанд, аз стек муваққатӣ такрор кунед, дар ҳоле ки элемент дар болои стеки муваққатӣ аз болои партофташудаи стеки аслӣ камтар аст. Унсури болоии анбораи муваққатиро ба анбори аслӣ гузоред ва онро аз анбораи муваққатӣ хориҷ кунед. Қуттии болоии аслиро ба анбори муваққатӣ тела диҳед. Дар ниҳоят, стаки муваққатӣ унсурҳоро бо тартиби мураттаб дар бар мегирад. Ин мушкилот тағироти ночизест дар мавриди навъ а стекро бо истифодаи стаки муваққатӣ.

Алгоритм

  1. Массивро [] андозаи n оғоз кунед.
  2. Сохтори стеки маълумотро эҷод кунед. Аз массиви a [] гузаред ва ҳамаи элементҳои массиви a [] -ро дар стек пахш кунед.
  3. Ба ин монанд, як стаки дигари муваққатӣ эҷод кунед.
  4. Гузаред, дар ҳоле ки андозаи стаки аслӣ 0 нест. Тағирёбандаи tmp эҷод кунед ва унсурро дар болои стеки аслӣ дар он нигоҳ доред ва онро аз стаки аслӣ бардоред.
  5. Боз ҳам дар ҳоле, ки стаки муваққатӣ холӣ нест ва попро дар болои стеки муваққатӣ то он даме ки камтар аз тағирёбандаи tmp гузоред. Ҳангоми партофтан аз стаки муваққатӣ, унсури болоии стаки муваққатиро ба стаки аслӣ тела диҳед.
  6. Тағири тағирёбандаро ба стаки муваққатӣ тела диҳед.
  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 барои ҷобаҷогузории массив бо ёрии Stacks

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 элемент фазои стакании муваққатиро истифода кардем. Фосилае, ки стаки аслӣ истифода мебарад, барои алгоритм ҳисоб карда намешавад.