TRI DE SÉLECTION - TUTORIEL DS

Dans cet article, nous discuterons de l’algorithme de tri par sélection. La procédure de travail du tri par sélection est également simple. Cet article sera très utile et intéressant pour les étudiants car ils pourraient être confrontés au tri de sélection comme question lors de leurs examens. Il est donc important d’aborder le sujet.

Dans le tri par sélection, la plus petite valeur parmi les éléments non triés du tableau est sélectionnée à chaque passage et insérée à sa position appropriée dans le tableau. C'est aussi l'algorithme le plus simple. Il s'agit d'un algorithme de tri par comparaison sur place. Dans cet algorithme, le tableau est divisé en deux parties, la première est la partie triée et l'autre est la partie non triée. Initialement, la partie triée du tableau est vide et la partie non triée est le tableau donné. La partie triée est placée à gauche, tandis que la partie non triée est placée à droite.

Dans le tri par sélection, le premier plus petit élément est sélectionné dans le tableau non trié et placé en première position. Après cela, le deuxième plus petit élément est sélectionné et placé dans la deuxième position. Le processus se poursuit jusqu'à ce que le tableau soit entièrement trié.

La complexité moyenne et dans le pire des cas du tri par sélection est Sur²) , où n est le nombre d'éléments. Pour cette raison, il ne convient pas aux grands ensembles de données.

Le tri par sélection est généralement utilisé lorsque -

Un petit tableau doit être trié
Le coût d'échange n'a pas d'importance
Il est obligatoire de vérifier tous les éléments

Voyons maintenant l'algorithme de tri par sélection.

Algorithme

 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

Fonctionnement de l'algorithme de tri par sélection

Voyons maintenant le fonctionnement de l'algorithme de tri par sélection.

Pour comprendre le fonctionnement de l'algorithme de tri par sélection, prenons un tableau non trié. Il sera plus facile de comprendre le tri Sélection via un exemple.

Soit les éléments du tableau -

Désormais, pour la première position du tableau trié, l’ensemble du tableau doit être analysé séquentiellement.

Maintenant, 12 est stocké à la première position, après avoir recherché dans tout le tableau, il s'avère que 8 est la plus petite valeur.

industrie et usine

Alors, échangez 12 avec 8. Après la première itération, 8 apparaîtra à la première position dans le tableau trié.

Pour la deuxième position, où 29 est actuellement stocké, nous analysons à nouveau séquentiellement le reste des éléments du tableau non triés. Après analyse, nous constatons que 12 est le deuxième élément le plus bas du tableau qui devrait apparaître en deuxième position.

Maintenant, échangez 29 avec 12. Après la deuxième itération, 12 apparaîtra à la deuxième position dans le tableau trié. Ainsi, après deux itérations, les deux plus petites valeurs sont placées au début de manière triée.

Le même processus est appliqué au reste des éléments du tableau. Nous montrons maintenant une représentation picturale de l’ensemble du processus de tri.

Maintenant, le tableau est complètement trié.

Complexité du tri de sélection

Voyons maintenant la complexité temporelle du tri par sélection dans le meilleur des cas, le cas moyen et le pire des cas. Nous verrons également la complexité spatiale du tri par sélection.

1. Complexité temporelle

Cas	Complexité temporelle
Meilleur cas	Sur²)
Cas moyen	Sur²)
Pire cas	Sur²)

Sur²)

2. Complexité spatiale

Complexité spatiale	O(1)
Écurie	OUI

La complexité spatiale du tri par sélection est O(1). En effet, dans le tri par sélection, une variable supplémentaire est requise pour l'échange.

Implémentation du tri par sélection

Voyons maintenant les programmes de sélection dans différents langages de programmation.

Programme: Écrivez un programme pour implémenter le tri par sélection en langage 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;>

Sortir:

Programme: Écrivez un programme pour implémenter le tri par sélection en 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;>

Sortir:

Après l'exécution du code ci-dessus, la sortie sera -

Donc, c'est tout à propos de l'article. J'espère que l'article vous sera utile et informatif.

Cet article ne se limitait pas à l’algorithme. Nous avons également discuté de la complexité, du fonctionnement et de la mise en œuvre du tri par sélection dans différents langages de programmation.

TechCodeview

Algorithme de tri par sélection