Um resumo sobre: vetores não ordenados.
Tags: algorithms, javascript
Published: 2023-02-19 20:24:51

<u>**Linhas gerais sobre inserção, pesquisa e exclusão de dados em um vetor não ordenado.**</u>

Para trabalharmos em um determinado sistema, as operações básicas que utilizamos são: inserção, pesquisa e remoção. Vamos para exemplos práticos: vamos supor que estamos em um treino de futebol, quando entra um jogador é como se entrasse um novo dado nessa estrutura de dados ou vetor, quando sai um jogador, quer dizer que excluímos um dado. 
Podemos ver o time como um array com 11 posições e os jogadores serão **<u>inseridos</u>** de forma aleatória (não ordenada) nesse array, vamos inserindo ocupando a posição 0, 1, 2, 3 e assim por diante. Se pensarmos no Big-O, para inserir um novo jogador nesse array é necessário um passo somente **ArrayTime.push(Jogador)**. Assim, a notação big-o será constante O(1). 
Agora vamos supor que precisássemos **<u>encontrar</u>** um elemento(jogador) nesse Array Time. Em javascript, usamos a função find para percorrer o array e encontrar o jogador. Em notação Big-O será O(n), ou seja, quanto maior o array e quantidade de dados, maior a complexidade, sendo assim, linear. 
Se quisermos **<u>excluir</u>** um jogador, iremos percorrer o array em um número n de passos e tirá-lo da posição, após isso precisamos remanejar as posições para que a posição tirada não fique vazia. Para remanejar, precisamos dar mais uma quantidade n de passos, pois isso irá depender do número que tiramos e qual posição ele estava. Perceba na imagem:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xg7lmxv19npwh11sc8ri.png)

Lembrando que como são vetores não ordenados, os números, logicamente, não estão ordenados nem em ordem crescente, nem decrescente, apenas de forma aleatória.
Na imagem, retiramos o número 1. Com isso, foram necessários 5 passos. 

- Passo 1 - verificar a posição zero.
- Passo 2 - verificar a posição um.
- Passo 3 - verificar a posição dois e tirar o número 1.
- Passo 4- Remanejar o número 8 para a segunda posição.
- Passo 5 - Remanejar o 5 para a terceira posição.

Em Big-O, a notação ficaria assim: O(2n), como N é infinito, ficaria infinito mais infinito que ficaria O(n), ou seja, linear.

**<u>Chaves únicas X Chaves duplicadas:</u>**

No exemplo anterior, não estávamos levando em consideração se as chaves eram duplicadas ou únicas, dei apenas uma visão bem simplificada. Entretanto, neste tópico irei abordar sobre a comparação entre chaves únicas e duplicadas na **_<u>verificação, inserção e exclusão de dados</u>_**. No exemplo dos jogadores, não é permitido jogadores com o mesmo número na camisa, assim, não é permitido valores duplicados. Se a chave fosse pelo nome do jogador, aí seria permitida chaves duplicadas, pois em um time, jogadores podem ter o mesmo nome. Se uma estrutura permitir chaves duplicadas, na **<u>pesquisa</u>**, o programa ao invés de procurar a primeira chave até encontrar e após isso pausar, ele precisará percorrer todo o array. Em JS se as chaves não forem duplicadas, podemos passar o método find no array, mas se as chaves forem duplicadas, passaremos o método filter. Retornando para o exemplo do time de futebol, se as chaves forem o número da camisa, nós utilizamos o find, se forem os nomes, utilizamos o filter, pois terá a possibilidade de haver mais de um jogador com o mesmo nome. Para **<u>inserção</u>** de um jogador, se as chaves forem o nome, é só inserir na última posição e pronto, pois não precisamos preocupar se está repetida ou não. Se forem os números, teremos que percorrer todo o array para verificar se há algum número igual ao que vai entrar para não haver chaves duplicadas, logo após a verificação, é só inserir. Por último, a **<u>exclusão</u>**, caso a chave for única, iremos percorrer o array até encontrar o elemento para excluir e depois reorganizar as posições, aplicar o método find no array e depois o splice. Se a chave for duplicada o processo será: Procura e exclui, rearranja, procura e exclui e rearranja novamente, faz esse processo até chegar ao fim do array, precisaremos utilizar o método filter. 
Em todas as chaves, a notação big-o será linear, ou seja, quanto maior a entrada de dados, maior será o n, embora a quantidade de passos mudará consideravelmente para cada caso, como descrevi. 

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

[Caso tenha dúvidas sobre os métodos find, splice e filter do Javascript.](https://developer.mozilla.org/pt-BR/docs/Web/JavaScript/Reference/Global_Objects/Array)

[Leia sobre o artigo de Big-O para entender melhor o tema:](https://dev.to/costamateus7/um-resumo-sobre-big-o-2hpk)