Loading repository data…
NetoStAna / repository
Repositório contendo estudos de algoritmos de ordenação desenvolvidos na linguagem C++. Os algoritmos apresentados nesse repositório partem de estudos iniciados no curso de ordenação do Dr. André Backes no canal Programação Descomplicada Linguagem C
A transparent discovery signal based on current public GitHub metadata.
This score does not audit code, security, maintainers, documentation quality, or suitability. Verify the repository and its current documentation before adoption.
Repositório contendo estudos de algoritmos de ordenação desenvolvidos na linguagem C++.
Os algoritmos de ordenação presentes nesse repositório são aplicados sobre um vetor contendo elementos de uma classe denominada Individuo, contendo as variáveis int: id e idade; float: peso e altura; e string: nome.
class Individuo
{
private:
int id, idade;
float peso, altura;
string nome;
Para mais informações sobre a classe e a estrutura dos dados verifique a pasta sobre Lista Sequencial Estática em meu repositório sobre Estruturas de Dados.
Todos os algoritmos ordenam o vetor com objetos do tipo Individuo, através do id de cada um em ordem crescente.
O método utiliza uma variável int: continuar, para verificar a necessidade de continuar a ordenação, uma variável int: fim, inicializada com a quantidade de itens no vetor, um Individuo: auxiliar, para auxiliar nas trocas necessárias pela ordenação, assim como um loop do, while, que segue enquanto o valor da variável continuar for diferente de 0.
void Lista::bubble_sort()
{
int continuar, fim = this->quantidade_max;
Individuo auxiliar;
do
{
A cada etapa do loop a variável continuar recebe o valor 0 e é utilizado um laço for que percorre a quantidade de itens correspondente ao valor da variável fim.
continuar = 0;
for (int i = 0; i < fim - 1; i++)
{
A cada etapa do laço é verificado se o id do Individuo na posição i do vetor é maior que o id do Individuo da posição seguinte. Em caso afirmativo, a variável auxiliar recebe o Individuo da posição i, a posição i recebe o Individuo da posição seguinte, a posição seguinte recebe o da variável e a variável recebe o valor de .
Selected from shared topics, language and repository description—not editorial ratings.
Neto-SantAna /
Repositório contendo estudos de algoritmos de ordenação desenvolvidos na linguagem C++. Os algoritmos apresentados nesse repositório partem de estudos iniciados no curso de ordenação do Dr. André Backes no canal Programação Descomplicada Linguagem C Topics
34/100 healthIndividuoauxiliarcontinuari if (this->lista[i].get_id() > this->lista[i + 1].get_id())
{
auxiliar = this->lista[i];
this->lista[i] = this->lista[i + 1];
this->lista[i + 1] = auxiliar;
continuar = i;
}
Desta forma, ao fim do laço, o Individuo com maior id será posto no final do vetor. Por fim, a variável fim é decrementada em uma unidade para evitar trabalhar com o elemento já ordenado e o loop do, while continua até que todos os elementos estejam ordenados.
}
fim--;
} while (continuar != 0);
}
Melhor Caso: O(n)
Pior Caso: O(n²)
O método utiliza uma variável int: j, para controlar um laço aninhado e a posição de inserção do elemento analisado, e uma variável Individuo: auxiliar, para auxiliar nas trocas necessárias pela ordenação, assim como um laço for que percorre o vetor a partir do segundo elemento até o fim.
void Lista::insertion_sort()
{
int j;
Individuo auxiliar;
for (int i = 1; i < this->quantidade_max; i++)
{
A cada etapa do laço, a variável auxiliar recebe o Individuo da posição i e utiliza-se outro laço for aninhado, iniciando na posição i e percorrendo o vetor até o início ou até que seja encontrado um Individuo com id menor que o id do Individuo armazenado na variável auxiliar.
auxiliar = this->lista[i];
for (j = i; j > 0 && auxiliar.get_id() < this->lista[j - 1].get_id(); j--)
{
A cada etapa do laço aninhado, o elemento da posição j do vetor recebe o elemento anterior. Por fim, a última posição j recebe o Individuo armazenado na variável auxiliar, desta forma, o Individuo que originalmente estava na posição i estará na posição correta em relação aos elementos anteriores.
this->lista[j] = this->lista[j - 1];
}
this->lista[j] = auxiliar;
}
}
Melhor Caso: O(n)
Pior Caso: O(n²)
O método utiliza uma variável int: menor_id, para verificar a posição do Individuo com menor id no vetor, uma variável Individuo: auxiliar, para auxiliar nas trocas necessárias da ordenação, assim como um laço for que percorre o vetor do início até a última posição.
void Lista::selection_sort()
{
int menor_id;
Individuo auxiliar;
for (int i = 0; i < this->quantidade_max - 1; i++)
{
A cada etapa do laço, a variável menor_id recebe o valor de i, em seguida é utilizado outro laço for aninhado que percorre o vetor da posição seguinte de i até o final.
menor_id = i;
for (int j = i + 1; j < this->quantidade_max; j++)
{
A cada etapa do laço aninhado o valor do id do Individuo na posição j é comparado ao valor do id do Individuo na posição menor_id. Caso o primeiro seja menor que o segundo, a variável menor_id recebe o valor de j, desta forma ao fim do laço aninhado a variável menor_id terá a posição do Individuo com o menor id no vetor.
if (this->lista[j].get_id() < this->lista[menor_id].get_id())
{
menor_id = j;
}
Por fim, é verificada a diferença entre o valor da variável i e o valor da variável menor_id, caso estes sejam diferentes, a variável auxiliar recebe o Individuo da posição i do vetor, a posição i do vetor recebe o Individuo da posição menor_id e a posição menor_id recebe o Individuo da variável auxiliar. Caso contrário, o primeiro laço for continua normalmente.
}
if (i != menor_id)
{
auxiliar = this->lista[i];
this->lista[i] = this->lista[menor_id];
this->lista[menor_id] = auxiliar;
}
}
}
Melhor Caso: O(n²)
Pior Caso: O(n²)
O método utiliza a função merge_recursion aplicada sobre a variável lista, iniciando em 0 e finalizando em quantidade_max - 1.
void Lista::merge_sort()
{
this->merge_recursion(this->lista, 0, this->quantidade_max - 1);
}
A função recebe uma variável Individuo *: lista, uma variável int: inicio e uma variável int: fim como parâmetros e utiliza uma variável int: meio, para dividir o vetor.
void Lista::merge_recursion(Individuo *lista, int inicio, int fim)
{
int meio;
Em seguida, são comparados os valores das variável inicio e fim, caso o primeiro seja menor que o segundo, a variável meio recebe o valor da média entre as duas variáveis, a função merge_recursion é usada na primeira e na segunda metade do vetor e a função merge é aplicada sobre as variáveis lista, inicio, meio e fim.
if (inicio < fim)
{
meio = floor((inicio + fim) / 2);
this->merge_recursion(lista, inicio, meio);
this->merge_recursion(lista, meio + 1, fim);
this->merge(lista, inicio, meio, fim);
}
}
A função recebe uma variável Individuo *: lista e as variáveis int: inicio, meio e fim, como parâmetros e utiliza as variáveis int: primeira_metade, inicializada com o valor da variável inicio, int: segunda_metade, inicializada com o valor da variável meio mais 1, int: quantidade, inicializada com o valor da variável fim menos o valor da variável inicio mais 1, bool: fim_primeira_metade e fim_segunda_metade, inicializadas em false e aloca-se um vetor de objetos do tipo Individuo: temporario, com a quantidade definida na variável quantidade, para auxiliar na transferência dos elementos durante a ordenação.
void Lista::merge(Individuo *lista, int inicio, int meio, int fim)
{
int primeira_metade = inicio;
int segunda_metade = meio + 1;
int quantidade = fim - inicio + 1;
bool fim_primeira_metade = false, fim_segunda_metade = false;
Individuo *temporario = new Individuo[quantidade];
Em seguida, verifica-se se o a variável temporario está vazia, caso contrário, inicia-se um laço for que percorre todo o vetor.
if (temporario != NULL)
{
for (int i = 0; i < quantidade; i++)
{
A cada etapa do laço, é verificado se uma das variáveis fim_primeira_metade e fim_segunda_metade se tornaram verdadeiras, em caso negativo, o id do Individuo da posição da primeira_metade é comparado ao id do Individuo da posição da segunda_metade, o menor destes dois é colocado na posição i do vetor e sua variável correspondente é incrementada em uma unidade.
if (!fim_primeira_metade && !fim_segunda_metade)
{
if (lista[primeira_metade].get_id() < lista[segunda_metade].get_id())
{
temporario[i] = lista[primeira_metade++];
}
else
{
temporario[i] = lista[segunda_metade++];
}
Em seguida, verifica-se se a primeira ou a segunda metade chegaram ao fim e atualiza-se a variável correspondente.
if (primeira_metade > meio)
{
fim_primeira_metade = true;
}
if (segunda_metade > fim)
{
fim_segunda_metade = true;
}
Caso uma das duas metades já tenha chegado ao fim, verifica-se qual destas está finalizada e insere-se o restante dos demais elementos no vetor.
}
else
{
if (!fim_primeira_metade)
{
temporario[i] = lista[primeira_metade++];
}
else
{
temporario[i] = lista[segunda_metade++];
}
Por fim, o a variável temporario contará com um vetor ordenado e será transferida para a variável lista recebida como parâmetro, através de um laço for que percorre ambos os vetores. Em seguida, a variável temporario é liberada da memória, finalizando a função.
}
}
for (int j = 0, k = inicio; j < quantidade; j++, k++)
{
lista[k] = temporario[j];
}
}
delete [] temporario;
}
Melhor Caso: O(n * logn)
Pior Caso: O(n * logn)
O método utiliza a função quick_recursion aplicada sobre a variável lista, iniciando em 0 e finalizando em quantidade_max - 1.
void Lista::quick_sort()
{
this->quick_recursion(this->lista, 0, this->quantidade_max - 1);
}
A função recebe uma variável Individuo *: lista, uma variável int: inicio e uma variável int: fim como parâmetros e utiliza uma variável int: pivo, para definir o ponto de início da ordenação.
void Lista::quick_recursion(Individuo *lista, int inicio, int fim)
{
int pivo;
Em seguida, são comparados os valores das variável fim e inicio, caso o primeiro seja maior que o segundo, a variável pivo recebe o valor retornado da função particionar aplicada às variáveis recebidas como parâmetro e a função quick_recursion é aplicada sobre as duas partes do vetor que são divididas pelo valor da variável pivo.
if (fim > inicio)
{
pivo = this->particionar(lista, inicio, fim);
this->quick_recursion(lista, inicio, pivo - 1);
this->quick_recursion(lista, pivo + 1, fim);
}
}
A função recebe uma variável Individuo *: lista, uma variável int: inicio e uma variável int: fim como parâmetros e utiliza as variáveis int: esquerda, inicializada com o valor da variável inicio, int: direita, ini