Complexité de temps de tri de sélection

Le tri de sélection est une sorte d'algorithme de tri. Une liste non triée peut être triée par ordre croissant ou dans l'ordre descendant. Considérez la liste non triée:

55 65 35 15 85 75 25 45

Si cette liste est triée par ordre croissant, ce serait:

15 25 35 45 55 65 75 85

Si la liste est triée par ordre décroissant, ce serait:

85 75 65 55 45 35 25 15

Dans cet article, seul le tri par ordre croissant est considéré. Sélection trie en recherchant de petits éléments et en les échangeant avec les éléments de départ, à partir du plus petit élément, tandis que les éléments de départ remplacés deviennent ascendants. Une liste doit être triée par ordre croissant à la fin de ce processus.

L'article vise à déterminer la complexité temporelle du tri de sélection. La programmation suivante est effectuée dans le langage C.

Algorithme de tri de sélection

Les étapes du tri de sélection sont les suivantes:

• Supposons que le premier élément est le plus petit élément.
• Comparez cet élément avec les autres éléments pour connaître le véritable petit élément.
• Échanger le plus petit élément trouvé avec le premier élément.
• Répétez les trois étapes précédentes dans l'ordre, à l'exclusion du premier élément remplacé.
• Continuez à répéter les trois étapes précédentes, à l'exclusion des éléments vers l'extrémité gauche (inférieure) qui ont été remplacées.
• Le tri se termine lorsque le dernier élément est atteint.

Il existe deux principaux types d'opération ici, qui sont des comparaisons et des échanges. Passer d'un élément à l'autre est également une opération, mais il faut relativement peu de temps par rapport à l'opération de comparaison ou à échanger l'opération dans le tri de sélection.

Sur²) Complexité du temps

Considérez le code suivant:

INT Result = 0;
pour (int i = 0; i<8; i++)
pour (int j = 0; j<8; j++)
Résultat = résultat + 1;


printf ("% i \ n", résultat);

Il y a une boucle extérieure et intérieure. Chaque boucle itère huit fois. La seule opération d'ajout pour les deux boucles est l'opération principale et fonctionne 64 fois. 64 = 8 x 8 = 82. La sortie est 64.

Ce code est considéré comme ayant 82 opérations principales. Si 8 est remplacé par n, alors la complexité temporelle serait donnée comme suit:

O (N2)

Cela utilise la notation Big-O. La notation commence par O en majuscules, suivie de parenthèses. À l'intérieur des parenthèses se trouve le nombre d'opérations principales pour le code.

Considérez le code suivant:

INT Result = 0;
pour (int i = 0; i<8; i++)
pour (int j = i; j<8; j++)
Résultat = résultat + 1;


printf ("% i \ n", résultat);

La boucle extérieure itère huit fois. La boucle intérieure itère jusqu'à la huitième fois mais commence de i, qui est le numéro d'itération de la boucle extérieure. La sortie est 36. La seule opération d'ajout fonctionne 36 fois et non 64 fois. Eh bien, cela est toujours considéré comme une complexité temporelle o (n2). Le fonctionnement du tri de sélection est similaire à ce code. En d'autres termes, le tri de sélection est considéré comme ayant une complexité temporelle O (n2).

Codage en c

Le tri de sélection donnera toujours une complexité temporelle O (n2). Peu importe comment les éléments du tableau sont organisés. C'est parce que tous les éléments sont d'abord numérisés; Ensuite, les autres éléments sans les premiers sont scannés ensuite; La numérisation du reste des éléments sans les deux premiers suit, et ainsi de suite. La numérisation doit être terminée avant d'échanger.

La liste à trier est:

P o i u y t r e w q

Le programme C trie dans l'ordre croissant. Essentiellement, le programme commence par:

#inclure
void SelectIOSORT (char a [], int n)
pour (int i = 0; iint minindx = i;
pour (int j = i + 1; jif (a [j] < A[minIndx])
minindx = j;

char à char = a [i]; A [i] = a [minindx]; A [minindx] = temp; // échange

La bibliothèque responsable de la saisie du clavier et de la sortie au moniteur est incluse. Ensuite, il y a la définition de la fonction de tri de sélection. Cette fonction comme paramètres a le tableau (référence) avec la liste et le nombre d'éléments dans le tableau.

Il y a deux boucles à forte; L'un est imbriqué à l'intérieur de l'autre. La boucle externe itère sur tous les éléments à partir de la première. Alors que la boucle externe est à un index, la boucle intérieure itère sur le reste des éléments, à l'exclusion de l'élément précédent. L'opération principale est l'opération de comparaison dans la boucle imbriquée imbriquée.

L'échange est effectué pour chaque itération de la boucle extérieure juste après la fin de la boucle intérieure.

Une fonction principale C appropriée pour le programme est:

int main (int argc, char ** argv)

int n = 10;
char a [] = 'p', 'o', 'i', 'u', 'y', 't', 'r', 'e', ​​'w', 'q';
selectIOSORT (A, N);
pour (int i = 0; iprintf ("% c", a [i]);
printf ("\ n");
retour 0;

La sortie est:

E i o p q r t u w y

trié.

Il commence par la déclaration du nombre d'éléments dans le tableau. Ensuite, il y a la déclaration du tableau. Il y a dix éléments dans le tableau. Ces éléments sont des caractères. Ainsi, la déclaration de la table commence par «char». Ensuite, la fonction de tri d'insertion est appelée. Le premier argument de l'appel de fonction est le nom du tableau. Le deuxième argument est le nombre d'éléments dans le tableau.

Une boucle pour. Cette boucle for-imprime les caractères triés. Il utilise la fonction printf () du stdio.bibliothèque H. Le premier argument de cette fonction est une chaîne. Cette chaîne est une chaîne spéciale mais a toujours des caractères qui seraient imprimés. Il a également des paramètres pour les arguments. Dans ce cas, il n'y a qu'un seul paramètre,% c. Il n'y a aussi qu'un seul argument, un [i]. Une fois que tous les caractères ont été imprimés sur une seule ligne, la fonction PRINTF () suivante fait passer la sortie à la ligne suivante.

Conclusion

Cet article a discuté des étapes du tri de sélection, qui incluent en supposant que le premier élément est le plus petit élément, en comparant cet élément avec le reste des éléments, et en connaissant le véritable petit élément. De plus, un utilisateur doit échanger le plus petit élément trouvé avec le premier élément et répéter les trois étapes précédentes dans l'ordre, à l'exclusion du premier élément remplacé. Les dernières étapes incluent la continuation de répéter les trois étapes ci-dessus, à l'exclusion des éléments vers l'extrémité gauche (inférieure) qui ont été remplacées; Le tri se termine lorsque le dernier élément est atteint. La complexité du temps pour le tri de sélection est O (N2).