DOUG LLOYD: Quindi, in CS50 abbiamo imparato a conoscere una varietà di ordinamento e ricerca algoritmi. E a volte può essere un po 'difficile da mantenere traccia di ciò che l'algoritmo fa che cosa. Abbiamo davvero solo scremato la superficie troppo, ci sono molti altri di ricerca e algoritmi di ordinamento. Quindi, in questo video diamo basta prendere pochi minuti per cercare di distillare ogni algoritmo fino ai suoi elementi fondamentali in modo da poter ricordare la più informazioni importanti su di loro ed essere in grado di articolare la le differenze, se necessario. 

Il primo è selection sort. L'idea di base dietro ordinamento per selezione è trovare il più piccolo elemento indifferenziati in un array e scambiarlo con il primo elemento indifferenziati di tale matrice. Abbiamo detto che il caso peggiore tempo di esecuzione di cui è stato n al quadrato. E se si desidera richiamare perché, prende un guardare il video selection sort. Il tempo di esecuzione nel caso migliore è anche n quadrato. 

Bubble sort, l'idea alla base che uno è quello di scambiare coppie adiacenti. Quindi questa è la chiave che ti aiuta ricordare la differenza qui. Selezione tipo è, fino ad ora, trovare la bolla smallest-- sort è scambiare le coppie adiacenti. Ci scambiamo coppie adiacenti di elementi se sono fuori uso, che di fatto bolle elementi più grandi a destra, e allo stesso tempo inizia anche spostare elementi più piccoli a sinistra. Il tempo di esecuzione caso peggiore di bubble sort è n quadrato. Il tempo di esecuzione nel caso migliore di bubble sort è n. Perché in quella situazione noi non actually-- potremmo non è necessario apportare swap affatto. Dobbiamo solo fare un passare attraverso tutti gli elementi n. 

In insertion sort, il idea di base si sta spostando. Questa è la parola chiave per insertion sort. Stiamo andando a un passo una volta attraverso la matrice da sinistra a destra. E come facciamo noi, che siamo andando a spostare elementi abbiamo già visto per fare spazio a quelli più piccoli che hanno bisogno di adattarsi in qualche luogo indietro in quella porzione filtrate. Così si costruisce il array ordinato uno elemento alla volta, da sinistra a destra, e ci spostiamo le cose per fare spazio. Il tempo di esecuzione nel caso peggiore di insertion sort è n al quadrato. Il momento migliore caso familiare è n. 

Unire sort-- la parola chiave qui è diviso e unire. Abbiamo diviso la gamma completa, se è sei elementi, otto elementi, 10.000 elements-- abbiamo diviso giù della metà, della metà, della metà, fino a quando abbiamo sotto matrice di n un array di elementi. Un insieme di n uno array di elementi. Così abbiamo iniziato con uno Array di 1000 elementi, e arriviamo al punto in cui siamo avere 1.000 matrici di un elemento. Poi si comincia a fondere quelle sub array nuovo insieme nell'ordine corretto. Quindi prendiamo due array un elemento- e creare una matrice a due elementi. Prendiamo due array di due elementi e creare un array di quattro elementi e così via e così via finché non avremo di nuovo ricostruito un array elemento n. 

Il tempo di esecuzione nel caso peggiore di merge sort è n volte il log n. Abbiamo n elementi, ma questo processo ricombinazione prende il log n passi per arrivare indietro di una gamma completa. Il caso migliore tempo di esecuzione è anche log n n perché questo processo non lo fa davvero gli importa se la matrice era ordinati o non iniziare con. Il processo è lo stesso, c'è modo di cose cortocircuito. Quindi n log n nel caso peggiore, n log n nel migliore dei casi. 

Abbiamo parlato di due algoritmi di ricerca. Quindi ricerca lineare è di circa iterazione. Si procede attraverso l'array una volta, da sinistra a destra, cercando di trovare il numero di che stiamo cercando. Il tempo peggiore familiare è grande O di n. Ci potrebbe prendere iterare attraverso ogni singolo elemento per trovare l'elemento che stiamo cercando per, sia in ultima posizione, o per niente. Ma non possiamo confermare che fino a abbiamo esaminato tutto. m il caso migliore, troviamo subito. Il tempo di esecuzione nel caso migliore di ricerca lineare è omega di 1. 

Infine, c'era la ricerca binaria, che richiede schiera assortita. Ricordate che è una molto importante considerazione quando si lavora con ricerca binaria. E 'un prerequisito per utilizzare it-- la matrice che si sta guardando attraverso devono essere ordinati. Altrimenti, la parola chiave è divide et impera. Dividere l'array in mezzo e eliminare la metà degli elementi ogni volta, come si procede attraverso. A causa di questo divide et impera e le cose suddivisione in mezza approccio, il tempo di esecuzione nel caso peggiore di ricerca binaria è log n, che è sostanzialmente meglio di ricerca lineare n. Il momento migliore caso familiare, è ancora uno. 

Potremmo trovare subito il prima volta che facciamo una divisione, ma, ancora una volta, ricordate che sebbene ricerca binaria è sostanzialmente migliore di ricerca lineare in virtù di essere contro log n n, potrebbe essere necessario passare attraverso il lavoro di ordinare l'array prima, che potrebbe rendere meno efficaci a seconda sulla dimensione della iterazione filtrate. 

Sono Doug Lloyd, questo è CS50.