ORDENAÇÃO POR SELEÇÃO

Neste artigo, discutiremos o algoritmo de classificação por seleção. O procedimento de trabalho da classificação por seleção também é simples. Este artigo será muito útil e interessante para os alunos, pois eles podem enfrentar a classificação por seleção como uma questão em seus exames. Então, é importante discutir o tema.

Na ordenação por seleção, o menor valor entre os elementos não classificados do array é selecionado em cada passagem e inserido em sua posição apropriada no array. É também o algoritmo mais simples. É um algoritmo de classificação por comparação local. Neste algoritmo, o array é dividido em duas partes, a primeira é a parte classificada e a outra é a parte não classificada. Inicialmente, a parte classificada do array está vazia e a parte não classificada é o array fornecido. A parte classificada é colocada à esquerda, enquanto a parte não classificada é colocada à direita.

Na classificação por seleção, o primeiro menor elemento é selecionado da matriz não classificada e colocado na primeira posição. Depois disso, o segundo menor elemento é selecionado e colocado na segunda posição. O processo continua até que o array esteja totalmente classificado.

A complexidade média e de pior caso da classificação por seleção é Sobre²) , onde n é o número de itens. Devido a isso, não é adequado para grandes conjuntos de dados.

A classificação por seleção geralmente é usada quando -

Uma pequena matriz deve ser classificada
O custo de troca não importa
É obrigatório verificar todos os elementos

Agora, vamos ver o algoritmo de classificação por seleção.

Algoritmo

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL &gt; arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos

Algoritmo de classificação de seleção

Agora, vamos ver o funcionamento do algoritmo de classificação por seleção.

Para entender o funcionamento do algoritmo de classificação por seleção, vamos pegar um array não classificado. Será mais fácil entender a classificação por seleção por meio de um exemplo.

Deixe os elementos do array serem -

Agora, para a primeira posição no array classificado, todo o array deve ser varrido sequencialmente.

Atualmente, 12 é armazenado na primeira posição, após pesquisar todo o array, descobre-se que 8 é o menor valor.

caminho definido em java

Portanto, troque 12 por 8. Após a primeira iteração, 8 aparecerá na primeira posição do array classificado.

Para a segunda posição, onde 29 está armazenado atualmente, verificamos novamente sequencialmente o restante dos itens da matriz não classificada. Após a varredura, descobrimos que 12 é o segundo elemento mais baixo na matriz que deveria aparecer na segunda posição.

Agora, troque 29 por 12. Após a segunda iteração, 12 aparecerá na segunda posição na matriz classificada. Assim, após duas iterações, os dois menores valores são colocados no início de forma ordenada.

O mesmo processo é aplicado ao restante dos elementos do array. Agora, estamos mostrando uma representação pictórica de todo o processo de classificação.

Agora, o array está completamente classificado.

Complexidade de classificação de seleção

Agora, vamos ver a complexidade de tempo da classificação por seleção no melhor caso, no caso médio e no pior caso. Veremos também a complexidade do espaço da classificação por seleção.

1. Complexidade de tempo

Caso	Complexidade de tempo
Melhor caso	Sobre²)
Caso Médio	Sobre²)
Pior caso	Sobre²)

Sobre²)

2. Complexidade Espacial

Complexidade Espacial	O(1)
Estábulo	SIM

A complexidade espacial da classificação por seleção é O (1). Isso ocorre porque, na classificação por seleção, uma variável extra é necessária para a troca.

Implementação de classificação de seleção

Agora, vamos ver os programas de seleção por seleção em diferentes linguagens de programação.

Programa: Escreva um programa para implementar ordenação por seleção em linguagem C.

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

Saída:

Programa: Escreva um programa para implementar a classificação por seleção em Java.

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

Saída:

Após a execução do código acima, a saída será -

Então, isso é tudo sobre o artigo. Espero que o artigo seja útil e informativo para você.

Este artigo não se limitou apenas ao algoritmo. Também discutimos a complexidade, o funcionamento e a implementação da classificação por seleção em diferentes linguagens de programação.

TechCodeview

Algoritmo de classificação por seleção