Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Desvio Padrão e Bubble Sort

0 votos
23 visitas
perguntada Out 11 em Economia por CICERO FILHO (26 pontos)  
editado Out 12 por CICERO FILHO

Calcule o desvio padrão do número de passes bubble sort, e o expresse em termos de n e da função P(n).

Referência: livro "The art of computer programming", volume 3, página 134, exercício 7. Autor: Donald E. Knuth.

Compartilhe

1 Resposta

0 votos
respondida Out 11 por CICERO FILHO (26 pontos)  
republicada Out 22 por CICERO FILHO

Da equação (7) temos da seção 5.2.2 páginas 108 e 109 do livro “The Art of Computer Programming”, que:

\[A_{ave}=n+1-\sum_{k=0}^{n}\frac{k^{n-k}k!}{n!}=n+1-P(n)\]

Onde \(P(n)\) é função cujo valor assintótico foi encontrado para ser: \(\sqrt{\frac{\pi}{2}}-\frac{2}{3}+O\left(\frac{1}{\sqrt{n}}\right)\).

Assim,

\[\sqrt{(2 (n + 1) (1 + P(n) - P(n + 1)) - P(n)^2}\\\]

Reescrevendo:

\[\sqrt{( n + 1) - 2 (P(n+1) - 1)) - P(n)^2}\\\]

Derivando:

\[\frac{d}{dn}={(\sqrt{2( n + 1) (P(n)-P(n+1)+1)-P(n)^2}\ } \]

\[\frac{(P(n) (-P´(n)) + (n + 1) (P´(n) - P´(n + 1)) + P(n) - P(n + 1) + 1)}{\sqrt{2( n + 1) (P(n)-P(n+1)+1)- P(n)^2}\\}\]

Possível derivação:

\[\frac{d}{dn} (\sqrt{(-P(n)^2 + 2 (1 + n) (1 + P(n) - P(1 + n))} )\]

\[\frac{d}{dn} (\sqrt{(2 (n + 1) (P(n) - P(n + 1) + 1) - P(n)^2))}) = \frac{d\sqrt(u))}{du} \frac {du} {dn}\]

onde \(u = 2 (n + 1) (P(n) - P(n + 1) + 1) - P(n)^2\) e \(\frac{d} {du}(\sqrt{u})= \frac{1}{2\sqrt{u}}\)

\[\frac {\frac {d}{dn}(-P(n)^2 + 2 (1 + n) (1 + P(n) - P(1 + n)))}{2\sqrt{(-P(n)^2 + 2 (1 + n) (1 + P(n) - P(1 + n))}}\]

Diferenciando a soma termo por termo e os fatores de saída constantes:

\[\frac{=(-(\frac{d}{dn}(P(n)^2)) + 2 (\frac{d}{dn}((1 + n) (1 + P(n) - P(1 + n))))}{2\sqrt{-P(n)^2 + 2 (1 + n) (1 + P(n) - P(1 + n))}}\]

Usando a regra da cadeia, \(\frac{d}{dn} (P(n)^2) = \frac{d(u^2)}{du}\frac{du}{dn}\), onde \(u=P(n)\) e \(\frac{d}{du}(u^2) = 2 u.\)

\[=\frac{(2 \frac{d}{dn}((1 + n) (1 + P(n) - P(1 + n)))) - 2 (\frac{d}{dn}(P(n))) P(n))}{2 \sqrt{(-P(n)^2 + 2 (1 + n) (1 + P(n) - P(1 + n))}}\]

Usando novamente a regra da cadeia, \(\frac{d}{dn}(P(n)) = \frac{dP(u)}{du}\frac{du}{dn}\), onde \(u = n\) e \(\frac{d}{du}(P(u)) = P´(u).\)

\[=\frac{(2 \frac{d}{dn}((1 + n) (1 + P(n) - P(1 + n)))) - (\frac{d}{dn}(n)) P´(n) 2 P(n)}{2 \sqrt{(-P(n)^2 + 2 (1 + n) (1 + P(n) - P(1 + n))}}\]

Usando a regra do produto, \(\frac{d}{dn} (u v) = v \frac{du}{dn} + u \frac{dv}{dn}\) , onde \(u = n + 1\) e \(v = P(n) - P(n + 1) + 1.\)

E depois realizando diversos procedimentos de simplificação algébrica, obtêm-se:

\[=\frac{ (1 + P(n) - P(1 + n) - P(n) P´(n) + (1 + n) (P´(n) - P´(1 + n)))}{\sqrt{(-P(n)^2 + 2 (1 + n) (1 + P(n) - P(1 + n))})} \]

Essa foi a maior simplificação possível.

Resolução computacional genérica para a questão:

    list=[]
num=int(input("Quantidade de números"))
print("entrada de valores:")
for k in range(num):
    list.append(int(input()))
    print("lista nao classificada:", list)
    for j in range:len(list-1)
    for i in range(len(list)-1-j):
        if list[i]>list[i+1]:
            list[i],list[i+1]=list[i+1],list[i]
            print(list)
            then:print(list)
            print()
            print("lista classificada:",list)
            import math
            def mean(list):
                return sum(list)*1.0/len(list)
                def stanDev(list):
                            length=len(list)
                            m=mean(list)
                            total_sum=0
                            for x in range(length):
                                total_sum +=(list[x]-m)**2
                                under_root=total_sum*1.0/length
                                return math.sqrt(under_root)
                            stan_dev=standev(list)
                            print(stan_Dev)

Simulação de Exemplo:

Supondo uma lista hipotética de números para classificar
[15,20,5,16,74,35,46,12], será calculada a lista parcialmente
classificada após uma passagem completa bubble sort. Na sequência será
calculado o desvio padrão dos resultados.

def shortBubbleSort(alist):
    exchanges = True
    passnum = len(alist)-1
    while passnum > 0 and exchanges:
       exchanges = False
       for i in range(passnum):
           if alist[i]>alist[i+1]:
               exchanges = True
               temp = alist[i]
               alist[i] = alist[i+1]
               alist[i+1] = temp
       passnum = passnum-1

alist=[15,20,5,16,74,35,46,12]
shortBubbleSort(alist)
print(alist)

[5, 12, 15, 16, 20, 35, 46, 74]

import statistics

#Passe 1
list = [5, 12, 15, 16, 20, 35, 46, 74]
print("List : " + str(list))
st_dev = statistics.pstdev(list)
print("Desvio padrão da lista 1: " + str(st_dev))

Desvio padrão da lista 1: 21.362569484965988
comentou Nov 6 por bonfim_tiago (6 pontos)  
Em primeiro lugar, gostaria de te parabenizar pelos códigos gerados! Os códigos são intuitivos, modularizados e concisos.
   Tendo isso em vista, os comentários que eu vou fazer aqui devem ser encarados como oportunidades de aprimoramento somente, não sendo nada grave.
    Bom, eu senti falta de alguns comentários pelo código. Ainda que o código seja intuitivo, eu acredito que documentar, por exemplo, a declaração de funções pode ser uma prática muito importante na manutenção futura desse programa. Uma breve descrição da funcionalidade da função e dos parâmetros de entrada e saída bastaria. Além disso, o fragmento:
while passnum > 0 and exchanges:
       exchanges = False
       for i in range(passnum):
           if alist[i]>alist[i+1]:
               exchanges = True
               temp = alist[i]
               alist[i] = alist[i+1]
               alist[i+1] = temp

   ganharia bastante com a adição de alguns breves comentários. Outro exemplo ainda seria o trecho:
for k in range(num):
    list.append(int(input()))
    print("lista nao classificada:", list)
    for j in range:len(list-1)
    for i in range(len(list)-1-j):
        if list[i]>list[i+1]:
            list[i],list[i+1]=list[i+1],list[i]
            print(list)
            then:print(list)
            print()
            print("lista classificada:",list)
            import math
            def mean(list):
                return sum(list)*1.0/len(list)
                def stanDev(list):
                            length=len(list)
                            m=mean(list)
                            total_sum=0
                            for x in range(length):
                                total_sum +=(list[x]-m)**2
                                under_root=total_sum*1.0/length
                                return math.sqrt(under_root)
                            stan_dev=standev(list)
                            print(stan_Dev)

   Depois, uma prática que eu venho adotando no Python há algum tempo consiste em apresentar o tipo esperado do dado quando da declaração dos parâmetros de entrada de uma função. Por exemplo, poderia ser a declaração de uma variável do tipo int como "a: int" ao invés de somente "a". Isso pode não fazer nenhuma diferença para o Python, mas confere um nível muito interessante de legibilidade aos códigos. Por isso, a recomendação.
   Por fim, uma prática interessante é sempre adicionar após a declaração das funções o fragmento __name__ == '__main__' para explicar ao leitor que o seu código de testes principal está vindo. Isso facilita a segmentação e manutenção do código.

   No mais, parabéns e um grande abraço!
comentou Nov 8 por CICERO FILHO (26 pontos)  
Muito obrigado pelo comentário! Farei o ajustei, com a inserção dos comentários e postarei para ver
os resultados! Abs.
...