Solucionado (ver solução)
Solucionado
(ver solução)
1
resposta

Dúvida no algoritmo quickSort

bom dia,

No teste de mesa utilizando vários consoles.log percebi que em algumas etapas do loop o pivo fica com valor de índice fracionado, por exemplo 0.5 | 6.5 | 4.5, no entanto percebi que isso não é um problema pois ele acaba arredando esse valor para baixo.

array:  [
  { titulo: 'Python', preco: 20 },
  { titulo: 'PHP', preco: 15 },
  { titulo: 'Rust', preco: 22 },
  { titulo: 'Java', preco: 30 },
  { titulo: 'Elixir', preco: 50 },
  { titulo: 'C++', preco: 35 },
  { titulo: 'Scala', preco: 40 },
  { titulo: 'Ruby', preco: 28 },
  { titulo: 'JavaScript', preco: 25 },
  { titulo: 'C#', preco: 33 },
  { titulo: 'Go', preco: 45 }
]
esquerda, direita:  0 1
array.length:  11
pivo:  0.5 { titulo: 'Python', preco: 20 }
atualEsquerda, atualDireita:  0 1
array:  [
  { titulo: 'PHP', preco: 15 },
  { titulo: 'Python', preco: 20 },
  { titulo: 'Rust', preco: 22 },
  { titulo: 'Java', preco: 30 },
  { titulo: 'Elixir', preco: 50 },
  { titulo: 'C++', preco: 35 },
  { titulo: 'Scala', preco: 40 },
  { titulo: 'Ruby', preco: 28 },
  { titulo: 'JavaScript', preco: 25 },
  { titulo: 'C#', preco: 33 },
  { titulo: 'Go', preco: 45 }
]
esquerda, direita:  3 10
array.length:  11
pivo:  6.5 { titulo: 'Scala', preco: 40 }
atualEsquerda, atualDireita:  3 10
atualEsquerda:  3
array[atualEsquerda].preco < pivo.preco:  30 40
atualDireita:  10
array[atualDireita].preco > pivo.preco:  45 40
atualEsquerda, atualDireita:  5 8
atualEsquerda:  5
array[atualEsquerda].preco < pivo.preco:  35 40
atualEsquerda, atualDireita:  7 7
atualEsquerda:  7
array[atualEsquerda].preco < pivo.preco:  28 40

A minha dúvida é se isso não compromete a performance do algoritmo tornando este mais custoso com grandes volumes de dados a serem processados?

Essa é apenas uma dúvida conceitual.

1 resposta
solução!

Olá! Tudo bem com você?

Em relação ao valor fracionado do pivô, isso não compromete a performance do algoritmo. Na verdade, o que acontece é que o valor fracionado é arredondado para baixo, o que não afeta a ordem dos elementos no array.

O que pode afetar a performance do algoritmo é a escolha do pivô em si. Se o pivô for escolhido de forma inadequada, pode ocorrer um desbalanceamento na partição do array, o que pode aumentar o número de comparações necessárias para ordenar o array.

Por isso, é importante escolher o pivô de forma estratégica, considerando as características do array que está sendo ordenado.

Espero ter esclarecido a sua dúvida. Caso tenha mais alguma dúvida, com relação a este tópico, estarei à disposição.

Grande abraço e bons estudos!