DOUG LLOYD: Donc, en CS50 nous avons appris à propos une variété de tri et de recherche algorithmes. Et parfois, il peut être un peu difficile à garder trace de ce que l'algorithme fait quoi. Nous avons vraiment seulement écrémé la surface trop, il ya beaucoup d'autres recherche et des algorithmes de tri. Ainsi, dans cette vidéo nous allons il suffit de prendre quelques minutes pour essayer de distiller chaque algorithme vers le bas à ses éléments essentiels de sorte que vous pouvez vous rappeler le plus des informations importantes sur les et être en mesure d'articuler la différences, si nécessaire. 

La première est la sélection sorte. L'idée de base derrière sélection Trier est de trouver l'élément non triés plus petit dans un tableau et échanger avec le premier élément non triés de ce tableau. Nous avons dit que le pire des cas moment de l'exécution de ce n était carré. Et si vous voulez rappeler pourquoi, prenez un oeil à la vidéo sélection de tri. Le temps d'exécution meilleur des cas est également n carré. 

Bubble sorte, l'idée derrière ce on est d'échanger des paires adjacentes. Voilà donc la clé qui vous aide rappeler la différence ici. Sélection tri est, jusqu'ici, trouver la bulle smallest-- Sort est échanger paires adjacentes. Nous échangeons des paires adjacentes d'éléments si elles sont hors de l'ordre, qui a effectivement bulles grands éléments vers la droite, et en même temps il commence aussi à déplacer les éléments plus petits vers la gauche. Le pire cas de temps d'exécution de tri à bulles est n carré. Le temps d'exécution meilleur des cas de tri à bulles est n. Parce que dans cette situation nous ne actually-- pas nous ne pourrions pas besoin de faire des swaps du tout. Nous avons seulement pour faire un passer à travers tous les éléments de n. 

Dans le tri par insertion, la idée de base est en train de changer. Voilà le mot-clé pour le tri par insertion. Nous allons à l'étape une fois à travers le tableau de gauche à droite. Et comme nous le faisons, nous sommes va changer éléments nous avons déjà vu pour faire place à plus petits qui doivent correspondre quelque part Retour dans la partie triés. Donc, nous construisons le tableau trié un élément à la fois, de gauche à droite, et nous changeons des choses à faire de la place. Le temps d'exécution pire cas de tri par insertion est n carré. Le temps meilleur des cas fonctionner est n. 

Fusionner sort-- le mot-clé ici est fractionner et fusionner. Nous avons partagé la gamme complète, que ce soit il est six éléments, huit éléments, 10.000 elements-- nous divisons diminué de moitié, moitié, moitié, jusqu'à ce que nous avons en vertu de tableau n un tableaux élémentaires. Un ensemble de n un tableaux élémentaires. Donc, nous avons commencé avec un Tableau 1000-élément, et nous arrivons au point où nous avoir 1.000 à un élément tableaux. Puis nous commençons à fusionner ces sous-réseaux retour ensemble dans le bon ordre. Donc, nous prenons deux tableaux à un élément et créer un tableau à deux éléments. Nous prenons deux tableaux à deux éléments et de créer un réseau de quatre éléments et ainsi de suite et ainsi de suite jusqu'à ce que nous avons nouveau reconstruit une matrice n de l'élément. 

Le temps d'exécution pire cas de tri par fusion est N fois log n. Nous avons n éléments, mais ce processus de recomposition prend log n étapes pour obtenir revenir à une gamme complète. Le meilleur des cas d'exécution est également n log n parce que ce processus n'a pas vraiment soucie si le tableau était triés ou non pour commencer. Le processus est le même, il ya aucun moyen de courtes choses circuit. Alors n log n dans le pire des cas, n log n dans le meilleur des cas. 

Nous avons parlé de deux la recherche des algorithmes. Donc, la recherche linéaire est d'environ itération. Nous procédons à travers la matrice une fois, de gauche à droite, en essayant de trouver le nombre que nous recherchons. Le temps le pire des cas courir est grand O de n. Il pourrait nous emmener itération à travers chaque élément pour trouver l'élément que nous sommes à la recherche pour, soit en dernière position, ou pas du tout. Mais nous ne pouvons pas confirmer que, jusqu'à nous avons examiné tout. m le meilleur des cas, nous trouvons immédiatement. Le temps d'exécution le meilleur des cas de recherche linéaire est l'oméga de 1. 

Enfin, il y avait une recherche binaire, qui exige gamme assortis. Rappelez-vous que est une très considération importante lorsque vous travaillez avec la recherche binaire. Il est une condition préalable à l'utilisation de it-- le tableau que vous êtes à la recherche par le biais doit être trié. Dans le cas contraire, le mot-clé est diviser pour régner. Diviser le tableau en deux et éliminer la moitié des éléments chaque fois que vous passez à travers. En raison de cette diviser pour mieux régner et les choses de fractionnement en demi approche, le temps d'exécution pire cas de recherche binaire est log n, qui est sensiblement mieux que la n de la recherche linéaire. Le temps meilleur des cas fonctionner est encore un. 

Nous pourrions trouver immédiatement le première fois que nous faisons une division, mais, encore une fois, rappelez-vous que Bien que la recherche binaire est nettement mieux que la recherche linéaire en vertu d'être log n par rapport à n, vous pourriez avoir à passer par le travail de tri votre premier tableau, qui pourrait rendre moins efficace en fonction de la taille de l'itération triés. 

Je suis Doug Lloyd, cela est CS50.