by evelyn

Ordenando Objetos em JavaScript com QuickSort e pesquisando com Binary Search

Neste artigo, vamos criar uma função QuickSort capaz de ordenar um array de objetos de forma dinâmica. Depois, usaremos o Binary Search para buscar elementos de forma eficiente.

0

Se você já precisou ordenar um array de objetos em JavaScript, provavelmente usou o método .sort(). No entanto, entender e implementar algoritmos clássicos de ordenação, como o QuickSort, pode ser muito útil para aprendizado e otimização.

Neste post, vamos criar uma função QuickSort capaz de ordenar um array de objetos de forma dinâmica, depois, usaremos o Binary Search para buscar elementos de forma eficiente.

O que é QuickSort?

O QuickSort é um algoritmo eficiente de ordenação que segue o paradigma Dividir para Conquistar. Ele funciona assim:

1. Escolhe um elemento como pivô.

2. Divide os elementos em dois grupos:

• Os menores que o pivô (esquerda).

• Os maiores que o pivô (direita).

3. Chama recursivamente o QuickSort para cada grupo.

4. Junta os elementos ordenados.

Agora, vamos aplicá-lo para ordenar objetos em um array!

Criando a Função QuickSort

Nosso objetivo é criar uma função chamada quickSort que recebe:

• Um array de objetos.

• Uma chave (key) para definir a ordenação.

Além disso, como algumas propriedades podem estar aninhadas (exemplo: currency.name), precisamos criar uma função auxiliar para acessar essas chaves dinamicamente.

Passo 1: Criar a função QuickSort

function quickSort(arr, key) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1]; // Escolhe o último elemento como pivô
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (getValue(arr[i], key) < getValue(pivot, key)) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left, key), pivot, ...quickSort(right, key)];
}

Explicando

• Se o array tem 1 ou nenhum elemento, ele já está ordenado.

• Escolhemos o último elemento como pivô.

• Criamos dois arrays:

• left: contém elementos menores que o pivô.

• right: contém elementos maiores que o pivô.

• Chamamos recursivamente o quickSort() para ordenar left e right.

Passo 2: Criar uma função para acessar propriedades aninhadas

Quando passamos currency.name, por exemplo, precisamos buscar essa chave dentro do objeto. Para isso, criamos uma função auxiliar:

function getValue(obj, key) {
  return key.split('.').reduce((o, k) => (o ? o[k] : ''), obj);
}

 Explicando:

• key.split(‘.’): Separa a chave em partes, como [“currency”, “name”].

• reduce(): Percorre as partes e acessa o valor dentro do objeto.

• Se a chave não existir, retorna ” para evitar erros.

Passo 3: Testar a função com um array de países

Agora, aplicamos o QuickSort a um array de países:

const countries = [
  {
    name: "Afghanistan",
    code: "AF",
    capital: "Kabul",
    region: "AS",
    currency: { code: "AFN", name: "Afghan afghani", symbol: "؋" },
    language: { code: "ps", name: "Pashto" },
    flag: "https://restcountries.eu/data/afg.svg",
    dialling_code: "+93",
    isoCode: "004"
  },
  {
    name: "Albania",
    code: "AL",
    capital: "Tirana",
    region: "EU",
    currency: { code: "ALL", name: "Albanian lek", symbol: "L" },
    language: { code: "sq", name: "Albanian" },
    flag: "https://restcountries.eu/data/alb.svg",
    dialling_code: "+355",
    isoCode: "008"
  },
  {
    name: "Algeria",
    code: "DZ",
    capital: "Algiers",
    region: "AF",
    currency: { code: "DZD", name: "Algerian dinar", symbol: "د.ج" },
    language: { code: "ar", name: "Arabic" },
    flag: "https://restcountries.eu/data/dza.svg",
    dialling_code: "+213",
    isoCode: "012"
  }
];

// Ordenando por 'name'
console.log(quickSort(countries, 'name'));

// Ordenando por 'currency.name'
console.log(quickSort(countries, 'currency.name'));

Resultado Esperado

Ordenação por nome (name):

[
  { "name": "Afghanistan", ... },
  { "name": "Albania", ... },
  { "name": "Algeria", ... }
]

Ordenação por moeda (currency.name):

[
  { "currency": { "name": "Afghan afghani" }, ... },
  { "currency": { "name": "Albanian lek" }, ... },
  { "currency": { "name": "Algerian dinar" }, ... }
]

Agora você tem uma função QuickSort totalmente funcional que pode ordenar um array de objetos com base em qualquer propriedade, incluindo aquelas aninhadas!

Aqui está o código completo com a implementação do QuickSort para ordenar um array de objetos dinamicamente em JavaScript:

function quickSort(arr, key) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1]; // Escolhe o último elemento como pivô
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (getValue(arr[i], key) < getValue(pivot, key)) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left, key), pivot, ...quickSort(right, key)];
}

// Função auxiliar para acessar propriedades aninhadas dinamicamente
function getValue(obj, key) {
  return key.split('.').reduce((o, k) => (o ? o[k] : ''), obj);
}

// Array de objetos (exemplo com países)
const countries = [
  {
    name: "Afghanistan",
    code: "AF",
    capital: "Kabul",
    region: "AS",
    currency: { code: "AFN", name: "Afghan afghani", symbol: "؋" },
    language: { code: "ps", name: "Pashto" },
    flag: "https://restcountries.eu/data/afg.svg",
    dialling_code: "+93",
    isoCode: "004"
  },
  {
    name: "Albania",
    code: "AL",
    capital: "Tirana",
    region: "EU",
    currency: { code: "ALL", name: "Albanian lek", symbol: "L" },
    language: { code: "sq", name: "Albanian" },
    flag: "https://restcountries.eu/data/alb.svg",
    dialling_code: "+355",
    isoCode: "008"
  },
  {
    name: "Algeria",
    code: "DZ",
    capital: "Algiers",
    region: "AF",
    currency: { code: "DZD", name: "Algerian dinar", symbol: "د.ج" },
    language: { code: "ar", name: "Arabic" },
    flag: "https://restcountries.eu/data/dza.svg",
    dialling_code: "+213",
    isoCode: "012"
  }
];

// Testando a função com diferentes chaves
console.log("Ordenado por nome:");
console.log(quickSort(countries, 'name'));

console.log("Ordenado por nome da moeda:");
console.log(quickSort(countries, 'currency.name'));

Binary Search: Por que a ordenação é importante?

O Binary Search (Busca Binária) é um algoritmo eficiente para encontrar um elemento em um array ordenado. Ele funciona assim:

Passo a Passo do Binary Search

  1. Escolha o elemento do meio do array.
  2. Compare com o valor procurado:
  • Se for igual, encontramos o elemento. ✅
  • Se for menor, busque na metade direita.
  • Se for maior, busque na metade esquerda.
  1. Repita o processo até encontrar o elemento ou confirmar que ele não está no array.

Se o array não estiver ordenado, o Binary Search não funciona corretamente.

Implementando o Binary Search

function binarySearch(arr, key, value) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid][key] === value) {
      return arr[mid]; // Encontrado 
    } else if (arr[mid][key] < value) {
      left = mid + 1; // Buscar na metade direita
    } else {
      right = mid - 1; // Buscar na metade esquerda
    }
  }

  return null; // Não encontrado 
}

Testando QuickSort + Binary Search

const countries = [
  { name: "Albania", code: "AL" },
  { name: "Afghanistan", code: "AF" },
  { name: "Algeria", code: "DZ" }
];

// Ordena o array antes de buscar
const sortedCountries = quickSort(countries, 'name');

console.log("Ordenado:", sortedCountries);

// Busca um país pelo nome
console.log(binarySearch(sortedCountries, 'name', 'Algeria')); // Encontrado
console.log(binarySearch(sortedCountries, 'name', 'Brazil'));  //  Não encontrado

O Binary Search é muito mais rápido que a busca linear, mas, novamente, só funciona se o array estiver ordenado. O QuickSort nos ajuda a preparar os dados antes da busca.
Juntos, esses algoritmos tornam a pesquisa extremamente eficiente.

Obrigada pela leitura 🙂

Curiosidade

Você sabe como uma pessoa dev front end ordena uma lista?
<div className={“flex flex-col-reverse”}>
<div>01</div>
<div>02</div>
<div>03</div>
</div>

😅

0

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *