1
resposta

Função recursiva Quick Sort

Olá! Fiquei com um pouco de dúvida sobre a recursão do código implementado e queria entender melhor, alguém poderia me ajudar, por favor?

Nesse código abaixo (desenvolvido na aula):

function quickSort(array, esquerda, direita) {
  let indiceAtual = particiona(array, esquerda, direita);
  if (esquerda < indiceAtual - 1) {
    quickSort(array, esquerda, indiceAtual - 1);
  }
  if (indiceAtual < direita) {
    quickSort(array, indiceAtual, direita);
  }
  return array;
}

A função "quickSort" retorna um array, porém quando chamamos ela dentro do bloco "if", para onde esse array que ela retorna vai?

Se estivesse escrito algo do tipo "array = quickSort()", faria mais sentido pra mim, pois o valor retornado será guardado. Então, como funciona essa chamada do quickSort dentro do if?

Fiquei meio confuso, pois geralmente nas funções recursivas que retornam algo, nós guardamos esse valor... Por exemplo:

function mergeSort(array) {
  if (array.length > 1) {
    const meio = Math.floor(array.length / 2);
    const parte1 = mergeSort(array.slice(0, meio));
    const parte2 = mergeSort(array.slice(meio, array.length));
    array = ordena(parte1, parte2);
  }
  return array;
}

Nessa função acima, o "mergeSort" retorna um array também, porém o valor desse array é guardado em variáveis, então o código faz total sentido pra mim. Essa mesma lógica é usada em outros códigos recursivos, então fiquei com dúvida do porquê chamamos daquela forma dentro do bloco if, sem guardar o valor...

Meu chute é que automaticamente ele atualize o valor do array, fazendo algo do tipo "array = quickSort()", mas não tenho certeza e não consegui encontrar pesquisando na internet... Poderiam me ajudar nisso?

1 resposta

Olá Matheus, tudo bem? Espero que sim!

Desde já peço desculpa pela demora para responder o seu tópico.

Na função "quickSort", quando chamamos a função recursivamente dentro do bloco "if", o array retornado pela função é simplesmente ignorado. Isso porque a função "quickSort" já está modificando o array original que foi passado como parâmetro, então não é necessário guardar o valor retornado em uma variável.

Ao chamar a função recursivamente dentro do bloco "if", estamos apenas dividindo o array em subarrays menores e aplicando a mesma lógica de ordenação neles. Como a função "quickSort" já está modificando o array original, não precisamos guardar o valor retornado em uma variável.

Já na função "mergeSort", como você mencionou, o valor retornado pela função é guardado em variáveis, pois a lógica de ordenação é um pouco diferente. Na função "mergeSort", estamos dividindo o array em subarrays menores, ordenando cada um deles e depois unindo-os novamente em um único array ordenado. Por isso, precisamos guardar os valores retornados em variáveis para poder unir os subarrays ordenados.

Espero ter ajudado a esclarecer sua dúvida! Se tiver mais alguma pergunta, fique à vontade para perguntar.

Bons estudos!

Caso este post tenha lhe ajudado, por favor, marcar como solucionado ✓.