Сортирање на низата со употреба на Купишта


Ниво на тешкотија Медиум
Често прашувано во Амазон Голдман Сакс IBM, Кулиза Јаху
Сортирање Магацинот

Проблем изјава

Проблемот „Сортирање низа со употреба на Купишта“ наведува дека ви е дадена структура на податоци низа 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 [] и турнете ги сите елементи на низата a [] во оџакот.
  3. Слично на тоа, создадете друг привремен оџак.
  4. Поминувајте додека големината на оригиналниот оџак не е 0. Создадете променлива tmp и зачувајте го елементот на горниот дел од оригиналниот оџак во него и попувајте го од оригиналниот оџак.
  5. Повторно поминувајте додека привремениот оџак не е празен и попувајте го елементот на горниот дел од привремениот оџак сè додека не биде помал од променливата tmp. Додека пукате од привремен оџак, турнете го горниот елемент на привремениот оџак во оригиналниот оџак.
  6. Притиснете ја променливата tmp во привремен оџак.
  7. Поминете од 0 до n-1 и зачувајте го горниот елемент на привремениот оџак во низата a [] на тековниот индекс и поп / избришете го елементот од привремениот оџак.
  8. На крај, поминете од 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

Анализа на сложеност

Временска комплексност

О (n ^ 2) каде n е бројот на елементи во оџакот. Бидејќи ги туркаме елементите назад од привремениот оџак во оригиналниот оџак во случај горниот дел од привремениот оџак да биде помал од елементот што треба да се турка. За подобро разбирање, размислете за редоследот на опаѓачки редослед и обидете се да го извршите алгоритмот.

Комплексноста на просторот

Тој) затоа што користевме привремен простор за магацинот за n елементи. Просторот што го користи оригиналниот оџак не се смета за алгоритмот.