Dans ce didacticiel, vous apprendrez comment fonctionne le tri par sélection. Vous trouverez également des exemples fonctionnels de tri par sélection en C, C ++, Java et Python.
Le tri par sélection est un algorithme qui sélectionne le plus petit élément d'une liste non triée à chaque itération et place cet élément au début de la liste non triée.
Comment fonctionne le tri par sélection?
- Définissez le premier élément comme
minimum.
Sélectionnez le premier élément au minimum - Comparez
minimumavec le deuxième élément. Si le deuxième élément est plus petit queminimum, affectez le deuxième élément commeminimum.
Comparezminimumavec le troisième élément. Encore une fois, si le troisième élément est plus petit, attribuez-minimumlui le troisième élément sinon ne faites rien. Le processus se poursuit jusqu'au dernier élément.
Comparez le minimum avec les éléments restants - Après chaque itération,
minimumest placé au début de la liste non triée.
Échangez le premier avec un minimum - Pour chaque itération, l'indexation commence à partir du premier élément non trié. Les étapes 1 à 3 sont répétées jusqu'à ce que tous les éléments soient placés à leurs positions correctes.
La première itération 
La deuxième itération 
La troisième itération 
La quatrième itération
Algorithme de tri par sélection
selectionSort (array, size) repeat (size - 1) times définir le premier élément non trié comme minimum pour chacun des éléments non triés si élément <currentMinimum set element as new minimum swap minimum with first unsorted position end selectionSort
Exemples Python, Java et 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); )
Complexité
| Cycle | Nombre de comparaison |
|---|---|
| 1er | (n-1) |
| 2e | (n-2) |
| 3e | (n-3) |
| … | … |
| dernier | 1 |
Nombre de comparaisons: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2presque égal à .n2
Complexité =O(n2)
De plus, nous pouvons analyser la complexité en observant simplement le nombre de boucles. Il y a 2 boucles donc la complexité est .n*n = n2
Complexités temporelles:
- Pire complexité des cas: Si nous voulons trier dans l'ordre croissant et que le tableau est dans l'ordre décroissant, le pire des cas se produit.
O(n2) - Meilleure complexité des cas: cela se produit lorsque le tableau est déjà trié
O(n2) - Complexité moyenne des cas: elle se produit lorsque les éléments du tableau sont dans un ordre confus (ni croissant ni décroissant).
O(n2)
La complexité temporelle du tri de sélection est la même dans tous les cas. À chaque étape, il faut trouver l'élément minimum et le mettre au bon endroit. L'élément minimum n'est connu que lorsque la fin du tableau n'est pas atteinte.
Complexité de l'espace:
La complexité de l'espace est O(1)due au fait qu'une variable supplémentaire tempest utilisée.
Applications de tri par sélection
Le tri de sélection est utilisé lorsque:
- une petite liste est à trier
- le coût de l'échange n'a pas d'importance
- la vérification de tous les éléments est obligatoire
- le coût d'écriture dans une mémoire est important comme dans la mémoire flash (le nombre d'écritures / échanges est
O(n)comparé au type de bulle)O(n2)
