Complexité de temps de tri rapide
Maintenant, il existe différentes façons d'écrire les fonctions pivot () et partition (). Le choix du type de fonction pivot () et / ou partition () détermine l'efficacité de l'ensemble du programme. L'efficacité est comme le nombre d'opérations principales qui sont effectuées par le programme.
La complexité du temps est l'exécution relative d'un programme. Cela peut être considéré comme le fonctionnement principal du programme.
Le tri peut ascendant ou descendre. Dans cet article, le tri monte.
Le but de cet article est de produire la complexité du temps pour un programme QuickSort. Étant donné que Quicksort peut être écrit de différentes manières en fonction du choix des fonctions Pivot () et / ou les fonctions de partition (), chaque type de sort rapide a sa propre complexité de temps. Cependant, il existe une gamme d'un certain nombre d'opérations dans lesquelles les différents types de programmes QuickSort correspondent. Cet article ne présente que l'un des différents types de programmes QuickSort. Tout segment de code présenté est de la langue C.
Division entier par deux
Quick Syt utilise la division entière pour diviser son ensemble principal en ensembles plus petits.
Maintenant,
11/2 = 5 reste 1
Division entier signifie, en prenant 5 et en abandonnant 1. C'est-à-dire accepter l'ensemble du nombre et ignorer le reste.
Aussi,
10/2 = 5 reste 0
Ici, le reste est nul et n'a pas d'importance. Pourtant, la division entière prend 5 et abandonne 0. C'est-à-dire accepter le nombre total et ignorer le reste est là, même s'il est nul. Parfois, dans la programmation, il est également bon de savoir si le reste est 0 ou non - voir plus tard.
Lors de la division d'une liste en sort rapide, une division entier est ce qui est utilisé.
Pour un tri rapide, pour obtenir l'index central basé sur zéro pour une liste, faites une division entière de deux pour la durée de la liste. Le nombre entier est l'index intermédiaire basé sur zéro. Pour obtenir la durée de la liste, commencez à compter à partir de 1.
Complexité du temps liée au tri rapide
Considérez le code suivant:
int n = 8;char a [] = 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h';
pour (int i = 0; i
printf ("\ n");
La sortie est:
a b c d e f g hC'est-à-dire que les huit éléments ont été imprimés.
Il y a huit éléments identifiés par n. Le corps de la boucle a un contenu.
printf ("% c", a [i]);C'est une opération principale. Ainsi, huit opérations principales ont eu lieu. La complexité temporelle de ce code est écrite comme:
Sur)
Où n est le nombre d'opérations principales. C'est la notation Big-O. Dans la notation, la première lettre est O en majuscules. Ensuite, il y a des parenthèses. À l'intérieur des parenthèses se trouve le nombre d'opérations ou le nombre maximal possible d'opérations.
Considérez maintenant le segment de code suivant:
pour (int i = 0; i<8; i++)pour (int i = 0; i
si (i == 2)
casser;
printf ("\ n");
La sortie est:
A B CLe corps de la boucle a un contenu.
printf ("% c", a [i]);si (i == 2)
casser;
Ceci est toujours considéré comme une opération principale dans cette situation. Trois éléments ont été imprimés parce que l'opération principale a été exécutée trois fois.
Maintenant,
8 = 23
=> 3 = journal2(8)
Si 8 est n, alors 3 est,
enregistrer2(n)
Et la complexité du temps serait donnée comme suit:
O (journal2n)
Il y a encore un autre segment de code à considérer par rapport à la complexité de temps Quicksort. C'est
pour (int i = 0; iprintf ("\ n");
printf ("\ n");
La sortie est:
a b c d e f g ha b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
Le nombre de caractères imprimés est de 64, à partir d'un nombre initial de 8. Cela signifie que l'opération principale a été exécutée 64 fois.
64 = 8 x 8 = 82
Si 8 est n, alors ce serait n2. La complexité temporelle de ce code est:
Sur2)
Algorithme de tri rapide dans cet article
Pour cet article, les étapes de l'algorithme sont:
- Recherchez la médiane (voir ci-dessous) entre le premier élément, l'élément central et le dernier élément de la liste.
- Positionner la médiane au milieu de la liste.
- Envoyez tous les éléments à droite qui sont inférieurs à la médiane, maintenant au milieu, à gauche de la médiane, et envoyez tous les éléments de gauche qui sont plus grands que la médiane à droite de la médiane. C'est ce qu'on appelle le partitionnement.
- Répétez les trois étapes ci-dessus dans l'ordre, pour chaque sous-liste, jusqu'à ce que la liste soit séparée en éléments uniques.
- Lorsque la liste se compose d'éléments uniques séparés, la liste est triée.
Médian
Pour obtenir la médiane des trois éléments,
TAXIréorganiser les trois éléments dans l'ordre, je.e.
A B CL'élément central, b, est la médiane.
Illustration de tri rapide
La liste à tri est:
P V D Q S X T BIl y a huit éléments. Lorsque la liste a été triée, ce serait:
B d p q s t v xDonc, le problème est: trier la liste:
P V D Q S X T BUtilisation de Quicksort.
La médiane entre P, Q et B est recherchée. C'est p. Cette recherche de la médiane implique trois opérations. Il y a donc un total de trois opérations jusqu'à présent. Mettre la médiane au milieu de la liste donne:
V d q p s x t bN'oubliez pas: l'indice de l'élément central est le résultat de la division entier de deux. Il y a quatre mouvements ici, pour p et q. Ce sont quatre opérations. Cela fait un total de sept opérations jusqu'à présent (trois plus quatre). Maintenant, B sera envoyé à gauche, et V et Q seront envoyés à droite, pour avoir:
D B P V Q S X TNotez que P n'est plus au milieu du milieu. Cependant, il y a eu trois mouvements. Ce sont trois opérations. Il y a donc dix opérations jusqu'à présent (sept plus trois). Chacun des deux sous-listes doit être divisé en trois parties (la médiane est une partie).
La médiane pour D et B est D. La recherche de la médiane est trois opérations. Cela fait jusqu'à présent un total de treize opérations (dix plus trois). Le partitionnement de ces éléments donne:
B dIl y avait deux mouvements ici. Ce sont deux opérations. Cela fait jusqu'à présent un total de quinze opérations (treize plus). Ensuite, la médiane de l'ensemble v, q, s, x, t doit être recherchée, et l'ensemble partitionné.
La médiane pour V, S et T est t. La recherche médiane est de trois opérations. Jusqu'à présent, il y a eu dix-huit opérations (quinze plus trois). Mettre T au milieu donne:
V q t s xIl y a trois mouvements ici. Ce sont trois opérations. Le nombre total d'opérations jusqu'à présent est de vingt et un (dix-huit plus trois). Envoi des éléments inférieurs à droite de T à gauche, et des éléments supérieurs à gauche de T à droite, donne:
Q s t v xIl y a deux mouvements ici. Ce sont deux opérations. Jusqu'à présent, il y a un total de vingt-trois opérations (vingt et un plus deux). Mettre toutes les partitions ensemble jusqu'à présent:
B d p q s t v xNotez que la liste est déjà triée. Cependant, l'algorithme doit se terminer. Q, s et v, x doivent être pris en charge. Il n'y aura pas de mouvement de personnages entre ces deux. Cependant, leur médiane sera examinée. La recherche de deux médianes est six opérations. Cela fait un total de vingt-neuf opérations pour l'ensemble du programme (vingt-trois plus six). La liste triée finale est:
B d p q s t v xNote:
24 = 8 x 3
=> 24 = 8xlog28
29 est approximativement égal à 24.
Conclusion
Selon le type de fonction choisi pour Pivot () et le type de fonction choisie pour partition (), la complexité temporelle du programme QuickSort sera quelque part entre
Sur.enregistrer2n)
et
Sur2)
compris. Notez que le point en o (n.enregistrer2n) signifie multiplication.