1
00:00:00,000 --> 00:00:02,826
>> [Glazbom]

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

3
00:00:05,660 --> 00:00:09,370
>> Doug LLOYD: Pa umetanje vrsta je još
algoritam možemo koristiti za sortiranje niz.

4
00:00:09,370 --> 00:00:12,350
Ideja iza ovog algoritma
je izgraditi sortirani niz

5
00:00:12,350 --> 00:00:19,670
na mjestu, kreće elemente iz
onako kao što ide, kako bi napravili mjesta.

6
00:00:19,670 --> 00:00:22,240
To je malo drugačiji
od odabira vrste ili mjehura

7
00:00:22,240 --> 00:00:25,460
vrsta, na primjer, gdje
mi smo podešavanjem mjesta,

8
00:00:25,460 --> 00:00:26,910
gdje smo stvaranje swap.

9
00:00:26,910 --> 00:00:29,760
>> U tom slučaju ono što smo zapravo
radite je klizni elementi

10
00:00:29,760 --> 00:00:31,390
više, zabit.

11
00:00:31,390 --> 00:00:34,030
Kako ovo algoritam
rad u pseudokod?

12
00:00:34,030 --> 00:00:37,646
Pa neka je samo reći da je samovoljno
Prvi element niza je riješeno.

13
00:00:37,646 --> 00:00:38,770
Mi smo ga gradi na mjestu.

14
00:00:38,770 --> 00:00:42,660
>> Mi ćemo ići jedan element u isto vrijeme i
graditi ga, pa je prva stvar koju smo vidjeli

15
00:00:42,660 --> 00:00:43,890
je jedan element polje.

16
00:00:43,890 --> 00:00:47,720
A po definiciji, jedan
Element niz sortira.

17
00:00:47,720 --> 00:00:50,850
>> Onda ćemo ponoviti ovaj postupak until--
ćemo ponoviti sljedeći postupak

18
00:00:50,850 --> 00:00:52,900
dok su svi elementi razvrstani.

19
00:00:52,900 --> 00:00:57,770
Pogledajte sljedeću nerazvrstani elementa i
umetnite ga u sortiranog dijela,

20
00:00:57,770 --> 00:01:01,209
pomicanjem potreban broj
elemenata zabit.

21
00:01:01,209 --> 00:01:03,750
Nadam se da ovo vizualizacija
će vam pomoći da vidite točno ono što je

22
00:01:03,750 --> 00:01:05,980
događa s umetanja vrste.

23
00:01:05,980 --> 00:01:08,010
>> Pa opet, ovdje je naš
Cijeli niz Nesortirano,

24
00:01:08,010 --> 00:01:10,970
svi elementi navedeno u crveno.

25
00:01:10,970 --> 00:01:13,320
I neka je slijede
koraci našeg pseudokod.

26
00:01:13,320 --> 00:01:16,970
Prva stvar koju radimo, je zovemo
Prvi element polja, sortirati.

27
00:01:16,970 --> 00:01:20,920
Dakle, mi smo samo ću reći
pet, sad ste razvrstani.

28
00:01:20,920 --> 00:01:24,570
>> Onda mi gledamo na sljedeći
nesortirani element polja

29
00:01:24,570 --> 00:01:27,610
i želimo umetnuti da
u sortirane dijela,

30
00:01:27,610 --> 00:01:29,750
pomicanjem elemenata više.

31
00:01:29,750 --> 00:01:33,470
Dakle, dva je sljedeći nesortiran
element polja.

32
00:01:33,470 --> 00:01:36,250
Jasno mu je i mjesto prije
pet, pa što ćemo učiniti

33
00:01:36,250 --> 00:01:41,580
je vrsta držite dva stranu za trenutak,
pomak pet, a potom umetnite dva

34
00:01:41,580 --> 00:01:43,210
Prije pet, gdje bi trebao ići.

35
00:01:43,210 --> 00:01:45,280
I sada možemo reći da su dva je riješeno.

36
00:01:45,280 --> 00:01:48,400
>> Dakle, kao što možete vidjeti, mi smo samo dosad
pogledao dva elementa niza.

37
00:01:48,400 --> 00:01:50,600
Nismo izgledao
odmor na sve, ali smo

38
00:01:50,600 --> 00:01:54,582
dobio ta dva elementa razvrstani prema
način pomicanja mehanizma.

39
00:01:54,582 --> 00:01:56,410
>> Tako smo opet ponoviti postupak.

40
00:01:56,410 --> 00:01:58,850
Pogledajte sljedeći nesortiran
Element, to je jedan.

41
00:01:58,850 --> 00:02:04,010
Idemo drže da na stranu za trenutak,
pomak sve više, i staviti jedan

42
00:02:04,010 --> 00:02:05,570
gdje bi trebao ići.

43
00:02:05,570 --> 00:02:08,110
>> Opet, i dalje, mi smo jedini ikada
pogledao jedan, dva i pet.

44
00:02:08,110 --> 00:02:12,480
Mi ne znamo što drugo dolazi,
ali smo razvrstani one tri elementa.

45
00:02:12,480 --> 00:02:16,030
>> Sljedeća Nesortirano element
tri, pa ćemo ga staviti na stranu.

46
00:02:16,030 --> 00:02:18,200
Mi ćemo pomak na ono što smo
potrebno je što, ovaj put

47
00:02:18,200 --> 00:02:21,820
nije sve kao u prethodnom
dva slučaja, to je samo pet.

48
00:02:21,820 --> 00:02:25,440
A onda ćemo se držati tri u,
između dva i pet.

49
00:02:25,440 --> 00:02:27,849
>> Šest je sljedeći nesortiran
element polja.

50
00:02:27,849 --> 00:02:31,140
A u stvari šest je veći od pet, pa
mi ni ne morate to učiniti bilo zamjene.

51
00:02:31,140 --> 00:02:35,710
Mi samo možemo sklepati šest pravo na
kraj dijela poredanih.

52
00:02:35,710 --> 00:02:38,270
>> Konačno, četiri je
Posljednji Nesortirano elementa.

53
00:02:38,270 --> 00:02:42,060
Tako ćemo ga staviti na stranu, pomak tijekom
elementi moramo prebaciti preko,

54
00:02:42,060 --> 00:02:43,780
a zatim staviti četiri, gdje mu je i mjesto.

55
00:02:43,780 --> 00:02:46,400
A sada pogledajte, mi smo vrsta
svih elemenata.

56
00:02:46,400 --> 00:02:48,150
Obavijest s umetanjem
vrsta, nismo imali

57
00:02:48,150 --> 00:02:50,240
ići naprijed i natrag preko polja.

58
00:02:50,240 --> 00:02:54,720
Mi išli samo preko polja
jedno vrijeme i pomaknuo se stvari

59
00:02:54,720 --> 00:02:59,870
da bismo već naišli, kako
kako bi napravili mjesta za nove elemente.

60
00:02:59,870 --> 00:03:02,820
>> Dakle, što je najgori slučaj
Scenarij s umetanjem vrste?

61
00:03:02,820 --> 00:03:05,090
U najgorem slučaju,
Niz je u obrnutom redoslijedu.

62
00:03:05,090 --> 00:03:11,180
Morate pomak svaki od n elemenata
do n pozicija, svaki put kad smo

63
00:03:11,180 --> 00:03:12,880
napraviti umetanje.

64
00:03:12,880 --> 00:03:15,720
To je puno pomicanja.

65
00:03:15,720 --> 00:03:18,014
>> U najboljem slučaju,
Niz je savršeno razvrstani.

66
00:03:18,014 --> 00:03:20,680
A nešto poput onoga što se dogodilo
s pet i šest u, primjerice,

67
00:03:20,680 --> 00:03:23,779
gdje smo samo mogli pričvrstiti na
bez potrebe za bilo kakvo pomicanje,

68
00:03:23,779 --> 00:03:24,820
mi u biti ne bih učinio.

69
00:03:24,820 --> 00:03:27,560
>> Ako zamislite da je naš
Niz je jedan do šest,

70
00:03:27,560 --> 00:03:29,900
ćemo krenuti
izjavljujući jedan je riješeno.

71
00:03:29,900 --> 00:03:33,300
Dva dolazi nakon jednog tako možemo jednostavno
kažu, u redu, ali jedan i dva su razvrstani.

72
00:03:33,300 --> 00:03:36,190
Tri dolazi nakon dva tako, u redu,
jedan i dva i tri su razvrstani.

73
00:03:36,190 --> 00:03:39,590
>> Mi ne čineći nikakve zamjene, mi smo
Upravo kreće ovu proizvoljnu crtu

74
00:03:39,590 --> 00:03:42,460
između razvrstani i Nesortirano kako idemo.

75
00:03:42,460 --> 00:03:46,646
Jednako učinkovito kao što smo učinili u primjeru,
okrećući elemente plava, kao što smo nastavili.

76
00:03:46,646 --> 00:03:48,270
Dakle, što je najgori slučaj izvođenja, onda?

77
00:03:48,270 --> 00:03:51,854
Zapamtite, ako imamo pomak svake od
su n elemenata n eventualno pozicije,

78
00:03:51,854 --> 00:03:54,020
nadam se da vam daje
ideja da je najgori slučaj

79
00:03:54,020 --> 00:03:57,770
Runtime je Big O n na kvadrat.

80
00:03:57,770 --> 00:04:00,220
>> Ako je niz savršeno
razvrstani, sve što morate učiniti

81
00:04:00,220 --> 00:04:04,480
je pogledate svakog pojedinog elementa
jednom, a onda smo gotovi.

82
00:04:04,480 --> 00:04:08,440
Dakle, u najboljem slučaju, to je omega n.

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

84
00:04:09,490 --> 00:04:11,760
Ovo je CS50.

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