Atividade supervisionada algoritmos 2

Prévia do material em texto

Bolha
A: 0. 5, 77, 2, 4, 11, 10, 5, 2, 8, 1, 0
 0 0 0 0 0 0 0 0 0 1
 5 77 2 4 11 10 5 2 8
A: 1. 0, 5, 77, 2, 4, 11, 10, 5, 2, 8, 1
 1 1 1 1 1 1 1 1 1 8
 5 77 2 4 11 10 5 2
A: 2. 0, 1, 5, 77, 2, 4, 11, 10, 5, 2, 8
 2 2 2 2 2 2 2 5
 5 77 2 4 11 10
A: 3. 0, 1, 2, 5, 77, 2, 4, 11, 10, 5, 8
 2 2 77 5 5 10
 5 11
A: 4. 0, 1, 2, 2, 5, 77, 4, 5, 11, 10, 8
 4 4 77 8 8 10
 5 11
A: 5. 0, 1, 2, 2, 4, 5, 77, 5, 8, 11, 10
 5 77 10 11
A: 6. 0, 1, 2, 2, 4, 5, 5, 77, 8, 10, 11
 8 77
A: 7. 0, 1, 2, 2, 4, 5, 5, 8, 77, 10, 11
 10 77
A: 8. 0, 1, 2, 2, 4, 5, 5, 8, 10, 77, 11
 11 77
A: 9. 0, 1, 2, 2, 4, 5, 5, 8, 10, 11, 77
 
Bolha
B: 0. 9, 45, 12, 23, 47, 74, 56, 87
 12 45 56 74
B: 1. 9, 12, 45, 23, 47, 56, 74, 87
 23 45
B: 2. 9, 12, 23, 45, 47, 56, 74, 87
Inserção
A: 0. 5, 77, 2, 4, 11, 10, 5, 2, 8, 1, 0
A: 1. 2, 5, 77, 4, 11, 10, 5, 2, 8, 1, 0
A: 2. 2, 5, 77, 4, 11, 10, 5, 2, 8, 1, 0
A: 3. 2, 4, 5, 77, 11, 10, 5, 2, 8, 1, 0
A: 4. 2, 4, 5, 11, 77, 10, 5, 2, 8, 1, 0
A: 5. 2, 4, 5, 10, 11, 77, 5, 2, 8, 1, 0
A: 6. 2, 4, 5, 5, 10, 11, 77, 2, 8, 1, 0
A: 7. 2, 2, 4, 5, 5, 10, 11, 77, 8, 1, 0
A: 8. 2, 2, 4, 5, 5, 8, 10, 11, 77, 1, 0
A: 9. 1, 2, 2, 4, 5, 5, 8, 10, 11,77, 0
A: 10. 0, 1, 2, 2, 4, 5, 5, 8, 10, 11, 77
Inserção
B: 0. 9, 45, 12, 23, 47, 74, 56, 87
B: 1. 9, 45, 12, 23, 47, 74, 56, 87
B: 2. 9, 12, 45, 23, 47, 74, 56, 87
B: 3. 9, 12, 23, 45, 47, 74, 56, 87
B: 4. 9, 12, 23, 45, 47, 56, 74, 87
Seleção
A: 0. 5, 77, 2, 4, 11, 10, 5, 2, 8, 1, 0
A: 1. 0, 5, 77, 2, 4, 11, 10, 5, 2, 8, 1
A: 2. 0, 1, 5, 77, 2, 4, 11, 10, 5, 2, 8
A: 3. 0, 1, 2, 5, 77, 2, 4, 11, 10, 5, 8
A: 4. 0, 1, 2, 2, 5, 77, 4, 11, 10, 5, 8
A: 5. 0, 1, 2, 2, 4, 5, 77, 11, 10, 5, 8
A: 6. 0, 1, 2, 2, 4, 5, 5, 77, 11, 10, 8
A: 7. 0, 1, 2, 2, 4, 5, 5, 8, 77, 11, 10
A: 8. 0, 1, 2, 2, 4, 5, 5, 8, 10, 77, 11
A: 9. 0, 1, 2, 2, 4, 5, 5, 8, 10, 11, 77
Seleção
B: 0. 9, 45, 12, 23, 47, 74, 56, 87
B: 1. 9, 12, 45, 23, 47, 74, 56, 87
B: 2. 9, 12, 23, 45, 47, 74, 56, 87
B: 3. 9, 12, 23, 45, 47, 56, 74, 87
 
Shell sort
A=[5,77,2,4,11,10,5,2,8,1,0]
Gap = 11 \ 2 = 5
0:[5,77,2,4,11,10,5,2,8,1,0]
                       0             10
   0                  5
1:[0,77,2,4,11,5,5,2,8,1,10]
       5               77
3:[0,5,2,4,11,5,77,2,8,1,10]
4:[0,5,2,4,11,5,77,2,8,1,10]
5:[0,5,2,4,11,5,77,2,8,1,10]
                1               11
Gap = teto(5 / 2)=3
 7:[0,5,2,4,11,5,77,2,8,1,10]
 8:[0,5,2,4,11,5,77,2,8,1,10]
 9:[0,5,2,4,11,5,77,2,8,1,10]
10:[0,5,2,4,11,5,77,2,8,1,10]
11:[0,5,2,4,11,5,77,2,8,1,10]
                  2         11
    [0,5,2,4,2,5,77,11,8,1,10]
        2       5
12:[0,2,2,4,5,5,77,11,8,1,10]
    [0,2,2,4,5,5,77,11,8,1,10]
                        1         77 
    [0,2,2,4,5,5,1,11,8,77,10]
              1       4
    [0,2,2,1,5,5,4,11,8,77,10]
13:[0,2,2,1,5,5,4,11,8,77,10]
                          10         11
Gap= 3/3 =1
14:[0,2,2,1,5,5,4,10,8,77,11]
15:[0,2,2,1,5,5,4,10,8,77,11]
16:[0,2,2,1,5,5,4,10,8,77,11]
           1  2
    [0,2,1,2,5,5,4,10,8,77,11]
        1 2
    [0,1,2,2,5,5,4,10,8,77,11]
17:[0,1,2,2,5,5,4,10,8,77,11]
18:[0,1,2,2,5,5,4,10,8,77,11]
19:[0,1,2,2,5,5,4,10,8,77,11]
                    4 5
    [0,1,2,2,5,4,5,10,8,77,11]
                 4 5
    [0,1,2,2,4,5,5,10,8,77,11]
20:[0,1,2,2,4,5,5,10,8,77,11]
21:[0,1,2,2,4,5,5,10,8,77,11]
                           8 10
    [0,1,2,2,4,5,5,8,10,77,11]
22:[0,1,2,2,4,5,5,8,10,77,11]
23:[0,1,2,2,4,5,5,8,10,77,11]
                                  11 77
    [0,1,2,2,4,5,5,8,10,11,77]
                  Ordenado.
    [0,1,2,2,4,5,5,8,10,11,77]
Shell sort
B=[9,45,12,23,47,74,56,87]
Gap=5
0:[9,45,12,23,47,74,56,87]
1:[9,45,12,23,47,74,56,87]
2:[9,45,12,23,47,74,56,87]
Gap=3
3:[9,45,12,23,47,74,56,87]
4:[9,45,12,23,47,74,56,87]
5:[9,45,12,23,47,74,56,87]
6:[9,45,12,23,47,74,56,87]
 7[9,45,12,23,47,74,56,87]
Gap=1
 8:[9,45,12,23,47,74,56,87]
10:[9,45,12,23,47,74,56,87]
        12 45
11:[9,12,45,23,47,74,56,87]
            23  45
12:[9,12,23,45,47,74,56,87]
13:[9,12,23,45,47,74,56,87]
14:[9,12,23,45,47,74,56,87]
15:[9,12,23,45,47,74,56,87]
                            56 74
16:[9,12,23,45,47,56,74,87]
17:[9,12,23,45,47,56,74,87]
         Ordenado.
  [9,12,23,45,47,56,74,87]
                             
Quick Sort                  pivo:a[1]=5
A=[5,77,2,11,10,5,2,1,8,1,0] 
0:[5,77,2,11,10,5,2,1,8,1,0]     d > pivô?  Nâo! 
    e                                 d                                           
  
  [0,77,2,11,10,5,2,1,8,1,5]     troca!
    e                                 d 
  [0,77,2,11,10,5,2,1,8,1,5]     e > pivô?  Sim!  
       e                              d 
  
  [0,5,2,11,10,5,2,1,8,1,77]     troca!
       e                          d    
1:[0,5,2,11,10,5,2,1,8,1,77]     d > pivô?  Não! 
       e                         d   
  [0,1,2,11,10,5,2,1,8,5,77]     troca!
       e                         d  
  [0,1,2,11,10,5,2,1,8,5,77]     e > pivô?  Não!  
          e                      d 
  [0,1,2,11,10,5,2,1,8,5,77]     e  incrementa  
             e                   d    
  [0,1,2,11,10,5,2,1,8,5,77]     e > pivô?  Sim! 
             e                   d    
  [0,1,2,5,10,5,2,1,8,11,77]     troca! 
             e                  d    
2:[0,1,2,5,10,5,2,1,8,11,77]     d > pivô?  Sim! 
             e              d    
  [0,1,2,5,10,5,2,1,8,11,77]     d > pivô?  Nâo!   
             e           d    
  [0,1,2,1,10,5,2,5,8,11,77]     troca!  
             e           d    
  [0,1,2,1,10,5,2,5,8,11,77]     e > pivô?  Sim!  
                 e       d    
  [0,1,2,1,5,5,2,10,8,11,77]     troca! 
                e        d  
3:[0,1,2,1,5,5,2,10,8,11,77]     d > pivô?  Nâo! 
                e   d  
  [0,1,2,1,2,5,5,10,8,11,77]     troca!
                e   d  
  [0,1,2,1,2,5,5,10,8,11,77]     e > pivô?  Não! 
                  e d  
  [0,1,2,1,2,5,5,10,8,11,77]    Os indices se 
                     d                       encontram,pivô              
                     e                       está ordenado
pivo:a[1]=0
4:[0,1,2,1,2,5][5][10,8,11,77]   d > pivô?  Sim! 
    e         d                                  
                                        
  [0,1,2,1,2,5][5][10,8,11,77]   d > pivô?  Sim! 
    e      d 
  [0,1,2,1,2,5][5][10,8,11,77]   d > pivô?  Sim! 
    e   d       
  [0,1,2,1,2,5][5][10,8,11,77]   d > pivô?  Sim! 
   e d       
  [0][1,2,1,2,5][5][10,8,11,77]    Os indices se 
    e                                            encontram,pivô 
    d                                            está ordenado
pivo:a[1]=1
5:[0][1,2,1,2,5][5][10,8,11,77]    d > pivô?  Sim!
        e          d                                  
            
  [0][1,2,1,2,5][5][10,8,11,77]    d > pivô?  Sim!
        e       d    
  [0][1,2,1,2,5][5][10,8,11,77]    d > pivô?  Não!
        e    d                                  
                                                  
  [0][1,2,1,2,5][5][10,8,11,77]    troca! 
        e    d
  [0][1,2,1,2,5][5][10,8,11,77]    e > pivô?  Sim!
           e d[0][1,1,2,2,5][5][10,8,11,77]    troca! 
           e d      
6:[0][1,1,2,2,5][5][10,8,11,77]    Os indices se 
           e                                      encontram,pivô 
           d                                      está ordenado
  [0][1][1][2,2,5][5][10,8,11,77]
             e                                     
             d               
7:[0][1][1][2,2,5][5][10,8,11,77]  Testa o outro
         e                                          vetor para 
         d                                          garantir que
                                                     que esteja
                                                     ordenado.                                                                           
pivo:a[1]=2
8:[0][1][1][2,2,5][5][10,8,11,77]  d > pivô?  Sim! 
                 e    d                                         
  [0][1][1][2,2,5][5][10,8,11,77]  d > pivô?  Não! 
                 e d   
  [0][1][1][2,2,5][5][10,8,11,77]   troca! 
                 e d                                                                             
  [0][1][1][2,2,5][5][10,8,11,77]    Os indices se 
                    e                               encontram,pivô 
                    d                                está ordenado
9:[0][1][1][2][2][5][5][10,8,11,77] Testa o outro
                  e                                   vetor para 
                  d                                  garantir que
                                                        que esteja
                                                        ordenado.          
10:[0][1][1][2][2][5][5][10,8,11,77] Testa o outro
                                  e                      vetor para 
                                  d                      garantir que
                                                         que esteja
                                                         ordenado.          
pivo:a[1]=10
11:[0][1][1][2][2][5][5][10,8,11,77]d > pivô?
                                        e          d        Sim!
  [0][1][1][2][2][5][5][10,8,11,77]d > pivô?
                                        e     d              Sim!
  [0][1][1][2][2][5][5][10,8,11,77]d > pivô?
                                     e d                 Não!
  [0][1][1][2][2][5][5][8,10,11,77]         troca
                                    e d                
  [0][1][1][2][2][5][5][8,10,11,77] Os indices se  
                                        d          encontram,pivô 
                                        e          está ordenado
12:[0][1][1][2][2][5][5][8][10][11,77] Testa o                   
                                      e                     outro
                                      d                     vetor para 
                                                            garantir que
                                                            que esteja
                                                            ordenado.
pivo:a[1]=11
13:[0][1][1][2][2][5][5][8][10][11,77] d > pivô?                                                                                                               
                                                  e   d          Sim!
  [0][1][1][2][2][5][5][8][10][11,77] Ordenado!                                                                                                             
                                                e   
                                                d
14:[0][1][1][2][2][5][5][8][10][11][77]                                                                   
                                                         e
                                                         d
                         Ordenado! 
               [0,1,1,2,2,5,5,8,10,11,77]
Quick sort
B=[9,45,12,23,47,74,56,87]
pivo=B[8 \ 2]=B[4]=23       (\ divisão exata)
1:[9,45,12,23,47,74,56,87]   d > pivo? Sim.
    e                               d             d  decrementa.                       
  [9,45,12,23,47,74,56,87]   d > pivo? Sim.
    e                          d                  d  decrementa.
  [9,45,12,23,47,74,56,87]   d > pivo? Sim.
    e                     d                       d  decrementa.
  [9,45,12,23,47,74,56,87]   d > pivo? Sim.
    e                d                            d  decrementa.
  [9,45,12,23,47,74,56,87]   d > pivo? Não.
    e           d                                d  para.
  [9,45,12,23,47,74,56,87]   e > pivo? Não
    e           d                                e  incrementa.
  [9,45,12,23,47,74,56,87]   e > pivo? Sim
        e       d                               
  [9,23,12,45,47,74,56,87]   troca.
       e       d                                
2:[9,23,12,45,47,74,56,87]   d decrementa.
        e  d                               d > pivo? Não.  
  [9,12,23,45,47,74,56,87]   troca.
        e  d                                    .
  [9,12,23,45,47,74,56,87]   e incrementa.
            d  
            e
  [9,12,23,45,47,74,56,87]   Os indices se.
            d                               encontram o pivô
            e                               está ordenado.
pivo=A[2\2]=A[1]=9.
3:[9,12][23][45,47,74,56,87]   d > pivo? Sim.
    e  d                                      d  decrementa. 
                                            
  [9,12][23][45,47,74,56,87]  Os indices se 
    e                                          encontram,pivô 
    d                       .                  ordenado.
4:[9][12][23][45,47,74,56,87] O teste é feito no 
         d                                    vetor subdividido
         e                                    para garantir que o      
                                        elemento está ordenado.
pivo=B[5 \ 2]=B[2]=47
5:[9][12][23][45,47,74,56,87] d > pivo? Sim.
                       e                 d     d  decrementa.
  [9][12][23][45,47,74,56,87] d > pivo? Sim.
                       e            d         d  decrementa.
  [9][12][23][45,47,74,56,87] d > pivo? Sim.
                       e       d              d  decrementa.
  [9][12][23][45,47,74,56,87] d > pivo?Não.
                       e  d                   d  para.
  [9][12][23][45,47,74,56,87] e > pivo?Não.
                       e  d                   e  incrementa.
  [9][12][23][45,47,74,56,87] Os indices se.
                          d                    encontram,pivô 
                          e                     ordenado.                                         
6:[9][12][23][45][47][74,56,87] O teste é feito no 
                      d                           vetor subdividido
                      e                         para garantir que o
                                        elemento está ordenado.
pivo=B[3 \ 2]=B[1]=74
6:[9][12][23][45][47][74,56,87]  d > pivo? Sim.
                                    e        d     d  decrementa. 
  [9][12][23][45][47][74,56,87]  d > pivo? Sim.
                                    e  d          d  decrementa. 
  [9][12][23][45][47][74,56,87]  d > pivo? Não.
                                    e  d          
  [9][12][23][45][47][56,74,87]  troca.
                                    e  d          
  [9][12][23][45][47][56,74,87] e incrementa.
                                        d 
                                        e       
7:[9][12][23][45][47][56][74][87] pivo ordenado.
                                               
8:[9][12][23][45][47][56][74][87] Teste é feito 
                                    d               nas subdivisões.
                                    e     
9:[9][12][23][45][47][56][74][87]  
                                                 d 
                                                 e
  [9,12,23,45,47,56,74,87] Ordenado. 
          
Segue as questões Heap eMerge