Neste tutorial, você aprenderá como funciona a classificação por seleção. Além disso, você encontrará exemplos de trabalho de classificação de seleção em C, C ++, Java e Python.
A classificação por seleção é um algoritmo que seleciona o menor elemento de uma lista não classificada em cada iteração e coloca esse elemento no início da lista não classificada.
Como funciona a classificação por seleção?
- Defina o primeiro elemento como
minimum.
Selecione o primeiro elemento como mínimo - Compare
minimumcom o segundo elemento. Se o segundo elemento for menor queminimum, atribua o segundo elemento comominimum.
Compareminimumcom o terceiro elemento. Novamente, se o terceiro elemento for menor, atribuaminimumao terceiro elemento, caso contrário, não faça nada. O processo continua até o último elemento.
Compare o mínimo com os elementos restantes - Após cada iteração,
minimumé colocado na frente da lista não classificada.
Troque o primeiro pelo mínimo - Para cada iteração, a indexação começa a partir do primeiro elemento não classificado. As etapas 1 a 3 são repetidas até que todos os elementos sejam colocados em suas posições corretas.
A primeira iteração 
A segunda iteração 
A terceira iteração 
A quarta iteração
Algoritmo de classificação de seleção
selectionSort (array, size) repeat (size - 1) times definir o primeiro elemento não classificado como o mínimo para cada um dos elementos não classificados if element <currentMinimum definir elemento como novo mínimo mínimo de troca com primeira posição não classificada end selectionSort
Exemplos de Python, Java e C / C ++
Python Java C C ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
Complexidade
| Ciclo | Número de comparação |
|---|---|
| 1ª | (n-1) |
| 2ª | (n-2) |
| 3ª | (n-3) |
| … | … |
| último | 1 |
Número de comparações: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2quase igual a .n2
Complexidade =O(n2)
Além disso, podemos analisar a complexidade simplesmente observando o número de loops. Existem 2 loops, então a complexidade é .n*n = n2
Complexidades de tempo:
- Complexidade de pior caso: se quisermos classificar em ordem crescente e a matriz estiver em ordem decrescente, então, o pior caso ocorre.
O(n2) - Melhor caso de complexidade: ocorre quando a matriz já está classificada
O(n2) - Complexidade média de caso: ocorre quando os elementos da matriz estão em ordem desordenada (nem crescente nem decrescente).
O(n2)
A complexidade de tempo da classificação de seleção é a mesma em todos os casos. A cada passo, você deve encontrar o elemento mínimo e colocá-lo no lugar certo. O elemento mínimo não é conhecido até que o final da matriz não seja alcançado.
Complexidade do espaço:
A complexidade do espaço ocorre O(1)porque uma variável extra tempé usada.
Aplicativos de classificação de seleção
A classificação de seleção é usada quando:
- uma pequena lista deve ser classificada
- custo de troca não importa
- a verificação de todos os elementos é obrigatória
- custo de gravação em uma memória é importante, como na memória flash (o número de gravações / trocas é
O(n)comparado ao tipo bolha)O(n2)
