Como implementar a classificação de seleção em C?

A seleção Sort é outro algoritmo que opera localizando o número inteiro mais baixo da matriz e, em seguida, atribuindo-o à posição superior. O índice ao lado da posição do menor inteiro será usado para iniciar a próxima matriz que deve ser digitalizada.

Exemplo de classificação de seleção em C

Se pegarmos uma matriz com números [10,2,8,4,6] em que o menor número é 2. Assim, colocaremos o menor número, que é 2, na primeira posição, após o que a matriz procurará como [2,10,8,4,6]. Em seguida, pegaremos o próximo menor número porque 2 já está em sua posição correta agora. O próximo menor número é 4, que será colocado na segunda posição, após o que a matriz será pesquisada de maneira semelhante até que seja finalmente classificada.

A classificação por seleção em C classifica os números em ordem crescente. Modificando o algoritmo, os números podem ser organizados em uma classificação descendente. A classificação por seleção também pode ser executada em outras linguagens além de C, como a classificação por seleção C++ ou a classificação por seleção Python.

Aprenda Cursos de Desenvolvimento de Software online nas melhores universidades do mundo. Ganhe Programas Executivos de PG, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.

Algoritmo de classificação de seleção

• Primeiro, definimos o elemento inicial na classificação por seleção como o mínimo e procuramos o menor elemento na matriz para o procedimento correto do Algoritmo de classificação por seleção .
• O elemento mínimo agora é comparado com o segundo componente. Se o segundo elemento cair abaixo do mínimo, vamos trocá-los e, em seguida, atribuir um valor mínimo ao terceiro elemento.
• Caso contrário, continuaremos no terceiro elemento e o compararemos com o mínimo. Se o segundo elemento exceder o nosso primeiro elemento, iremos trocá-lo. Repita esse processo até o último componente.
• Após cada iteração, veremos que nosso mínimo chegou ao início da lista não ordenada.
• Começaremos a indexação a partir da primeira entrada da lista não classificada para cada iteração. Até que a lista seja classificada ou todos os componentes estejam adequadamente posicionados, repetiremos as etapas 1 a 4 várias vezes.

Cursos e artigos populares sobre engenharia de software

O exemplo a seguir com cada iteração ajudará a entender o processo de classificação por seleção em C em detalhes–

Iteração #1

Eu [ ] = 8,5,2,6,4

Definir um mínimo - 8

Compare i 0 e i 1

Como, i 0 > i 1 , defina mínimo = 5.

• Compare i 1 e i 2

Como, i 1 > i 2 , defina mínimo = 2.

• Compare i 2 e i 3

Como, i 2 < i 3 , defina mínimo = 2.

• Compare i 2 e i 4

Como, i 2 < i 4 , defina mínimo =2.

2 é o menor número de todos os elementos, devemos trocar i 0 e i 2

­ Iteração #2

I [ ] = 2,5,8,6,4

Definir mínimo 5

• Compare i 1 e i 2

Como, i 1 < i 2 , defina mínimo = 5.

• Compare i 1 e i 3

Como i 1 < i 3, defina mínimo = 5

• Compare i 1 e i 4

Novamente, i 1 < i 4 , defina mínimo = 4.

4 é o menor elemento da matriz, portanto, devemos trocar i 1 e i 4 .

Iteração #3

I [] = 2,4,8,6,5

Definir mínimo 8

• Compare i 2 e i 3

Como, i 2 > i 3 , defina mínimo = 6.

• Compare i 3 e i 4

Como, i 3 > i 4 , defina mínimo = 5.

5 é o menor elemento da matriz, você deve trocar i 2 e i 4 .

Iteração #4

Eu [ ] = 2,4,5,6,8

Definir mínimo 6

• Compare i 3 e i 4

Como i 3 < i 4 , defina mínimo = 6.

O mínimo é colocado no lugar correto; portanto, nenhuma troca ocorrerá.

Exemplo de ordenação por seleção em C

// Ordenação por seleção em C

#include <stdio.h>

// função para trocar a posição de dois elementos

void swap(int *a, int *b) {

int temperatura = *a;

*a = *b;

*b = temperatura;

}

void selectionSort(int array[], int size) {

for (int passo = 0; passo < tamanho – 1; passo++) {

int min_idx = etapa;

for (int i = passo + 1; i < tamanho; i++) {

// Para classificar em ordem decrescente, altere > para < nesta linha.

// Selecione o elemento mínimo em cada loop.

if (array[i] < array[min_idx])

min_idx = i;

}

// coloca min na posição correta

swap(&array[min_idx], &array[step]);

}

}

//função para imprimir um array

void printArray(int array[], int size) {

for (int i = 0; i < tamanho; ++i) {

printf("%d", matriz[i]);

}

printf(“\n”);

}

// código do motorista

int principal() {

dados int[] = {20, 12, 10, 15, 2};

int tamanho = sizeof(dados) / sizeof(dados[0]);

seleçãoSort(dados, tamanho);

printf(“Matriz ordenada na ordem de envio:\n”);

printArray(dados, tamanho);

}

Análise de Complexidade de Sorte de Seleção

Entrada – n itens de entrada são fornecidos.

Saída – O número de etapas necessárias para classificar a lista.

Lógica – Se recebermos n itens, ele fará n-1 comparações na primeira passagem, n-2 comparações na segunda passagem, n-3 comparações na terceira passagem e assim por diante. Consequentemente, o número total de comparações pode ser calculado usando o;

Saída -

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

Soma = n(n-1)/2 ou seja, O(n²)

Como o método de classificação por seleção precisa de algum espaço de memória adicional para variáveis ​​temporárias para troca, ele tem uma complexidade de tempo de O(n2) e uma complexidade de espaço de O(1).

Análise de complexidade de tempo de classificação de seleção

Melhor caso: para a matriz que foi classificada anteriormente, o método de classificação por seleção tem uma complexidade de tempo de melhor caso de O(n²).

Caso Médio: O algoritmo de ordenação por seleção tem uma complexidade de tempo de caso médio de O(n²) quando os itens são arranjados em confusão, ou seja, nem em ordem crescente nem em ordem decrescente.

Pior caso: quando invertemos a ordem decrescente de um array para sua ordem crescente, a complexidade de tempo do pior caso é O(n²).

A complexidade temporal do método de ordenação por seleção é O(n²) em cada um dos três cenários. Isso se deve ao fato de que devemos identificar os itens mínimos para cada etapa, a fim de organizá-los adequadamente. Depois de rastrear todo o array, teremos encontrado nosso elemento mínimo.

Conclusão

Isso encerra a postagem do blog “Ordenação por seleção em C”. Você deve entender que ele também pode ser executado em outras linguagens, como Selection Sort C++ e Selection Sort Python. Esperamos que este artigo ajude você a entender como classificar elementos em C.

A classificação por seleção não é o único segmento na jornada para se tornar um programador. Se você espera obter um impulso significativo em sua carreira de desenvolvimento de software com um diploma profissional, o upGrad está aqui! upGrad's front-end (JavaScript, HTML, CSS), back-end (NoSQL-MongoDB) e microsserviços, então você pode seguir o curso de Mestrado em Ciência da Computação da UpGrad. Ministrado por IIIT Bangalore e LJMU Alumni Status, este curso ajuda você a conseguir sua carreira como engenheiro de software/desenvolvedor full-stack com os gigantes da tecnologia em todo o mundo.

Este curso abrange o conhecimento básico de ferramentas como Java, Spring e Hibernate, fortalecendo nossas habilidades de desenvolvimento full-stack para explorar o mercado de trabalho com oportunidades notáveis.

Inscreva-se para saber mais!