Yığını başka bir yığın kullanarak sıralama

Question

Yığını başka bir yığın kullanarak sıralamak için kullanılan bu algoritmanın zaman karmaşıklığını bilmek istiyorum. Ben O (N^2) olduğunu düşündüm ama görünüşe göre daha fazla görünüyor.

public static Stack<Integer> sort(Stack<Integer> s) { 
    Stack<Integer> r = new Stack<Integer>(); 

    while(!s.isEmpty()) { 
     int tmp = s.pop(); 
     while(!r.isEmpty() && r.peek() > tmp) { 
      s.push(r.pop()); 
     } 
     r.push(tmp); 
    } 
    return r; 
} 

Answer 1

O (n^2) bana görünüyor. Zaten sıralanmış bir yığının en kötü performansa sahip olduğunu tahmin ediyorum. Belirli bir boyutta zaten sıralanmış bir yığın göz önüne alındığında, s.push'un yürütülme sayısını saydım.

Stack of size 1. backpushes: 0 
Stack of size 2. backpushes: 1 
Stack of size 3. backpushes: 3 
Stack of size 4. backpushes: 6 
Stack of size 5. backpushes: 10 
Stack of size 6. backpushes: 15 
Stack of size 7. backpushes: 21 
Stack of size 8. backpushes: 28 
Stack of size 9. backpushes: 36 

0,1,3,6,10 triangular numbers dizisidir. Boyut N'nin sıralanmış bir yığını, (N^2 + N)/2 backpushes gerektirir. Bu onu yapar (N^2).

Answer 2

yığını [x_2, .., x_n] (yığın sağ doğru büyür) tasnif en fazla tmp

Transferi aşağıdaki

1. Sıralama substack [x_2, .., x_n] Pop x_1
2. s arasında yapacak Not yığınına [x_1, .., x_n] zaman ayırma, t(n-1) zaman alıyorsaöğeleri r öğelerinden s
3. r
4. için x_1 düğmesine basın. 3. adımda aktarılan öğeleri bir kez daha işleyin, ancak hiçbir zaman çalışmadığı sürece döngü sırasında iç kısımda olacak şekilde sırayla.

Algoritmanın [x_1, .., x_n] üzerinde çalıştırılması en fazla t(n-1) + O(n) zamanını alacaktır. Yani

t(n) <= O(n) + t(n-1) <= c * n + t(n-1) 
t(n) <= c * n + c * (n - 1) + t(n-2) <= ... <= c * (1 + 2 + ... + n) 
t(n) <= c * n(n + 1)/2 

Yani t(n)O(n^2) olduğunu (bazı sabit c için) yol açar.

Answer 3

Bu sorun, o (n^2) karmaşıklığında yapılabilir. Bu, en fazla sayıda sayı atma ve ikinci yığındaki depolama öğelerini saklamadan ve ilk yığının boyutunu güncelleştirmeden ve daha sonra ilk yığına geri itmeden yapılabilir . Kod pasajına bir göz atın.

#include<stdio.h> 
      func(struct stack *s1) 
      { 
          struct stack* s2=(struct stack*) malloc(sizeof(struct stack)) 
          int i=0; 
          int max=INT_MIN; 
          size=s1->size; 
          if(s1->size==0) 
          { 
           return; 
          } 
          for(;i<size;i++) 
          { 

           while(size(s1)!=size)//popping the elements and pushing in s2 stack and keeping track of maximum element. 
           { 

            temp=pop(s1); 
            if(temp>max) 
            { 

             push(s2,max); 
             max=temp; 
            } 

           } 
           push(s1,max);//pushing the max element into stack s1 back and updating the size in push operation. 
           while(!empty(s2))//pushing extracted numbers back into stack s1 from s2. 
           { 
            push(s1,pop(s2)); 

           } 

          } 


     }