Quick sort ou ordenação rápida usando Javascript

O quick sort é um algorítimo rápido e eficiente de ordenaçãp por comparação não estável. Basea-se na estratégia de dividir e conquistar.

A estratégia de Dividir e Conquistar.

Em ciência da computação, dividir e consquistar é uma estratégia usada para quebrar o problema á ser resolvido em partes menores. Então a solução aplicada na solução de uma parte menor do seu problema, será a mesma para resolver todas as outras partes menores resultantes, utilizando recursividade para tal.

Aplicando a técnica de Dividir e Conquistar para executar ordenação de dados.

Dado um vetor de valores do mesmo tipo e possivelmente desordenado, o primeiro passo é dividir esse vetor em duas partes, e para isso escolhemos uma chave do vetor que será usada como delimitador para a divisão do vetor 2 partes. Á essa chave damos o nome de pivô. Ás partes divididas do vetor, poderemos dar o nome de ladoEsquerdo e ladoDireito.

Os critérios para se escolher qual chave do vetor agirá como pivô podem variar, podendo ser assim o primeiro, o último ou até mesmo o elemento que se encontra no meio do vetor.

Performance

Há diferentes implementações do algorítimo quickSort focando uma melhor performance. O meio mais simples de implementar é o Método de partição de Lomuto, porém este método pode perder performance e atingir O(n^2) quando o vetor já está ordenado ou possui muitos elementos iguais. Métodos como Hoare e Dual-Pivot Quicksort são mais eficientes.

Complexidade de tempo:

Pior caso
O(n^2) comparações,
O(n^2) trocas
Melhor caso
O(n log n) comparações,
O(1) trocas
Performance média
O(n log n) comparações,
O(n log n) trocas

Complexidade de espaço:

Pior caso e Caso médio
O(n)
Melhor caso
O(n log n)

Implementação usando o primeiro elemento do vetor como pivô:

Array.prototype.ordenarRapido = function() {
  const vetor = this;

  // caso base
  // vetor já está ordenado
  if (vetor.length <= 1) {
    return vetor;
  }

  // primeiro elemento do array como pivo
  let pivo = vetor[0];
  // armazena numeros menores
  let subVetorEsquerdo = [];
  // armazena numeros maiores
  let subVetorDireito = [];

  // inicia comparacoes apos o pivo
  for (let i = 1; i < vetor.length; i++) {
    const valorAtual = vetor[i];
    if (valorAtual < pivo) {
      subVetorEsquerdo.push(valorAtual);
    } else {
      subVetorDireito.push(valorAtual);
    }
  }
  console.log(`aplicando solução parcial: [...[${subVetorEsquerdo.join(', ')}].ordenarRapido(), ${pivo}, ...[${subVetorDireito.join(', ')}].ordenarRapido()]`)
  
  return subVetorEsquerdo.ordenarRapido().concat([pivo] , subVetorDireito.ordenarRapido());
};


console.log(
  [5, 3, 7, 6, 2, 9].ordenarRapido()
);

// aplicando solução parcial: [...[3, 2].ordenarRapido(), 5, ...[7, 6, 9].ordenarRapido()]
// aplicando solução parcial: [...[2].ordenarRapido(), 3, ...[].ordenarRapido()]
// aplicando solução parcial: [...[6].ordenarRapido(), 7, ...[9].ordenarRapido()]
// [ 2, 3, 5, 6, 7, 9 ]

Queda de performance

Para provar a teoria do método de partição de Lomuto pode atingir O(n^2), faremos testes com vetores com 10 e 100 elementos e vetores ordenados e desordenados.

let comparacoes = 0
let trocas = 0
const ordenarRapido = (vetor) => {
  if (vetor.length <= 1) return vetor;
  let pivo = vetor[0];
  let subVetorEsquerdo = [];
  let subVetorDireito = [];
  for (let i = 1; i < vetor.length; i++) {
    const valorAtual = vetor[i];
    if (valorAtual < pivo) {
      subVetorEsquerdo.push(valorAtual);
    } else {
      subVetorDireito.push(valorAtual);
    }
    comparacoes++;
    trocas++;
  }
  trocas++;
  
  return ordenarRapido(subVetorEsquerdo).concat([pivo] , ordenarRapido(subVetorDireito));
};

console.log('-------------------------------------> Vetor Desordenado com 100 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [
    100, 66, 46, 31,  2, 90, 61, 37, 16,  3, 24, 73,
     44, 84, 86, 32, 98, 58, 89, 54, 21, 18, 78, 35,
     91, 23, 26, 39,  9, 64, 59, 81, 36, 92, 14, 29,
     57, 19, 60, 52,  7, 15,  4, 56, 71, 38, 79, 13,
     27, 28, 88, 53, 41,  8, 82, 22, 20, 95, 80, 85,
     76, 69, 17, 97, 34, 75, 12, 25, 70, 55, 65, 42,
     72, 47, 30, 94, 40, 45, 74,  5, 11, 77, 48, 87,
      1, 51, 99, 50, 62, 96, 63, 43, 93, 83, 49,  6,
     33, 67, 68, 10
  ];


  const timeStart = performance.now();
  const result = ordenarRapido(arr);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Ordenado com 100 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [];
  let i = 1;
  while(arr.length < 100){
    arr.push(i);
    i++;
  }
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Ordenado com 100 elementos iguais')
{
  comparacoes = 0
  trocas = 0
  const arr = [];
  let i = 1;
  while(arr.length < 100){
    arr.push(1);
    i++;
  }
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Ordenado com 10 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Ordenado com 10 elementos iguais')
{
  comparacoes = 0
  trocas = 0
  const arr = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Desordenado com 10 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [9, 1, 10, 2, 8, 3, 7, 4, 6, 5];
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Desordenado com 10 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [];
  while(arr.length < 10){
      var r = Math.floor(Math.random() * 100) + 1;
      if(arr.indexOf(r) === -1) arr.push(r);
  }
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

Resultado

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 666, trocas: 731, tempo: 0.271575927734375 }
-------------------------------------> Vetor Ordenado com 100 elementos diferentes
{ comparacoes: 4950, trocas: 5049, tempo: 0.6909520626068115 }
-------------------------------------> Vetor Ordenado com 100 elementos iguais
{ comparacoes: 4950, trocas: 5049, tempo: 0.7713660001754761 }
-------------------------------------> Vetor Ordenado com 10 elementos diferentes
{ comparacoes: 45, trocas: 54, tempo: 0.014504075050354004 }
-------------------------------------> Vetor Ordenado com 10 elementos iguais
{ comparacoes: 45, trocas: 54, tempo: 0.01786494255065918 }
-------------------------------------> Vetor Desordenado com 10 elementos diferentes
{ comparacoes: 37, trocas: 45, tempo: 0.018097996711730957 }
-------------------------------------> Vetor Desordenado com 10 elementos diferentes
{ comparacoes: 35, trocas: 42, tempo: 0.020820021629333496 }

Implementação do quick sort com dois pivôs:

Dentre as as tentativas de melhoria de performance do algorítimo, podemos citar a implementação Dual-Pivot Quicksort, particionando o o vetor de entrada em 3 partes e utlizando 2 pivôs.

Essa abordagem é mais performática que o método de Lomuto, por exemplo, quando há uma entrada de dados consideravelmente maior.

function troca(vetor, chaveEsquerda, chaveDireita) {
  let auxiliar = vetor[chaveEsquerda];
  vetor[chaveEsquerda] = vetor[chaveDireita];
  vetor[chaveDireita] = auxiliar;
}

function dividir(vetor, chaveEsquerda, chaveDireita) {
  let pivo = vetor[Math.floor((chaveDireita + chaveEsquerda) / 2)]; // element do meio
  while (chaveEsquerda <= chaveDireita) {
    while (vetor[chaveEsquerda] < pivo) {
      chaveEsquerda++;
    }
    while (vetor[chaveDireita] > pivo) {
      chaveDireita--;
    }
    if (chaveEsquerda <= chaveDireita) {
      troca(vetor, chaveEsquerda, chaveDireita);
      chaveEsquerda++;
      chaveDireita--;
    }
  }
  return chaveEsquerda;
}

function ordenarRapido(vetor, chaveEsquerda, chaveDireita) {
  let pivo;
  if (vetor.length > 1) {
    
    pivo = dividir(vetor, chaveEsquerda, chaveDireita); //pivo returned from dividir
    
    if (chaveEsquerda < pivo - 1) { // mais elementos do lado esquerdo do pivo
      ordenarRapido(vetor, chaveEsquerda, pivo - 1);
    }
    if (pivo < chaveDireita) { // mais elementos do lado direito do pivo
      ordenarRapido(vetor, pivo, chaveDireita);
    }
  }
  return vetor;
}

Testando a performance

let trocas = 0;
let comparacoes = 0;

function troca(vetor, chaveEsquerda, chaveDireita) {
  let auxiliar = vetor[chaveEsquerda];
  vetor[chaveEsquerda] = vetor[chaveDireita];
  vetor[chaveDireita] = auxiliar;
  trocas++;
}



function dividir(vetor, chaveEsquerda, chaveDireita) {
  let pivo = vetor[Math.floor((chaveDireita + chaveEsquerda) / 2)]; // element do meio
  while (chaveEsquerda <= chaveDireita) {
    while (vetor[chaveEsquerda] < pivo) {
      chaveEsquerda++;
      comparacoes++;
    }
    while (vetor[chaveDireita] > pivo) {
      chaveDireita--;
      comparacoes++;
    }
    if (chaveEsquerda <= chaveDireita) {
      troca(vetor, chaveEsquerda, chaveDireita);
      chaveEsquerda++;
      chaveDireita--;
      comparacoes++;
    }
  }
  return chaveEsquerda;
}


function ordenarRapido(vetor, chaveEsquerda, chaveDireita) {
  let pivo;
  if (vetor.length > 1) {
    
    pivo = dividir(vetor, chaveEsquerda, chaveDireita); //pivo returned from dividir
    
    if (chaveEsquerda < pivo - 1) { // mais elementos do lado esquerdo do pivo
      ordenarRapido(vetor, chaveEsquerda, pivo - 1);
    }
    if (pivo < chaveDireita) { // mais elementos do lado direito do pivo
      ordenarRapido(vetor, pivo, chaveDireita);
    }
  }
  return vetor;
}

console.log('-------------------------------------> Vetor Desordenado com 100 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [
    100, 66, 46, 31,  2, 90, 61, 37, 16,  3, 24, 73,
     44, 84, 86, 32, 98, 58, 89, 54, 21, 18, 78, 35,
     91, 23, 26, 39,  9, 64, 59, 81, 36, 92, 14, 29,
     57, 19, 60, 52,  7, 15,  4, 56, 71, 38, 79, 13,
     27, 28, 88, 53, 41,  8, 82, 22, 20, 95, 80, 85,
     76, 69, 17, 97, 34, 75, 12, 25, 70, 55, 65, 42,
     72, 47, 30, 94, 40, 45, 74,  5, 11, 77, 48, 87,
      1, 51, 99, 50, 62, 96, 63, 43, 93, 83, 49,  6,
     33, 67, 68, 10
  ];

  const timeStart = performance.now();
  const result = ordenarRapido(arr, 0, arr.length);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Ordenado com 100 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [];
  let i = 1;
  while(arr.length < 100){
    arr.push(i);
    i++;
  }
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr, 0, arr.length);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Ordenado com 100 elementos iguais')
{
  comparacoes = 0
  trocas = 0
  const arr = [];
  let i = 1;
  while(arr.length < 100){
    arr.push(1);
    i++;
  }
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr, 0, arr.length);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Ordenado com 10 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr, 0, arr.length);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Ordenado com 10 elementos iguais')
{
  comparacoes = 0
  trocas = 0
  const arr = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr, 0, arr.length);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Desordenado com 10 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [9, 1, 10, 2, 8, 3, 7, 4, 6, 5];
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr, 0, arr.length);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

console.log('-------------------------------------> Vetor Desordenado com 10 elementos diferentes')
{
  comparacoes = 0
  trocas = 0
  const arr = [];
  while(arr.length < 10){
      var r = Math.floor(Math.random() * 100) + 1;
      if(arr.indexOf(r) === -1) arr.push(r);
  }
  // console.log(arr)

  const timeStart = performance.now();
  const result = ordenarRapido(arr, 0, arr.length);
  const timeEnd = performance.now();
  const tempo = timeEnd - timeStart;
  // console.log( result );

  console.log({
    comparacoes, trocas, tempo,
  });
}

Resultado:

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 648, trocas: 198, tempo: 0.3790459632873535 }
-------------------------------------> Vetor Ordenado com 100 elementos diferentes
{ comparacoes: 580, trocas: 100, tempo: 0.08041703701019287 }
-------------------------------------> Vetor Ordenado com 100 elementos iguais
{ comparacoes: 361, trocas: 361, tempo: 0.07846701145172119 }
-------------------------------------> Vetor Ordenado com 10 elementos diferentes
{ comparacoes: 29, trocas: 10, tempo: 0.013962030410766602 }
-------------------------------------> Vetor Ordenado com 10 elementos iguais
{ comparacoes: 22, trocas: 22, tempo: 0.1363229751586914 }
-------------------------------------> Vetor Desordenado com 10 elementos diferentes
{ comparacoes: 34, trocas: 13, tempo: 0.010295987129211426 }
-------------------------------------> Vetor Desordenado com 10 elementos diferentes
{ comparacoes: 36, trocas: 14, tempo: 0.009860038757324219 }

Agora comparando ambos métodos:

Método de partição de Lomuto

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 666, trocas: 731, tempo: 0.271575927734375 }
-------------------------------------> Vetor Ordenado com 100 elementos diferentes
{ comparacoes: 4950, trocas: 5049, tempo: 0.6909520626068115 }
-------------------------------------> Vetor Ordenado com 100 elementos iguais
{ comparacoes: 4950, trocas: 5049, tempo: 0.7713660001754761 }
-------------------------------------> Vetor Ordenado com 10 elementos diferentes
{ comparacoes: 45, trocas: 54, tempo: 0.014504075050354004 }
-------------------------------------> Vetor Ordenado com 10 elementos iguais
{ comparacoes: 45, trocas: 54, tempo: 0.01786494255065918 }
-------------------------------------> Vetor Desordenado com 10 elementos diferentes
{ comparacoes: 37, trocas: 45, tempo: 0.018097996711730957 }
-------------------------------------> Vetor Desordenado com 10 elementos diferentes
{ comparacoes: 35, trocas: 42, tempo: 0.020820021629333496 }

Dual-Pivot Quicksort

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 648, trocas: 198, tempo: 0.3790459632873535 }
-------------------------------------> Vetor Ordenado com 100 elementos diferentes
{ comparacoes: 580, trocas: 100, tempo: 0.08041703701019287 }
-------------------------------------> Vetor Ordenado com 100 elementos iguais
{ comparacoes: 361, trocas: 361, tempo: 0.07846701145172119 }
-------------------------------------> Vetor Ordenado com 10 elementos diferentes
{ comparacoes: 29, trocas: 10, tempo: 0.013962030410766602 }
-------------------------------------> Vetor Ordenado com 10 elementos iguais
{ comparacoes: 22, trocas: 22, tempo: 0.1363229751586914 }
-------------------------------------> Vetor Desordenado com 10 elementos diferentes
{ comparacoes: 34, trocas: 13, tempo: 0.010295987129211426 }
-------------------------------------> Vetor Desordenado com 10 elementos diferentes
{ comparacoes: 36, trocas: 14, tempo: 0.009860038757324219 }

Agora comparando somente vetores desordenados com 100 elementos

Vetor 1

[
  35, 13, 52, 41, 82, 23, 27,  72, 39, 62,  1, 60,
  91, 12, 19, 17, 88, 48, 92,  97,  4, 46, 38, 31,
  54, 95, 30,  7, 66, 65, 75,  21, 73, 42, 94, 51,
  18, 25, 22, 83,  3, 64, 50,  71, 16, 14, 37, 90,
  29, 33, 59, 26, 45, 80, 85, 100, 55, 79, 10, 34,
  76, 96, 87,  8, 99, 47, 53,  28,  9, 57, 86, 49,
  15, 63, 11, 20, 81, 32, 40,  93, 67, 98, 43,  5,
   2, 84, 68, 77, 24, 69, 58,  61, 36, 89, 74, 70,
  78,  6, 56, 44
]

1 pivô, 2 particoes

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 555, trocas: 622, tempo: 0.2453920841217041 }

2 pivôs, 3 partições

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 658, trocas: 195, tempo: 0.36329591274261475 }

Vetor 2

[
  30, 68, 29, 31, 85, 56,  96,  6, 67, 87, 60, 35,
  93, 44, 79, 91, 11, 32,  45, 28, 12,  5, 98, 78,
  61, 41, 21,  3, 99, 49,  76, 64, 10, 86,  8, 36,
  15, 81, 37, 73,  9, 19,   4, 24, 90, 70, 42, 88,
  23, 39, 25, 72, 62, 13, 100, 34, 95, 46, 75, 80,
  65, 69, 74, 43, 92,  2,  97, 58, 48, 63, 77, 52,
  33, 89, 71, 27, 83, 14,  47, 54, 18, 57, 53, 51,
  17, 50, 38, 20, 40,  7,  22, 26, 16, 82, 66, 84,
   1, 94, 59, 55
]

1 pivô, 2 particoes

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 643, trocas: 709, tempo: 0.28028106689453125 }

2 pivôs, 3 partições

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 641, trocas: 209, tempo: 0.3620450496673584 }

Vetor 3

[
  17, 52, 62, 73, 22,  57, 92, 99, 38, 71, 96, 76,
  87, 58, 20,  6, 48,  32, 16, 39, 89, 27, 19, 90,
   5, 59, 24, 94, 14,  86, 63, 33, 55,  9, 97, 56,
  37, 47, 15, 78, 79,  67, 26, 83, 29, 10, 42, 60,
  84, 30, 11, 61, 45,  43, 82, 28,  2, 46, 69, 70,
  31, 85, 18, 13, 12,  93,  7, 50,  1, 44, 34,  3,
  91, 53, 25,  8, 81,  95, 36, 98, 41, 21, 80, 77,
  65, 75, 40, 35, 51, 100, 72, 66, 54,  4, 68, 74,
  49, 23, 64, 88
]

1 pivô, 2 particoes

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 616, trocas: 681, tempo: 0.25136101245880127 }

2 pivôs, 3 partições

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 678, trocas: 198, tempo: 0.3771599531173706 }

Vetor 4

[
    100, 66, 46, 31,  2, 90, 61, 37, 16,  3, 24, 73,
     44, 84, 86, 32, 98, 58, 89, 54, 21, 18, 78, 35,
     91, 23, 26, 39,  9, 64, 59, 81, 36, 92, 14, 29,
     57, 19, 60, 52,  7, 15,  4, 56, 71, 38, 79, 13,
     27, 28, 88, 53, 41,  8, 82, 22, 20, 95, 80, 85,
     76, 69, 17, 97, 34, 75, 12, 25, 70, 55, 65, 42,
     72, 47, 30, 94, 40, 45, 74,  5, 11, 77, 48, 87,
      1, 51, 99, 50, 62, 96, 63, 43, 93, 83, 49,  6,
     33, 67, 68, 10
]

1 pivô, 2 particoes

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 666, trocas: 731, tempo: 0.25054609775543213 }

2 pivôs, 3 partições

-------------------------------------> Vetor Desordenado com 100 elementos diferentes
{ comparacoes: 648, trocas: 198, tempo: 0.37080299854278564 }