1
00:00:00,000 --> 00:00:02,826
>> [MUSIC JOC]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Deci sortare prin inserție este un alt
algoritm putem folosi pentru a sorta un array.

4
00:00:09,370 --> 00:00:12,350
Ideea din spatele acestui algoritm
este de a construi matrice dumneavoastră sortat

5
00:00:12,350 --> 00:00:19,670
în loc, schimbarea elemente din
modul cum te duci, pentru a face loc.

6
00:00:19,670 --> 00:00:22,240
Acest lucru este puțin diferit
de la fel de selecție sau bule

7
00:00:22,240 --> 00:00:25,460
fel, de exemplu, în cazul în care
suntem ajustarea locații,

8
00:00:25,460 --> 00:00:26,910
unde facem swap-uri.

9
00:00:26,910 --> 00:00:29,760
>> În acest caz, ceea ce suntem de fapt
a face este elemente glisante

10
00:00:29,760 --> 00:00:31,390
peste, din drum.

11
00:00:31,390 --> 00:00:34,030
Cum functioneaza acest algoritm
lucrează în pseudocod?

12
00:00:34,030 --> 00:00:37,646
Ei bine, lui să spunem arbitrar că
primul element al tabloului este sortat.

13
00:00:37,646 --> 00:00:38,770
Suntem o clădire, în loc.

14
00:00:38,770 --> 00:00:42,660
>> Vom merge un element la un moment dat și
construi, și astfel primul lucru pe care vom vedea

15
00:00:42,660 --> 00:00:43,890
este o gamă un element.

16
00:00:43,890 --> 00:00:47,720
Și prin definiție, un
element de matrice sunt sortate.

17
00:00:47,720 --> 00:00:50,850
>> Apoi vom repeta acest proces until--
vom repeta procesul următor

18
00:00:50,850 --> 00:00:52,900
până când toate elementele sunt sortate.

19
00:00:52,900 --> 00:00:57,770
Uită-te la următorul element nesortate și
introduceți-l în porțiunea sortate,

20
00:00:57,770 --> 00:01:01,209
prin schimbarea numărului necesar
de elemente din drum.

21
00:01:01,209 --> 00:01:03,750
Sperăm că această vizualizare
vă va ajuta să vedeți exact ceea ce-i

22
00:01:03,750 --> 00:01:05,980
întâmplă cu insertie fel.

23
00:01:05,980 --> 00:01:08,010
>> Deci, din nou, aici e noastră
întreaga matrice nesortate,

24
00:01:08,010 --> 00:01:10,970
toate elementele indicate în roșu.

25
00:01:10,970 --> 00:01:13,320
Și să urmați
trepte de pseudocod nostru.

26
00:01:13,320 --> 00:01:16,970
Primul lucru ce facem, este o numim
primul element al tabloului, sortate.

27
00:01:16,970 --> 00:01:20,920
Deci suntem doar să spun
cinci, te sortate acum.

28
00:01:20,920 --> 00:01:24,570
>> Apoi ne uităm la următoarea
Element nesortate de matrice

29
00:01:24,570 --> 00:01:27,610
și vrem să inserați că
în porțiunea sortate,

30
00:01:27,610 --> 00:01:29,750
prin schimbarea elemente peste.

31
00:01:29,750 --> 00:01:33,470
Deci doi este următoarea nesortat
Element de matrice.

32
00:01:33,470 --> 00:01:36,250
În mod evident acesta face parte înainte ca
cinci, astfel încât ceea ce vom face

33
00:01:36,250 --> 00:01:41,580
este un fel de organiza două deoparte pentru un al doilea,
trecerea peste cinci, iar apoi introduceți de două

34
00:01:41,580 --> 00:01:43,210
înainte de cinci, în cazul în care pentru a ar trebui să meargă.

35
00:01:43,210 --> 00:01:45,280
Și acum putem spune că două sunt sortate.

36
00:01:45,280 --> 00:01:48,400
>> Deci, după cum puteți vedea, am numai în măsura
privi două elemente ale tabloului.

37
00:01:48,400 --> 00:01:50,600
Nu am uitat la
odihnă, la toate, dar am

38
00:01:50,600 --> 00:01:54,582
am aceste două elemente clasificate în funcție de
intermediul mecanismului de deplasare.

39
00:01:54,582 --> 00:01:56,410
>> Așa că am repeta procesul.

40
00:01:56,410 --> 00:01:58,850
Uită-te la următoarea nesortat
Element, e unul.

41
00:01:58,850 --> 00:02:04,010
Să susțin că o parte pentru un al doilea,
schimba totul peste, și a pus un

42
00:02:04,010 --> 00:02:05,570
în cazul în care ar trebui să meargă.

43
00:02:05,570 --> 00:02:08,110
>> Din nou, încă, am doar vreodată
sa uitat la una, două, cinci.

44
00:02:08,110 --> 00:02:12,480
Nu știm ce altceva se apropie,
dar am sortat cele trei elemente.

45
00:02:12,480 --> 00:02:16,030
>> Următorul element de nesortate este
trei, asa ca o vom deoparte.

46
00:02:16,030 --> 00:02:18,200
Vom schimba peste ceea ce am
Trebuie să care, de data aceasta

47
00:02:18,200 --> 00:02:21,820
nu este totul la fel ca în precedent
două cazuri, e doar cinci.

48
00:02:21,820 --> 00:02:25,440
Și apoi ne vom lipi trei în,
între cele două și cinci.

49
00:02:25,440 --> 00:02:27,849
>> Șase este următoarea nesortat
Element de matrice.

50
00:02:27,849 --> 00:02:31,140
Și, de fapt șase este mai mare de cinci, așa
nici măcar nu trebuie să faci orice swapping.

51
00:02:31,140 --> 00:02:35,710
Putem tac doar șase dreapta pe la
sfârșitul porțiunii sortate.

52
00:02:35,710 --> 00:02:38,270
>> În cele din urmă, patru este
ultim element nesortate.

53
00:02:38,270 --> 00:02:42,060
Deci vom deoparte, trecerea peste
elementele trebuie să se mute peste,

54
00:02:42,060 --> 00:02:43,780
și a pus apoi patru în cazul în care acesta face parte.

55
00:02:43,780 --> 00:02:46,400
Și acum uite, am un fel
a tuturor elementelor.

56
00:02:46,400 --> 00:02:48,150
Observați cu inserție
sortare, nu am avut

57
00:02:48,150 --> 00:02:50,240
pentru a merge înainte și înapoi pe matrice.

58
00:02:50,240 --> 00:02:54,720
Ne-am dus doar peste matrice
o singură dată, și am mutat lucrurile

59
00:02:54,720 --> 00:02:59,870
că am întâlnit deja, în scopul de
pentru a face loc pentru elementele noi.

60
00:02:59,870 --> 00:03:02,820
>> Deci, ce este cel mai rău caz
scenariu cu inserție fel?

61
00:03:02,820 --> 00:03:05,090
În cel mai rău caz,
matrice este în ordine inversă.

62
00:03:05,090 --> 00:03:11,180
Trebuie să schimbe fiecare dintre n elemente
până la n poziții, fiecare ne-am dată

63
00:03:11,180 --> 00:03:12,880
face o inserție.

64
00:03:12,880 --> 00:03:15,720
Asta-i o mulțime de schimbare.

65
00:03:15,720 --> 00:03:18,014
>> În cel mai bun caz,
matrice este sortata perfect.

66
00:03:18,014 --> 00:03:20,680
Și un fel de ceea ce sa întâmplat
cu cinci și șase în exemplul,

67
00:03:20,680 --> 00:03:23,779
în cazul în care am putea doar tac pe
fără a fi nevoie de a face orice schimbare,

68
00:03:23,779 --> 00:03:24,820
am face în esență, că.

69
00:03:24,820 --> 00:03:27,560
>> Dacă vă imaginați că nostru
matrice a fost unul prin șase,

70
00:03:27,560 --> 00:03:29,900
am începe prin
declararea unul este sortate.

71
00:03:29,900 --> 00:03:33,300
Două vine dupa o astfel încât să putem doar
spune, OK, bine unul și două sunt sortate.

72
00:03:33,300 --> 00:03:36,190
Trei vine după două astfel, OK,
unu și doi și trei sunt sortate.

73
00:03:36,190 --> 00:03:39,590
>> Noi nu facem nici un swap-uri, suntem
doar în mișcare această linie arbitrară

74
00:03:39,590 --> 00:03:42,460
între sortati si nesortate ca mergem.

75
00:03:42,460 --> 00:03:46,646
La fel de eficient cum am făcut în exemplul,
cotitură elemente albastru, așa cum vom proceda.

76
00:03:46,646 --> 00:03:48,270
Deci, ce este cel mai rău caz Runtime, atunci?

77
00:03:48,270 --> 00:03:51,854
Amintiți-vă, dacă trebuie să schimbe fiecare dintre
N elementele eventual n pozitiile,

78
00:03:51,854 --> 00:03:54,020
sperăm că vă oferă
o idee care cel mai rau caz

79
00:03:54,020 --> 00:03:57,770
rulare este O mare de n pătrat.

80
00:03:57,770 --> 00:04:00,220
>> În cazul în care matricea este perfect
sortate, tot ce trebuie să facem

81
00:04:00,220 --> 00:04:04,480
este sa te uiti la fiecare singur element
o dată, și apoi am terminat.

82
00:04:04,480 --> 00:04:08,440
Deci, în cel mai bun caz, este de omega n.

83
00:04:08,440 --> 00:04:09,490
>> Sunt Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Acest lucru este CS50.

85
00:04:11,760 --> 00:04:13,119