0 votos
19 visitas
perguntado em Programação por (940 pontos)
Por que um array ordenado pode ser processado mais rapidamente que um array fora de ordem?

Dê exemplos caso possível.

1 Resposta

0 votos
respondida por (940 pontos)

A maioria das linguaguens de programação apresenta estruturas de tomada de decisão como o IF.

Imagine um IF

if (data[c] >= 128)
    sum += data[c];
 

Imagine a o seguinte Array ORDENADO e como seria a decisão de cada IF(Not True-N, True-T) que é denotado em Branch.
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
Branch1 = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

Imagine a o seguinte Array DESORDENADO e como seria a decisão de cada IF(Not True-N, True-T) que é denotado em Branch.
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182...
Branch2 =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T...


Imagine que os Branch fossem trilhos de trem. Por meio de qual trilhos o trem chegaria mais rápido ao destino?
O Branch1 pois necessita de menos tomadas de decisões diferentes. Ou seja, quanto menos tomada de decisões, melhor. Assim se tivermos um array ordenado teremos decisões mais lineares que influirá em um código rodando mais rapidamente.
 

...