Ταξινόμηση μιας στοίβας χρησιμοποιώντας αναδρομή


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Goldman Sachs IBM Κουλίζα Yahoo
Αναδρομή Στοίβα

Δήλωση προβλήματος

Το πρόβλημα «Ταξινόμηση μιας στοίβας χρησιμοποιώντας αναδρομή» δηλώνει ότι σας δίνεται ένα σωρός δομή δεδομένων. Είδος τα στοιχεία του χρησιμοποιώντας αναδρομή. Μπορούν να χρησιμοποιηθούν μόνο οι παρακάτω λειτουργίες της στοίβας -

  • push (element) - για να εισαγάγετε το στοιχείο στη στοίβα.
  • pop () - pop () - για να αφαιρέσετε / διαγράψετε το στοιχείο στην κορυφή της δεδομένης στοίβας.
  • isEmpty () - για να ελέγξετε αν υπάρχει στοιχείο στη στοίβα ή όχι.
  • κορυφή () - για να δείτε / δείτε το στοιχείο στην κορυφή της δοσμένης στοίβας.

Ταξινόμηση μιας στοίβας χρησιμοποιώντας αναδρομή

Παράδειγμα

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. Αρχικοποίηση a σωρός και ώθηση στοιχείων σε αυτό.
  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

Πρόγραμμα Java για ταξινόμηση μιας στοίβας χρησιμοποιώντας αναδρομή

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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Ο (Ν ^ 2) όπου n είναι ο αριθμός των στοιχείων στη στοίβα. Διότι όταν πιέζουμε το στοιχείο στη στοίβα μπορεί να καταλήξουμε να αφαιρέσουμε όλα τα στοιχεία που υπάρχουν αυτήν τη στιγμή στη στοίβα και στη συνέχεια να το τοποθετήσουμε. Αυτή η περίπτωση παρουσιάζεται εάν η είσοδος είναι σε φθίνουσα σειρά.

Διαστημική πολυπλοκότητα

ΕΠΙ) επειδή χρησιμοποιήσαμε χώρο στοίβας για στοιχεία n. Κατά την αφαίρεση στοιχείων για να τοποθετήσετε το τρέχον στοιχείο μας. Έπρεπε να αποθηκεύσουμε τα αφαιρεθέντα στοιχεία, γεγονός που μας δίνει μια γραμμική πολυπλοκότητα χώρου.