Você está aqui: C ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca) |
Como usar a ordenação Selection Sort em C - Ordenação por Seleção em CQuantidade de visualizações: 1146 vezes |
|
Nesta dica mostrarei os detalhes da ordenação Selection Sort e como implementá-la em C. Também chamada de Ordenação por Seleção, esta ordenação classifica o array (ou vetor) de forma repetitiva procurando sempre o menor elemento na parte não ordenada do vetor e movendo-o para a parte já ordenada. Mencionei menor elemento para o caso da classificação em ordem crescente. Se for ordem decrescente então deveremos buscar sempre o maior elemento. Considerando o vetor [1, 6, 9, 3, 7, 8, 5, 2] nós teremos as iterações do laço externo e do laço interno, resultando nas seguintes trocas de elementos: Troca 1: 2 trocou de lugar com 6 Resultado: [1, 2, 9, 3, 7, 8, 5, 6] Troca 2: 3 trocou de lugar com 9 Resultado: [1, 2, 3, 9, 7, 8, 5, 6] Troca 3: 5 trocou de lugar com 9 Resultado: [1, 2, 3, 5, 7, 8, 9, 6] Troca 4: 6 trocou de lugar com 7 Resultado: [1, 2, 3, 5, 6, 8, 9, 7] Troca 5: 7 trocou de lugar com 8 Resultado: [1, 2, 3, 5, 6, 7, 9, 8] Troca 6: 8 trocou de lugar com 9 Resultado: [1, 2, 3, 5, 6, 7, 8, 9] Veja agora o código C completo para a ordenação Selection Sort. Coloquei comentários detalhados para facilitar o seu entendimento do algorítmo: ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
// protótipo da função que usa a ordenação Selection Sort para
// ordenar um array de inteiros
void ordenar_selection_sort(int vetor[], int tam);
// função principal do programa
int main(int argc, char *argv[]){
// vamos criar um vetor de inteiros
int valores[] = {1, 6, 9, 3, 7, 8, 5, 2};
int tam = 8;
int i;
setlocale(LC_ALL,""); // para acentos do português
// vamos mostrar o vetor na ordem original
printf("Vetor na ordem original: ");
for(i = 0; i < tam; i++){
printf("%d ", valores[i]);
}
// agora vamos usar a ordenação Selection Sort
// para ordenar o vetor em ordem crescente
ordenar_selection_sort(valores, tam);
// e agora vamos mostrar o vetor ordenado
printf("\nVetor ordenado: ");
for(i = 0; i < tam; i++){
printf("%d ", valores[i]);
}
printf("\n\n");
system("PAUSE");
return 0;
}
// função que usa a ordenação Selection Sort para
// ordenar um array de inteiros
void ordenar_selection_sort(int vetor[], int tam){
// vamos obter o tamanho do vetor
int n = tam;
int i, j, indice_menor_elemento;
// o laço externo percorre os elementos do vetor a partir
// do primeiro elemento e vai até o penúltimo elemento
for (i = 0; i < n - 1; i++){
// encontramos o menor elemento do sub-vetor que ainda
// não foi ordenado
indice_menor_elemento = i;
// o laço interno começa no índice (i + 1) e vai
// até a quantidade de elementos no vetor - 1
for (j = i + 1; j < n; j++){
// o elemento atual (j) é menor que o elemento no
// índice do menor elemento?
if (vetor[j] < vetor[indice_menor_elemento]){
// atualizamos o índice do menor elemento
indice_menor_elemento = j;
}
}
// troca o menor elemento com o elemento no índice
// i, no sub-vetor já ordenado
if(vetor[indice_menor_elemento] != vetor[i]){
int temp = vetor[indice_menor_elemento];
vetor[indice_menor_elemento] = vetor[i];
vetor[i] = temp;
}
}
}
Por apresentar laços aninhados (um laço externo e um interno), a ordenação Selection Sort não é recomendada para grandes conjuntos de dados, visto que sua complexidade de tempo é de O(n2). |
|
|
Desafios, Exercícios e Algoritmos Resolvidos de C |
Veja mais Dicas e truques de C |
Dicas e truques de outras linguagens |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
|
1º lugar: Java |







