1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [SORT mboilgeog]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Ollscoil Harvard]

3
00:00:04,560 --> 00:00:07,500
É [SEO CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Is é Sórtáil mboilgeog sampla de algartam sórtáil -

5
00:00:11,730 --> 00:00:14,460
is é sin, nós imeachta chun sórtáil sraith na n-eilimintí i

6
00:00:14,460 --> 00:00:15,840
ardaitheach nó ord íslitheach.

7
00:00:15,840 --> 00:00:18,710
Mar shampla, má raibh tú a shórtáil le sraith ina bhfuil an líon

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], bheadh ​​feidhme i gceart Sórtáil mboilgeog ais

9
00:00:23,060 --> 00:00:26,260
eagar curtha in eagar [2, 3, 5, 9] in ord ardaitheach.

10
00:00:26,260 --> 00:00:28,850
Anois, tá mé ag dul a mhíniú i pseudocode conas a oibríonn an algartam.

11
00:00:28,850 --> 00:00:34,000
>> Ligean le rá táimid ag sórtáil liosta de 5 slánuimhreacha - 3, 2, 9, 6, agus 5.

12
00:00:34,000 --> 00:00:37,650
Tosaíonn an algartam trí bhreathnú ar an dá ghné den chéad uair, 3 agus 2,

13
00:00:37,650 --> 00:00:40,850
agus seiceáil má tá siad as ord i gcoibhneas lena chéile.

14
00:00:40,850 --> 00:00:43,150
Tá siad - 3 níos mó ná 2.

15
00:00:43,150 --> 00:00:45,190
Chun a bheith in ord dul suas, ba chóir dóibh a bheith ar an bealach eile timpeall.

16
00:00:45,190 --> 00:00:46,610
Mar sin, babhtála againn orthu.

17
00:00:46,610 --> 00:00:49,760
Anois Breathnaíonn an liosta mar seo: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Next, táimid ag na gnéithe dara agus an tríú, 3 agus 9.

19
00:00:52,450 --> 00:00:55,770
Tá siad san ord ceart i gcoibhneas lena chéile.

20
00:00:55,770 --> 00:00:58,800
Is é sin, tá 3 níos lú ná 9 mar sin nach bhfuil an algartam babhtála leo.

21
00:00:58,800 --> 00:01:01,900
Next, táimid ag 9 agus 6. Tá siad as ord.

22
00:01:01,900 --> 00:01:04,260
>> Mar sin, ní mór dúinn a mhalartú leo toisc go bhfuil 9 níos mó ná 6.

23
00:01:04,260 --> 00:01:08,840
Ar deireadh, táimid ag an dá slánuimhreacha seo caite, 9 agus 5.

24
00:01:08,840 --> 00:01:10,850
Tá siad as ord, mar sin ní mór iad a mhalartú.

25
00:01:10,850 --> 00:01:13,360
Tar éis an pas chéad iomlán tríd an liosta,

26
00:01:13,360 --> 00:01:17,140
Breathnaíonn sé mar seo: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Gan olc. Tá sé curtha in eagar beagnach.

28
00:01:19,690 --> 00:01:22,450
Ach ní mór dúinn a reáchtáil trí mheán an liosta arís a fháil curtha in eagar go hiomlán.

29
00:01:22,450 --> 00:01:29,250
Dhá níos lú ná 3, mar sin ní féidir linn a mhalartú leo.

30
00:01:29,250 --> 00:01:31,700
>> Trí níos lú ná 6, mar sin ní féidir linn a mhalartú leo.

31
00:01:31,700 --> 00:01:35,500
Sé níos mó ná 5. Mhalartaigh againn.

32
00:01:35,500 --> 00:01:38,460
Sé níos lú ná 9. Ní chuirimid mhalartú.

33
00:01:38,460 --> 00:01:42,170
Tar éis an pas dara tríd, tá sé mar seo: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Anois, a ligean ar scríobh sé i pseudocode.

35
00:01:44,680 --> 00:01:48,450
Go bunúsach, do gach eilimint sa liosta, ní mór dúinn chun breathnú ar sé

36
00:01:48,450 --> 00:01:50,060
agus an eilimint go díreach ina cheart.

37
00:01:50,060 --> 00:01:53,420
Má tá siad as ord i gcoibhneas lena chéile - is é sin, más rud é an ghné ar an taobh clé

38
00:01:53,420 --> 00:01:56,810
níos mó ná an ceann ar dheis - ba chóir dúinn a mhalartú ar an dá ghné.

39
00:01:56,810 --> 00:02:01,270
>> Déanaimid é seo le haghaidh gach gné ar an liosta, agus atá déanta againn ar cheann pas a fháil tríd.

40
00:02:01,270 --> 00:02:05,160
Anois, tá muid díreach a dhéanamh ar an am pas-trí leor chun a chinntiú ar an liosta

41
00:02:05,160 --> 00:02:06,480
, tá curtha in eagar go hiomlán i gceart.

42
00:02:06,480 --> 00:02:08,889
Ach cé mhéad uair a bhfuil muid ag dul tríd an liosta

43
00:02:08,889 --> 00:02:10,400
ráthaíocht a thabhairt go bhfuil muid ag déanamh?

44
00:02:10,400 --> 00:02:14,730
Bhuel, tá an cás is measa ar chás má táimid tar éis liosta go hiomlán ar gcúl.

45
00:02:14,730 --> 00:02:17,840
Ansin a thógann sé roinnt pas-throughs comhionann leis an líon

46
00:02:17,840 --> 00:02:19,730
gnéithe n-1.

47
00:02:19,730 --> 00:02:24,720
Más rud é nach bhfuil an ciall intuitively, smaoineamh ar chás simplí - an liosta [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Tá sé seo ag dul a ghlacadh pas amháin-trí a shórtáil i gceart.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Is é an cás is measa go bhfuil 3 ghné curtha in eagar ar gcúl,

50
00:02:33,060 --> 00:02:34,830
tá sé ag dul go dtí 2 atriallta a ghlacadh chun a shórtáil.

51
00:02:34,830 --> 00:02:37,980
Tar éis atriall, tá sé [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
An táirgeacht dara sraith curtha in eagar [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Mar sin, tá a fhios agat go bhfuil tú riamh dul tríd an eagar, go ginearálta,

54
00:02:43,350 --> 00:02:46,790
níos mó ná n-1 uair, áit a bhfuil n líon na n-eilimintí sa eagar.

55
00:02:47,090 --> 00:02:50,470
Sé ar a dtugtar Sórtáil mboilgeog mar gheall ar an claonadh a bhíonn gnéithe is mó a 'mboilgeog-suas'

56
00:02:50,470 --> 00:02:51,950
leis an gceart go tapa go leor.

57
00:02:51,950 --> 00:02:53,980
Go deimhin, tá an algartam iompar an-suimiúil.

58
00:02:53,980 --> 00:02:57,410
>> Tar éis iterations m tríd an eagar ar fad,

59
00:02:57,410 --> 00:02:59,000
na heilimintí m rightmost a ráthú

60
00:02:59,000 --> 00:03:01,000
chun a shórtáil i n-áit ceart.

61
00:03:01,000 --> 00:03:02,280
Más mian leat a fheiceáil seo le haghaidh duit féin,

62
00:03:02,280 --> 00:03:05,500
is féidir linn iarracht é a chur ar liosta go hiomlán ar gcúl [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Tar éis pas a fháil tríd an liosta ar fad,

64
00:03:08,220 --> 00:03:09,220
[Fuaim na scríbhneoireachta]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
Is é an ghné rightmost 9 ina áit chuí.

67
00:03:21,250 --> 00:03:24,760
Tar éis an dara pas-trí, beidh an 6 bhfuil 'bubbled-suas' leis an

68
00:03:24,760 --> 00:03:26,220
áit rightmost an dara.

69
00:03:26,220 --> 00:03:28,840
Tá an dhá ghné ar dheis - 6 agus 9 - beidh a bheith ina n-áiteanna ceart

70
00:03:28,840 --> 00:03:30,580
tar éis an chéad dá pas-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Mar sin, conas is féidir linn seo a úsáid chun Optamaigh an algartam?

72
00:03:32,590 --> 00:03:34,850
Bhuel, tar éis atriall tríd an eagar

73
00:03:34,850 --> 00:03:37,690
ní mór dúinn i ndáiríre a sheiceáil leis an eilimint rightmost

74
00:03:37,690 --> 00:03:39,200
mar tá a fhios againn tá sé curtha in eagar.

75
00:03:39,200 --> 00:03:43,050
Tar éis dhá atriallta, tá a fhios againn do cinnte an dá rightmost heilimintí i bhfeidhm.

76
00:03:43,050 --> 00:03:48,260
Mar sin, go ginearálta, tar éis atriallta k tríd an raon iomlán,

77
00:03:48,260 --> 00:03:51,550
seiceáil na heilimintí k deireanach iomarcach ó tá a fhios againn

78
00:03:51,550 --> 00:03:52,360
tá siad sa suíomh ceart cheana féin.

79
00:03:52,360 --> 00:03:54,870
>> Mar sin, má tá tú ag sórtáil le sraith de ghnéithe n,

80
00:03:54,870 --> 00:03:57,870
ar an leagan den chéad uair - tá you'll a shórtáil gach ceann de na heilimintí - an chéad n-0.

81
00:03:57,870 --> 00:04:04,170
Ar an dara leagan, beidh ort chun breathnú ar gach ceann de na heilimintí rud ach an -

82
00:04:04,170 --> 00:04:07,090
an chéad n-1.

83
00:04:07,090 --> 00:04:10,520
Eile ad'fhéadfadh a bheith leas iomlán a bhaint a sheiceáil má tá an liosta in eagar cheana

84
00:04:10,520 --> 00:04:11,710
tar éis gach leagan.

85
00:04:11,710 --> 00:04:13,900
Má tá sé curtha in eagar cheana féin, ní mór dúinn a dhéanamh atriallta ar bith níos mó

86
00:04:13,900 --> 00:04:15,310
tríd an liosta.

87
00:04:15,310 --> 00:04:16,220
Conas is féidir linn seo a dhéanamh?

88
00:04:16,220 --> 00:04:19,360
Bhuel, más rud é nach bhfuil muid a dhéanamh ar aon bhabhtálacha ar pas-trí an liosta,

89
00:04:19,360 --> 00:04:22,350
tá sé soiléir go bhfuil an liosta a bhí curtha in eagar cheana féin toisc nach raibh muid a mhalartú rud ar bith.

90
00:04:22,350 --> 00:04:24,160
Mar sin, táimid cinnte nach bhfuil a shórtáil arís.

91
00:04:24,160 --> 00:04:27,960
>> B'fhéidir go bhféadfaí tú a thúsú athróg bratach ar a dtugtar 'Ní curtha in eagar' a

92
00:04:27,960 --> 00:04:30,990
falsa agus é a athrú go fíor má tá tú a mhalartú aon ghnéithe ar

93
00:04:30,990 --> 00:04:32,290
amháin atriall tríd an eagar.

94
00:04:32,290 --> 00:04:35,350
Nó dul céanna, a dhéanamh cuntar a chomhaireamh cé mhéad malairtí a dhéanann tú

95
00:04:35,350 --> 00:04:37,040
ar aon leagan ar leith.

96
00:04:37,040 --> 00:04:40,040
Ag deireadh an leagan, más rud é nach raibh tú babhtála aon cheann de na heilimintí,

97
00:04:40,040 --> 00:04:41,780
tá a fhios agat go bhfuil an liosta in eagar cheana féin agus tú ag déanamh.

98
00:04:41,780 --> 00:04:44,090
Sórtáil Bubble, cosúil le halgartaim sórtáil eile ar féidir, a bheith

99
00:04:44,090 --> 00:04:46,960
tweaked a bheith ag obair le haghaidh aon ghnéithe a bhfuil modh a ordú.

100
00:04:46,960 --> 00:04:50,610
>> Is é sin, mar gheall ar dhá ghné ar a bhfuil tú ar bhealach a rá má tá an chéad cheann

101
00:04:50,610 --> 00:04:53,770
níos mó ná, cothrom le nó níos lú ná an dara.

102
00:04:53,770 --> 00:04:56,870
Mar shampla, d'fhéadfaí tú a shórtáil litreacha na haibítre ag rá

103
00:04:56,870 --> 00:05:00,520
go <b, b <c, etc

104
00:05:00,520 --> 00:05:03,830
Nó d'fhéadfaí tú a shórtáil laethanta na seachtaine ina bhfuil dé domhnaigh níos lú ná Dé Luain

105
00:05:03,830 --> 00:05:05,110
atá níos lú ná Dé Máirt.

106
00:05:05,110 --> 00:05:09,630
>> Is é Sórtáil de mboilgeog trí aon mhodh algartam sórtáil an-éifeachtach nó go tapa.

107
00:05:09,630 --> 00:05:12,370
Is í an gcás is measa runtime Big O n ²

108
00:05:12,370 --> 00:05:14,810
toisc go bhfuil tú a dhéanamh atriallta n tríd an liosta

109
00:05:14,810 --> 00:05:18,430
seiceáil na heilimintí go léir n gach pas-trí, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Ciallaíonn an t-am ar siúl go mar an líon de na gnéithe atá tú méaduithe sórtáil,

111
00:05:22,730 --> 00:05:24,330
Méadaíonn sé seo an t-am a reáchtáil quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Ach más rud é nach bhfuil éifeachtacht ábhar mór imní é do chlár

113
00:05:27,330 --> 00:05:29,550
nó má tá tú ag sórtáil ach líon beag na n-eilimintí,

114
00:05:29,550 --> 00:05:31,660
d'fhéadfá a fháil Sórtáil Bubble úsáideach mar gheall ar

115
00:05:31,660 --> 00:05:33,360
Tá sé ar cheann de na halgartaim simplí sórtáil a thuiscint

116
00:05:33,360 --> 00:05:34,250
agus chun cód.

117
00:05:34,250 --> 00:05:37,270
Tá sé freisin ar bhealach iontach taithí a fháil le aistriú a teoiriciúil

118
00:05:37,270 --> 00:05:40,220
algartam i cód feidhmiú iarbhír.

119
00:05:40,220 --> 00:05:43,000
Bhuel, sin é Sórtáil mboilgeog ar do shon. Go raibh maith agat chun breathnú ar.

120
00:05:43,000 --> 00:05:44,000
CS50.TV