O Algoritmos de Ordenação
Por: makapros • 15/11/2019 • Artigo • 1.501 Palavras (7 Páginas) • 221 Visualizações
INTRODUÇÃO
Os algoritmos de ordenação são utilizados para que possamos retirar dados com mais facilidade e informações mais coerentes, há dois métodos e ordenações, assim cada algoritmo pode ser aproveitado ao máximo, pois cada método e ordenação e mais eficiente do que a outra, dependendo de onde será aplicada.
A linguagem C possui algoritmos que é recomendado para aplicações com baixa taxa de dados (método simples) como por exemplo o Insertion Sort, que possui um código mais simples, já as aplicações para uma alta taxa de dados (métodos eficientes) são utilizados os algoritmos que são mais complexos e sua implementação mais complicada, como por exemplo o Quick Sort.
- ALGORITMOS DE ORDENAÇÃO
Algoritmo de ordenação é um algoritmo que coloca as os elementos em sequência, essa ordenação pode ser completa ou parcial. Os elementos mais usados com numéricos e lexicográfica.
Temos várias razões para ordenar uma sequência, pois com ela ordenada temos acesso aos dados com mais eficiência.
Existem métodos simples e métodos eficientes, o método simples é mais indicado para conjunto pequenos de dados, seus códigos são mais simples e usam menos comparações, já os métodos eficientes possuem códigos mais completos e são adequados para conjunto maiores de dados.
Métodos simples;
Insertion Sort, Selection Sort, Bubble Sort, Comb Sort e Bogo Sort.
Métodos eficientes;
Merge Sort, HeapSort, Shell Sort, Radix Sort, Quick Sort e ect.
1.1 Insertion Sort
Insertion Sort ou ordenação por inserção é um método que percorre um vetor de elementos da esquerda para a direita e com o avanço vai ordenando os elementos à esquerda. É considerar um método de ordenação estável.
Exemplo e implementação;
[pic 1]
Código;
void insercao (int vet, int tam){
int i, j, x;
for (i=2; i<=tam; i++){
x = vet[i];
j=i-1;
vet[0] = x;
while (x < vet[j]){
vet[j+1] = vet[j];
j--;
}
vet[j+1] = x;
}
1.2 Selection Sort
A ordenação por seleção consiste em selecionar o menor item e colocá-lo na primeira posição, selecionar o segundo menor e deixa-lo na segunda posição e assim por diante, até todos os itens estarem ordenados. Selection Sort não é um algoritmo estável.
Exemplo e implementação;
[pic 2]
Código;
void selecao (int vet, int tam){
int i, j, min, x;
for (i=1; i<=n-1; i++){
min = i;
for (j=i+1; j<=n; j++){
if (vet[j] < vet[min])
min = j;
}
x = vet[min];
vet[min] = vet[i];
vet[i] = x;
}
}
1.3 Bubble Sort
Bubble Sort ou ordenação por flutuação (Bolha) é um algoritmo de ordenação simples e percorre o vetor diversas vezes e em cada passagem faz “flutuar” para o topo o maior elemento da sua sequência. Por percorrer diversas vezes os vetores ele não é recomendado para programas que precisam de velocidade ou programas com quantidade elevada de dados.
Exemplo e implementação;
[pic 3]
Código;
void bubble_sort (int vetor[], int n) {
int k, j, aux;
for (k = 1; k < n; k++) {
printf("\n[%d] ", k);
for (j = 0; j < n - k; j++) {
printf("%d, ", j);
if (vetor[j] > vetor[j + 1]) {
aux = vetor[j];
vetor[j] = vetor[j + 1];
vetor[j + 1] = aux;
}
}
}
}
1.4 Quick Sort
O algoritmo Quick Sort é o mais rápido algoritmo de ordenação interna, e o mais utilizado pois é aplicado em diversas variedades de situações.
O Quick Sort faz a comparação dos elementos dividindo o problema, assim ordenando cada conjunto dividido. A divisão ocorre a partir de um pivô, para em seguida realizar o mesmo procedimento nas duas listas.
Como funciona o Algoritmo:
- É escolhido um elemento da lista chamado pivô.
- A lista é reorganizada de forma que os elementos menores que o pivô fiquem de um lado e os maiores do outro (particionamento)
- As sub-listas abaixo e acima do pivô.
Exemplo e implementação;
[pic 4]
Código;
void quick(int vet[], int esq, int dir){
int pivo = esq, i,ch,j;
for(i=esq+1;i<=dir;i++){
j = i;
if(vet[j] < vet[pivo]){
ch = vet[j];
while(j > pivo){
vet[j] = vet[j-1];
j--;
}
vet[j] = ch;
pivo++;
}
}
if(pivo-1 >= esq){
quick(vet,esq,pivo-1);
}
if(pivo+1 <= dir){
quick(vet,pivo+1,dir);
}
}
ESTUDO DE CASO
Para realização prática deste artigo, foram feitos testes, os testes foram os seguintes:
Verificar o comportamento dos algoritmos em relação ao tempo, movimentações de trocas e comparações.
...