Comment implémenter le tri par sélection en C ?

La sélection Sort est un autre algorithme qui fonctionne en localisant le plus petit entier du tableau, puis en l'affectant à la position supérieure. L'index à côté de la position du plus petit entier sera utilisé pour commencer le tableau suivant qui doit être parcouru.

Exemple de tri de sélection en C

Si nous prenons un tableau avec des nombres [10,2,8,4,6] dans lequel le plus petit nombre est 2. Ainsi, nous placerons le plus petit nombre, qui est 2, en première position, après quoi le tableau aura l'air comme [2,10,8,4,6]. Ensuite, nous prendrons le plus petit nombre suivant car 2 est déjà dans sa position correcte maintenant. Le plus petit nombre suivant est 4, qui sera placé en deuxième position, après quoi le tableau sera recherché de la même manière jusqu'à ce qu'il soit finalement trié.

Le tri par sélection en C trie les nombres par ordre croissant. En modifiant l'algorithme, les nombres peuvent être organisés dans un ordre décroissant Le tri par sélection peut également être effectué dans d'autres langages que le C, comme le tri par sélection C++ ou le tri par sélection Python.

Apprenez des cours de développement de logiciels en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.

Algorithme de tri de sélection

• Tout d'abord, nous définissons l'élément initial du tri par sélection comme étant le minimum et recherchons le plus petit élément du tableau pour la procédure correcte de l' algorithme de tri par sélection .
• L'élément minimum est maintenant comparé au second composant. Si le deuxième élément tombe en dessous du minimum, nous les échangerons, puis attribuerons au troisième élément une valeur minimale.
• Sinon, nous continuerons au troisième élément et le comparerons au minimum. Si le deuxième élément dépasse notre premier élément, nous l'échangerons. Répétez ce processus jusqu'au dernier composant.
• Après chaque itération, nous verrons que notre minimum est arrivé au début de la liste non triée.
• Nous commencerons l'indexation à partir de la première entrée de la liste non triée pour chaque itération. Jusqu'à ce que la liste soit triée ou que tous les composants soient correctement positionnés, nous répéterons les étapes 1 à 4 plusieurs fois.

Cours et articles populaires sur le génie logiciel

L'exemple suivant avec chaque itération aidera à comprendre en détail le processus de tri par sélection en C -

Itération #1

Je [ ] = 8,5,2,6,4

Définir un minimum - 8

Comparez i 0 et i 1

Comme, i 0 > i 1 , définissez minimum = 5.

• Comparez i 1 et i 2

Comme, i 1 > i 2 , définissez minimum = 2.

• Comparez i 2 et i 3

Comme, i 2 < i 3 , définissez minimum= 2.

• Comparez i 2 et i 4

Comme, i 2 < i 4 , fixez minimum =2.

2 est le plus petit nombre de tous les éléments, il faut permuter i 0 et i 2

­ Itération #2

Je [ ]= 2,5,8,6,4

Définir au moins 5

• Comparez i 1 et i 2

Comme, i 1 < i 2 , définissez minimum = 5.

• Comparez i 1 et i 3

Comme i 1 < i 3, fixez minimum = 5

• Comparez i 1 et i 4

Encore une fois, i 1 < i 4 , définissez minimum = 4.

4 est le plus petit élément du tableau, nous devons donc échanger i 1 et i 4 .

Itération #3

Je [ ]= 2,4,8,6,5

Définir au moins 8

• Comparez i 2 et i 3

Comme, i 2 > i 3 , définissez minimum = 6.

• Comparez i 3 et i 4

Comme, i 3 > i 4 , définissez minimum = 5.

5 est le plus petit élément du tableau, vous devez échanger i 2 et i 4 .

Itération #4

Je [ ] = 2,4,5,6,8

Définir au moins 6

• Comparez i 3 et i 4

Comme i 3 < i 4 , définissez minimum = 6.

Le minimum est placé au bon endroit; ainsi, aucun échange ne se produira.

Exemple de tri de sélection en C

// Tri des sélections en C

#include <stdio.h>

// fonction pour échanger la position de deux éléments

void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = température ;

}

void selectionSort(int array[], int size) {

for (int step = 0; step < size – 1; step++) {

entier min_idx = étape ;

for (int je = pas + 1; je < taille; je++) {

// Pour trier par ordre décroissant, remplacez > par < dans cette ligne.

// Sélectionne l'élément minimum dans chaque boucle.

si (tableau[i] < tableau[min_idx])

min_idx = je ;

}

// place min à la bonne position

swap(&array[min_idx], &array[step]);

}

}

// fonction pour imprimer un tableau

void printArray(int array[], int size) {

pour (int je = 0; je < taille; ++i) {

printf("%d", tableau[i]);

}

printf("\n");

}

// code du pilote

int main() {

int data[] = {20, 12, 10, 15, 2} ;

int size = sizeof(data) / sizeof(data[0]);

selectionSort(données, taille);

printf("Tableau trié dans l'ordre croissant :\n");

printArray(données, taille);

}

Analyse de complexité du tri de sélection

Entrée – n éléments d'entrée sont donnés.

Sortie – Le nombre d'étapes nécessaires pour trier la liste.

Logique - Si on nous donne n éléments, il fera n-1 comparaisons au premier passage, n-2 comparaisons au deuxième passage, n-3 comparaisons au troisième passage, et ainsi de suite. Par conséquent, le nombre total de comparaisons peut être calculé à l'aide de la ;

Sortir -

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

Somme = n(n-1)/2 c'est-à-dire O(n²)

Étant donné que la méthode de tri par sélection nécessite un espace mémoire supplémentaire pour les variables temporaires à échanger, elle a une complexité temporelle de O(n2) et une complexité spatiale de O(1).

Analyse de la complexité du temps de tri de la sélection

Meilleur cas : pour le tableau qui a déjà été trié, la méthode de tri par sélection a une complexité temporelle optimale de O(n²).

Cas moyen : l'algorithme de tri par sélection a une complexité temporelle de cas moyen de O(n²) lorsque les éléments sont disposés de manière désordonnée, c'est-à-dire ni dans l'ordre croissant ni dans l'ordre décroissant.

Dans le pire des cas : lorsque nous inversons l'ordre décroissant d'un tableau dans son ordre croissant, la complexité temporelle dans le pire des cas est O(n²).

La complexité temporelle de la méthode de tri par sélection est O(n²) dans chacun des trois scénarios. Cela est dû au fait que nous devons identifier le strict minimum pour chaque étape afin de les disposer correctement. Après avoir tracé tout le tableau, nous aurons trouvé notre élément minimal.

Conclusion

Ceci met fin au billet de blog sur "Selection Sort In C". Vous devez comprendre qu'il peut également être exécuté dans d'autres langages, comme Selection Sort C++ et Selection Sort Python. Nous espérons que cet article vous aidera à comprendre comment trier des éléments en C.

Le tri par sélection n'est pas le seul segment du parcours pour devenir programmeur. Si vous espérez donner un coup de pouce significatif à votre carrière de développeur de logiciels avec un diplôme professionnel, upGrad est là ! développement frontend (JavaScript, HTML, CSS), backend (NoSQL-MongoDB) et microservices d'upGrad, vous pouvez alors suivre le cours de maîtrise ès sciences en informatique d'UpGrad. Dispensé par IIIT Bangalore & LJMU Alumni Status, ce cours vous aide à décrocher votre carrière en tant qu'ingénieur logiciel/développeur full-stack auprès des géants de la technologie à travers le monde.

Ce cours couvre les connaissances de base d'outils tels que Java, Spring et Hibernate, renforçant nos compétences en développement complet pour explorer le marché du travail avec des opportunités remarquables.

Inscrivez-vous pour en savoir plus !