Сортирајте оџак користејќи рекурзија


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

Изјава за проблем

Проблемот „Сортирај оџак користејќи рекурзија“ наведува дека ти е дадена a магацинот структура на податоци. Вид неговите елементи користејќи рекурзија. Може да се користат само подолу наведените функции на оџакот -

  • туркање (елемент) - за вметнување на елементот во оџакот.
  • pop () - pop () - за отстранување / бришење на елементот на горниот дел од дадениот оџак.
  • isEmpty () - за да провери дали има некој елемент во оџакот или не.
  • горе () - да peирне / види елементот на горниот дел од дадениот оџак.

Сортирајте оџак користејќи рекурзија

пример

9 4 2 -1 6 20
20 9 6 4 2 -1

Објаснување: Бидејќи оџакот е подреден во растечки редослед. Максималниот елемент доаѓа на врвот. Бидејќи оџакот е структура на податоци LIFO, излезот се чини дека е во опаѓачки редослед.

2 1 4 3 6 5
6 5 4 3 2 1

Алгоритам

  1. Иницијализира а магацинот и туркај елементи во него.
  2. Создадете функција за вметнување на елементите по подреден редослед во оџакот што прифаќа оџак и елемент како параметар. Проверете дали оџакот е празен или дадениот елемент е поголем од елементот на горниот дел од оџакот, турнете го елементот во оџакот и вратете се.
  3. Создадете привремена променлива и зачувајте го горниот дел од оџакот во неа. Поп елементот на горниот дел од оџакот и направете рекурзивен повик кон самата функција. Притиснете ја привремената променлива во оџакот.
  4. Слично на тоа, креирајте вид на функција () што прифаќа оџак како параметар. Проверете дали оџакот не е празен, создадете променлива x и зачувајте го горниот дел од оџакот во него. Поп елементот на врвот на оџакот. Остварете рекурзивен повик кон самата функција. Повикајте ја функцијата за да ги вметнете елементите по подреден редослед во оџакот.
  5. Повикајте ја функцијата за сортирање во главната ().
  6. Создадете функција за печатење на подредениот стек што прифаќа оџак како параметар. Поминувајте додека оџакот не е празен, отпечатете ги податоците на оџакот и преместете се на следниот елемент.

Код

Програма C ++ за сортирање на оџак користејќи рекурзија

#include <iostream> 
using namespace std; 
  
struct stack{  
    int data;  
    struct stack *next;  
};  
  
void initStack(struct stack **s){  
    *s = NULL;  
}  
  
int isEmpty(struct stack *s){  
    if(s == NULL){  
        return 1;  
    }    
    return 0;  
}  
  
void push(struct stack **s, int x){
    
    struct stack *p = (struct stack *)malloc(sizeof(*p));  
  
    if(p == NULL){  
        return;  
    }  
  
    p->data = x;  
    p->next = *s;  
    *s = p;  
}  
  
int pop(struct stack **s){  
    int x;  
    struct stack *temp;  
  
    x = (*s)->data;  
    temp = *s;  
    (*s) = (*s)->next;  
    free(temp);  
  
    return x;  
}  
  
int top(struct stack *s){  
    return (s->data);  
}  
  
void InsertWithSort(struct stack **s, int x){  
    
    if(isEmpty(*s) or x > top(*s)){  
        push(s, x);  
        return;  
    }  
  
    int temp = pop(s);  
    InsertWithSort(s, x);  
  
    push(s, temp);  
}  
  
void sort(struct stack **s){  
    
    if(!isEmpty(*s)){  
        int x = pop(s);  
  
        sort(s);  
  
        InsertWithSort(s, x);  
    }  
}  
  
void print(struct stack *s){  
    while(s){  
        cout<<s->data<<" "; 
        s = s->next;  
    }  
}  
  
int main(){  
    struct stack *top;  
  
    initStack(&top);
    
    push(&top, 9);  
    push(&top, 4);  
    push(&top, 2);  
    push(&top, -1);  
    push(&top, 6);
    push(&top, 20);
  
    sort(&top);  
    
    print(top);  
  
    return 0;  
}
20 9 6 4 2 -1

Јава програма за сортирање на оџакот користејќи рекурзија

import java.util.ListIterator; 
import java.util.Stack; 
  
class SortStack{ 
    
    static void InsertWithSort(Stack<Integer> s, int x){ 
        if (s.isEmpty() || x > s.peek()){ 
            s.push(x); 
            return; 
        } 
       
        int temp = s.pop(); 
        InsertWithSort(s, x); 
       
        s.push(temp); 
    } 
       
    static void sort(Stack<Integer> s){ 
        if(!s.isEmpty()){ 
            int x = s.pop(); 
       
            sort(s); 
       
            InsertWithSort(s, x); 
        } 
    } 
      
    static void print(Stack<Integer> s){ 
       ListIterator<Integer> lt = s.listIterator(); 
         
        while(lt.hasNext()){ 
            lt.next(); 
        }       
         
        while(lt.hasPrevious()){ 
           System.out.print(lt.previous()+" ");
        }   
    } 
    
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>(); 
        
        s.push(9);  
        s.push(4);  
        s.push(2);  
        s.push(-1);  
        s.push(6);
        s.push(20); 
       
        sort(s); 
       
        print(s); 
       
    } 
}
20 9 6 4 2 -1

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

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

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

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

НА) затоа што користевме простор за магацинот за n елементи. Додека отстранувате елементи за да го поставиме нашиот сегашен елемент. Моравме да ги чуваме отстранетите елементи, што ни дава линеарна вселенска комплексност.