Ταξινόμηση φυσαλίδων χρησιμοποιώντας δύο στοίβες


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Capgemini Δελχί MAQ
Παράταξη Ταξινόμηση

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

Το πρόβλημα "Bubble sort using two Stacks" δηλώνει ότι σας δίνεται ένα παράταξη a [] μεγέθους n. Δημιουργήστε μια συνάρτηση για να ταξινομήσετε τον δεδομένο πίνακα a [] χρησιμοποιώντας ένα παράδειγμα ταξινόμησης φυσαλίδων με δύο δομές δεδομένων στοίβας.

Ταξινόμηση φυσαλίδων χρησιμοποιώντας δύο στοίβες

Παράδειγμα

a[ ] = {15, 12, 44, 2, 5, 10}
2 5 10 12 15 44
a[ ] = {5, 6, 4, 2, 3, 1}
1 2 3 4 5 6

Αλγόριθμος

  1. Αρχικοποιήστε ένα παράταξη a [] μεγέθους n.
  2. Δημιουργήστε τη συνάρτηση είδος ο δεδομένος πίνακας που χρησιμοποιεί [] τύπος φυσαλίδων παράδειγμα με δύο σωρός δομές δεδομένων που δέχονται έναν πίνακα και το μέγεθός του ως παράμετρος.
  3. Δημιουργήστε μια δομή δεδομένων στοίβας του ακέραιος αριθμός τύπος. Διασχίστε τον δεδομένο πίνακα και σπρώξτε όλα τα στοιχεία του πίνακα στη στοίβα.
  4. Ομοίως, δημιουργήστε μια άλλη δομή δεδομένων στοίβας ακέραιου τύπου.
  5. Μετά από αυτό, διασχίστε από 0 έως n-1. Ελέγξτε εάν το τρέχον mod index 2 είναι ίσο με 0, διασχίστε ξανά ενώ η πρώτη στοίβα δεν είναι άδεια
  6. Δημιουργήστε μια ακέραια μεταβλητή και ανοίξτε το στοιχείο στην κορυφή της πρώτης στοίβας και αποθηκεύστε το.
  7. Ελέγξτε εάν η δεύτερη στοίβα είναι κενή, πιέστε / εισαγάγετε την ακέραια μεταβλητή στη δεύτερη στοίβα. Διαφορετικά ελέγξτε αν το στοιχείο στην κορυφή της δεύτερης στοίβας είναι μεγαλύτερο από την ακέραια μεταβλητή, δημιουργήστε μια προσωρινή μεταβλητή, ανοίξτε το στοιχείο στην κορυφή της δεύτερης στοίβας και αποθηκεύστε το στην προσωρινή μεταβλητή. Πιέστε την ακέραια μεταβλητή στη δεύτερη στοίβα. Μετά από αυτό, πιέστε την προσωρινή μεταβλητή στη δεύτερη στοίβα.
  8. Διαφορετικά, εάν το στοιχείο στην κορυφή της δεύτερης στοίβας είναι μικρότερο ή ίσο με την ακέραια μεταβλητή, πιέστε την ακέραια μεταβλητή στη στοίβα.
  9. Βγάλτε το πάνω μέρος της δεύτερης στοίβας και αποθηκεύστε το στον πίνακα a [] στο ευρετήριο n-1-current index.
  10. Διαφορετικά, εάν ο τρέχων δείκτης mod Το 2 είναι ίσο με 0, διασχίζει ενώ η δεύτερη στοίβα δεν είναι κενή.
  11. Δημιουργήστε μια ακέραια μεταβλητή και ανοίξτε το στοιχείο στην κορυφή της δεύτερης στοίβας και αποθηκεύστε το σε.
  12. Ο έλεγχος είναι ότι η πρώτη στοίβα είναι κενή, πιέστε / εισαγάγετε την ακέραια μεταβλητή στην πρώτη στοίβα. Διαφορετικά, ελέγξτε εάν το στοιχείο στην κορυφή της πρώτης στοίβας είναι μεγαλύτερο από την ακέραια μεταβλητή, δημιουργήστε μια προσωρινή μεταβλητή, ανοίξτε το στοιχείο στην κορυφή της πρώτης στοίβας και αποθηκεύστε το στην προσωρινή μεταβλητή. Πιέστε την ακέραια μεταβλητή στην πρώτη στοίβα. Μετά από αυτό, πιέστε την προσωρινή μεταβλητή στην πρώτη στοίβα.
  13. Διαφορετικά, εάν το στοιχείο στην κορυφή της πρώτης στοίβας είναι μικρότερο ή ίσο με την ακέραια μεταβλητή, πιέστε την ακέραια μεταβλητή στη στοίβα.
  14. Βάλτε το πάνω μέρος της πρώτης στοίβας και αποθηκεύστε το στη σειρά a [] στο ευρετήριο n-1-current index.
  15. Εκτυπώστε τον ταξινομημένο πίνακα.

Κώδικας

Πρόγραμμα C ++ για την εφαρμογή ταξινόμησης φυσαλίδων χρησιμοποιώντας δύο στοίβες

#include <bits/stdc++.h>
using namespace std;

void bubbleSortStack(int a[], int n){ 
    stack<int> s1;
      
    for(int i = 0; i < n; i++){ 
        s1.push(a[i]);
    }
      
    stack<int> s2;
      
    for(int i = 0; i < n; i++){ 
        
        if(i % 2 == 0){ 
            while (!s1.empty()){ 
                int t = s1.top();
                s1.pop(); 
                  
                if(s2.empty()){ 
                    s2.push(t);  
                }
                
                else{ 
                    
                    if(s2.top() > t){ 
                        int temp = s2.top(); 
                        s2.pop(); 
                        s2.push(t); 
                        s2.push(temp); 
                    } 
                    
                    else{ 
                        s2.push(t); 
                    } 
                } 
            } 
            a[n-1-i] = s2.top();
            s2.pop(); 
        }     
        
        else{
            
            while(!s2.empty()){ 
                int t = s2.top();
                s2.pop();
                  
                if (s1.empty()){ 
                    s1.push(t); 
                }
                  
                else{ 
                    
                    if (s1.top() > t){ 
                        int temp = s1.top();
                        s1.pop(); 
                          
                        s1.push(t); 
                        s1.push(temp); 
                    } 
                    
                    else{
                        s1.push(t); 
                    }
                } 
            } 
              
            a[n-1-i] = s1.top();
            s1.pop(); 
        } 
    }
    
    for(int i = 0; i < n; i++){
        cout<< a[i] << " "; 
    }
} 
  
int main() {
  int a[] = {15, 12, 44, 2, 5, 10};
  int n = sizeof(a)/sizeof(a[0]);
    
  bubbleSortStack(a, n); 
    
  return 0;
}
2 5 10 12 15 44

Πρόγραμμα Java για την εφαρμογή ταξινόμησης φυσαλίδων χρησιμοποιώντας δύο στοίβες

import java.util.Arrays; 
import java.util.Stack; 
  
class Sort{ 
    
    static void bubbleSortStack(int a[], int n){ 
        Stack<Integer> s1 = new Stack<>(); 
          
        for(int num : a){ 
            s1.push(num);
        }
          
        Stack<Integer> s2 = new Stack<>(); 
          
        for(int i = 0; i < n; i++){ 
            
            if(i % 2 == 0){ 
                while (!s1.isEmpty()){ 
                    int t = s1.pop(); 
                      
                    if(s2.isEmpty()){ 
                        s2.push(t);  
                    }
                    
                    else{ 
                        
                        if(s2.peek() > t){ 
                            int temp = s2.pop(); 
                            s2.push(t); 
                            s2.push(temp); 
                        } 
                        
                        else{ 
                            s2.push(t); 
                        } 
                    } 
                } 
                a[n-1-i] = s2.pop(); 
            }     
            
            else{
                
                while(!s2.isEmpty()){ 
                    int t = s2.pop(); 
                      
                    if (s1.isEmpty()){ 
                        s1.push(t); 
                    }
                      
                    else{ 
                        
                        if (s1.peek() > t){ 
                            int temp = s1.pop(); 
                              
                            s1.push(t); 
                            s1.push(temp); 
                        } 
                        
                        else{
                            s1.push(t); 
                        }
                    } 
                } 
                  
                a[n-1-i] = s1.pop(); 
            } 
        }
        
        for(int i = 0; i < n; i++){
            System.out.print(a[i]+" "); 
        }
    } 
      
    public static void main(String[] args){
        
        int a[] = {15, 12, 44, 2, 5, 10};
        
        bubbleSortStack(a, a.length); 
    } 
}
2 5 10 12 15 44

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

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

O (n ^ 2) όπου n είναι ο αριθμός ακέραιων αριθμών σε δεδομένο πίνακα a []. Αυτή είναι η συνήθης πολυπλοκότητα του χρόνου που απαιτείται από το Bubble Sort.

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

O (n) γιατί χρησιμοποιήσαμε χώρο για n στοιχεία. Αυτός ο χώρος αποθήκευσης απαιτείται για στοίβες.