ORDINAMENTO DELLA SELEZIONE

In questo articolo discuteremo dell'algoritmo di ordinamento della selezione. Anche la procedura di lavoro dell'ordinamento di selezione è semplice. Questo articolo sarà molto utile e interessante per gli studenti poiché potrebbero dover affrontare la selezione come domanda durante gli esami. Quindi è importante discutere l’argomento.

Nell'ordinamento per selezione, il valore più piccolo tra gli elementi non ordinati dell'array viene selezionato in ogni passaggio e inserito nella posizione appropriata nell'array. È anche l'algoritmo più semplice. È un algoritmo di ordinamento per confronto sul posto. In questo algoritmo, l'array è diviso in due parti, la prima è la parte ordinata e l'altra è la parte non ordinata. Inizialmente, la parte ordinata dell'array è vuota e la parte non ordinata è l'array specificato. La parte ordinata viene posizionata a sinistra, mentre la parte non ordinata viene posizionata a destra.

Nell'ordinamento per selezione, il primo elemento più piccolo viene selezionato dall'array non ordinato e posizionato nella prima posizione. Successivamente viene selezionato il secondo elemento più piccolo e posizionato nella seconda posizione. Il processo continua finché l'array non è completamente ordinato.

La complessità media e nel caso peggiore dell'ordinamento di selezione è SU²) , Dove N è il numero di elementi. Per questo motivo non è adatto a set di dati di grandi dimensioni.

L'ordinamento della selezione viene generalmente utilizzato quando:

Un piccolo array deve essere ordinato
Il costo dello scambio non ha importanza
E' obbligatorio controllare tutti gli elementi

Vediamo ora l'algoritmo di ordinamento della selezione.

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

Funzionamento dell'algoritmo di ordinamento di selezione

Ora vediamo il funzionamento dell'algoritmo di ordinamento della selezione.

Per comprendere il funzionamento dell'algoritmo di ordinamento della selezione, prendiamo un array non ordinato. Sarà più semplice comprendere l'ordinamento della selezione tramite un esempio.

Lascia che gli elementi dell'array siano -

Ora, per la prima posizione nell'array ordinato, l'intero array deve essere scansionato in sequenza.

Attualmente, 12 è memorizzato nella prima posizione, dopo aver cercato nell'intero array, si trova che 8 è il valore più piccolo.

qual è il caso in sql

Quindi, scambia 12 con 8. Dopo la prima iterazione, 8 apparirà nella prima posizione nell'array ordinato.

Per la seconda posizione, dove attualmente è memorizzato 29, eseguiamo nuovamente la scansione in sequenza del resto degli elementi dell'array non ordinato. Dopo la scansione, scopriamo che 12 è il secondo elemento più basso nell'array che dovrebbe apparire in seconda posizione.

Ora scambia 29 con 12. Dopo la seconda iterazione, 12 apparirà nella seconda posizione nell'array ordinato. Quindi, dopo due iterazioni, i due valori più piccoli vengono posti all'inizio in modo ordinato.

Lo stesso processo viene applicato al resto degli elementi dell'array. Ora mostriamo una rappresentazione pittorica dell'intero processo di smistamento.

Ora l'array è completamente ordinato.

Complessità dell'ordinamento della selezione

Ora, vediamo la complessità temporale dell'ordinamento della selezione nel caso migliore, nel caso medio e nel caso peggiore. Vedremo anche la complessità spaziale dell'ordinamento della selezione.

1. Complessità temporale

Caso	Complessità temporale
Caso migliore	SU²)
Caso medio	SU²)
Caso peggiore	SU²)

SU²)

2. Complessità spaziale

Complessità spaziale	O(1)
Stabile	SÌ

La complessità spaziale dell'ordinamento di selezione è O(1). Ciò avviene perché, nell'ordinamento per selezione, è necessaria una variabile aggiuntiva per lo scambio.

Implementazione dell'ordinamento di selezione

Vediamo ora i programmi di selezione ordinati nei diversi linguaggi di programmazione.

Programma: Scrivere un programma per implementare l'ordinamento per selezione in linguaggio 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;>

Produzione:

Programma: Scrivere un programma per implementare l'ordinamento per selezione in 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;>

Produzione:

Dopo l'esecuzione del codice sopra, l'output sarà:

Quindi, questo è tutto sull'articolo. Spero che l'articolo ti sia utile e informativo.

Questo articolo non si limitava solo all'algoritmo. Abbiamo anche discusso la complessità, il funzionamento e l'implementazione dell'ordinamento di selezione in diversi linguaggi di programmazione.

TechCodeview

Algoritmo di ordinamento della selezione