1 00:00:00,000 --> 00:00:03,360 >> [Ag seinm ceoil] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD: Ceart go leor, mar sin Is mboilgeog saghas algartaim 4 00:00:06,730 --> 00:00:08,730 Is féidir leat é a úsáid a shórtáil le sraith na n-eilimintí. 5 00:00:08,730 --> 00:00:10,850 A ligean ar ghlacadh le breathnú ar conas a oibríonn sé. 6 00:00:10,850 --> 00:00:13,240 >> Mar sin, an smaoineamh bunúsach taobh thiar de Tá mboilgeog saghas seo. 7 00:00:13,240 --> 00:00:17,340 Ba mhaith linn go ginearálta a bhogadh níos airde gnéithe luacháil go ginearálta leis an gceart, 8 00:00:17,340 --> 00:00:20,340 agus eilimintí luacháil níos ísle go ginearálta ar an taobh clé, mar ba mhaith linn a bheith ag súil. 9 00:00:20,340 --> 00:00:23,256 Ba mhaith linn na rudaí níos ísle a bheith ag an tús, agus na rudaí níos airde 10 00:00:23,256 --> 00:00:24,970 a bheith ag an deireadh. 11 00:00:24,970 --> 00:00:26,130 >> Conas is féidir linn é seo a? 12 00:00:26,130 --> 00:00:28,040 Go maith i cód pseudocode, d'fhéadfadh muid a rá, a ligean ar 13 00:00:28,040 --> 00:00:30,320 shocrú cuntar babhtála a luach neamh-náid. 14 00:00:30,320 --> 00:00:32,570 Beidh muid a fheiceáil cén fáth a dhéanann muid go sa dara. 15 00:00:32,570 --> 00:00:36,090 Agus ansin dúinn arís ar an méid seo a leanas próiseas go dtí go bhfuil an gcuntar babhtála 0, 16 00:00:36,090 --> 00:00:39,910 nó go dtí go ndéanann dúinn aon babhtálacha ar chor ar bith. 17 00:00:39,910 --> 00:00:43,170 >> Athshocraigh an gcuntar babhtála a 0 mura bhfuil sé cheana 0. 18 00:00:43,170 --> 00:00:46,420 Ansin, breathnú ar gach péire aice na n-eilimintí. 19 00:00:46,420 --> 00:00:49,550 Má tá na dhá ghné ní in ord, babhtála iad, 20 00:00:49,550 --> 00:00:51,620 agus cuir 1 leis an gcuntar babhtála. 21 00:00:51,620 --> 00:00:53,870 Má tá tú ag smaoineamh faoi seo sula tú visualize é, 22 00:00:53,870 --> 00:00:57,471 faoi ​​deara go mbeidh an bogadh níos ísle gnéithe luacháil ar an taobh clé 23 00:00:57,471 --> 00:01:00,720 agus níos airde gnéithe do cheart meas, ag déanamh go héifeachtach cad ba mhaith linn a dhéanamh, 24 00:01:00,720 --> 00:01:03,940 a bhfuil bogadh na grúpaí na n-eilimintí sa tslí sin. 25 00:01:03,940 --> 00:01:07,035 A ligean ar a shamhlú conas an D'fhéadfadh cuma baint úsáide as ár sraith 26 00:01:07,035 --> 00:01:10,504 go úsáid againn chun tástáil amach na halgartaim. 27 00:01:10,504 --> 00:01:13,420 Ní mór dúinn le sraith neamhshórtáilte anseo arís, le fios ag gach ceann de na heilimintí 28 00:01:13,420 --> 00:01:14,840 a bheith i dearg. 29 00:01:14,840 --> 00:01:17,970 Agus leag mé mo gcuntar babhtála le luach nonzero. 30 00:01:17,970 --> 00:01:20,610 Roghnaigh mé treallach diúltach 1-- nach bhfuil sé 0. 31 00:01:20,610 --> 00:01:23,840 Is mian linn a dhéanamh arís ar an bpróiseas seo go dtí an gcuntar babhtála Is 0. 32 00:01:23,840 --> 00:01:26,540 Sin é an fáth a leag mé mo babhtála gcuntar le roinnt luach neamh-náid, 33 00:01:26,540 --> 00:01:29,400 mar gheall ar shlí eile ar an Bheadh ​​gcuntar babhtála bheith 0. 34 00:01:29,400 --> 00:01:31,610 Ní bheadh ​​muid ag cur tús fiú an próiseas an algartam. 35 00:01:31,610 --> 00:01:33,610 Mar sin arís, are-- na céimeanna athshocrú an gcuntar babhtála 36 00:01:33,610 --> 00:01:37,900 chun 0, ansin féachaint ar gach aice péire, agus má tá siad as ord, 37 00:01:37,900 --> 00:01:40,514 babhtála iad, agus cuir 1 go dtí an gcuntar babhtála. 38 00:01:40,514 --> 00:01:41,680 Mar sin, a ligean ar tús a chur leis an bpróiseas seo. 39 00:01:41,680 --> 00:01:44,430 Mar sin, is é an chéad rud a dhéanann muid a leag muid an gcuntar babhtála chun 0, 40 00:01:44,430 --> 00:01:46,660 agus ansin tús a chur orainn ag lorg ag gach beirt in aice láimhe. 41 00:01:46,660 --> 00:01:49,140 >> Mar sin, táimid an chéad tús féachaint ar 5 agus 2. 42 00:01:49,140 --> 00:01:52,410 Feicimid go bhfuil siad amach as ordú agus mar sin táimid ag babhtála iad. 43 00:01:52,410 --> 00:01:53,830 Agus muid cuir 1 leis an gcuntar babhtála. 44 00:01:53,830 --> 00:01:57,860 Mar sin, anois tá ár gcuntar babhtála 1, agus 2 agus 5 curtha aistrigh. 45 00:01:57,860 --> 00:01:59,370 Anois táimid ag arís ar an bpróiseas arís. 46 00:01:59,370 --> 00:02:03,540 >> Táimid ag an péire eile in aice láimhe, 5 agus 1-- tá siad chomh maith as ord, 47 00:02:03,540 --> 00:02:06,960 mar sin againn babhtála iad agus cuir 1 a ghabhann leis an gcuntar babhtála. 48 00:02:06,960 --> 00:02:08,900 Ansin táimid ag 5 agus 3. 49 00:02:08,900 --> 00:02:13,830 Tá siad as ord, mar sin táimid ag babhtála iad agus táimid ag cuir 1 leis an gcuntar babhtála. 50 00:02:13,830 --> 00:02:15,550 Ansin táimid ar 5 agus 6. 51 00:02:15,550 --> 00:02:18,630 Tá siad in ord, mar sin ní bhfuil againn i ndáiríre gá aon rud a mhalartú an am seo. 52 00:02:18,630 --> 00:02:20,250 Ansin táimid ag 6 agus 4. 53 00:02:20,250 --> 00:02:24,920 Tá siad freisin as ord, mar sin táimid ag babhtála iad agus táimid ag cuir 1 leis an gcuntar babhtála. 54 00:02:24,920 --> 00:02:26,230 >> Anois faoi deara cad a tharla. 55 00:02:26,230 --> 00:02:29,514 Táimid tar éis ar athraíodh a ionad 6 léir ar an mbealach go dtí deireadh. 56 00:02:29,514 --> 00:02:32,180 Mar sin, i saghas roghnú, má tá tú le feiceáil go bhfuil físeán, cad a rinne muid go raibh 57 00:02:32,180 --> 00:02:35,290 dar críoch muid suas ag gluaiseacht an eilimintí is lú i bhfoirgneamh 58 00:02:35,290 --> 00:02:39,640 an sraith sórtáilte go bunúsach ó chlé go deas, is lú go dtí mó. 59 00:02:39,640 --> 00:02:43,200 I gcás na mboilgeog saghas, má tá muid tar éis an algartam áirithe, 60 00:02:43,200 --> 00:02:46,720 táimid ag dul i ndáiríre a bheith ag tógáil an sraith sórtáilte ó ceart 61 00:02:46,720 --> 00:02:49,100 ar chlé, is mó a is lú. 62 00:02:49,100 --> 00:02:53,840 Táimid tar éis a bubbled héifeachtach 6, an luach is mó, léir ar an mbealach go dtí deireadh. 63 00:02:53,840 --> 00:02:56,165 >> Agus mar sin is féidir linn a dhearbhú anois go bhfuil curtha in eagar, 64 00:02:56,165 --> 00:02:59,130 agus sa todhchaí iterations-- ag dul tríd an eagar again-- 65 00:02:59,130 --> 00:03:01,280 nach bhfuil againn a bhreithniú 6 níos mó. 66 00:03:01,280 --> 00:03:03,850 Ní mór dúinn ach a mheas na heilimintí neamhshórtáilte 67 00:03:03,850 --> 00:03:06,299 nuair a muid ag féachaint ar péirí cóngaracha. 68 00:03:06,299 --> 00:03:08,340 Mar sin, ní mór dúinn críochnaithe amháin pas a fháil trí mboilgeog saghas. 69 00:03:08,340 --> 00:03:11,941 Mar sin, anois táimid ag dul ar ais go dtí an cheist, arís go dtí go bhfuil an gcuntar babhtála 0. 70 00:03:11,941 --> 00:03:13,690 Bhuel an gcuntar babhtála 4, mar sin táimid ag dul 71 00:03:13,690 --> 00:03:15,410 a choinneáil ar athrá ar an bpróiseas arís. 72 00:03:15,410 --> 00:03:19,180 >> Táimid ag dul a athshocrú an gcuntar babhtála chun 0, agus breathnú ar gach péire in aice láimhe. 73 00:03:19,180 --> 00:03:21,890 Mar sin, tús a chur againn le 2 agus tá siad 1-- as ord, mar sin againn babhtála iad 74 00:03:21,890 --> 00:03:23,620 agus cuir muid 1 go dtí an gcuntar babhtála. 75 00:03:23,620 --> 00:03:25,490 2 agus 3, tá siad in ord. 76 00:03:25,490 --> 00:03:27,060 Ní chuirimid gá aon rud a dhéanamh. 77 00:03:27,060 --> 00:03:28,420 3 agus 5 in ord. 78 00:03:28,420 --> 00:03:30,150 Ní chuirimid gá aon rud a dhéanamh ann. 79 00:03:30,150 --> 00:03:32,515 >> 5 agus 4, tá siad amach ar ordú, agus mar sin táimid ag 80 00:03:32,515 --> 00:03:35,130 Ní mór a mhalartú leo agus cuir 1 a ghabhann leis an gcuntar babhtála. 81 00:03:35,130 --> 00:03:38,880 Agus anois tá muid ar athraíodh a ionad 5, an ghné eile is mó, 82 00:03:38,880 --> 00:03:40,920 go dtí deireadh an chuid neamhshórtáilte. 83 00:03:40,920 --> 00:03:44,360 Ionas gur féidir linn glaoch anois go mar chuid den chuid curtha in eagar. 84 00:03:44,360 --> 00:03:47,180 >> Anois tá tú ag lorg ar an scáileán agus is féidir a insint is dócha, 85 00:03:47,180 --> 00:03:50,130 agus is féidir liom, go bhfuil an eagar Tá curtha in eagar ceart anois. 86 00:03:50,130 --> 00:03:51,820 Ach ní féidir linn a chruthú go fóill. 87 00:03:51,820 --> 00:03:54,359 Ní chuirimid bhfuil ráthaíocht go bhfuil sé curtha in eagar. 88 00:03:54,359 --> 00:03:56,900 Ach tá sé seo i gcás an babhtála gcuntar dul le teacht i spraoi. 89 00:03:56,900 --> 00:03:59,060 >> Mar sin, tá muid pas i gcrích. 90 00:03:59,060 --> 00:04:00,357 Is é an gcuntar babhtála 2. 91 00:04:00,357 --> 00:04:02,190 Mar sin, táimid ag dul a dhéanamh arís an próiseas seo arís, 92 00:04:02,190 --> 00:04:04,290 arís go dtí go bhfuil an gcuntar babhtála 0. 93 00:04:04,290 --> 00:04:05,550 Athshocraigh an gcuntar babhtála a 0. 94 00:04:05,550 --> 00:04:06,820 Mar sin, beidh orainn a athshocrú é. 95 00:04:06,820 --> 00:04:09,810 >> Anois féach ar gach péire in aice láimhe. 96 00:04:09,810 --> 00:04:11,880 Sin in ord, 1 agus 2. 97 00:04:11,880 --> 00:04:13,590 2 agus 3 in ord. 98 00:04:13,590 --> 00:04:15,010 3 agus 4 in ord. 99 00:04:15,010 --> 00:04:19,250 Mar sin, ag an bpointe seo, faoi deara atá i gcrích againn ag féachaint ar gach péire in aice láimhe, 100 00:04:19,250 --> 00:04:22,530 ach tá an gcuntar babhtála fós 0. 101 00:04:22,530 --> 00:04:25,520 >> Más rud é nach bhfuil againn a athrú aon ghnéithe, ansin siad 102 00:04:25,520 --> 00:04:28,340 Ní mór a bheith in ord, ag bhua an phróisis. 103 00:04:28,340 --> 00:04:32,000 Agus mar sin ar éifeachtacht de shaghas, Is breá go eolaithe ríomhaire againn, 104 00:04:32,000 --> 00:04:35,560 Tá féidir linn a dhearbhú anois Ní mór an eagar ar fad 105 00:04:35,560 --> 00:04:38,160 a shórtáil, mar nach raibh muid a mhalartú aon eilimintí. 106 00:04:38,160 --> 00:04:40,380 Sin go leor go deas. 107 00:04:40,380 --> 00:04:43,260 >> Mar sin, cad é an cás is measa scéal le mboilgeog saghas? 108 00:04:43,260 --> 00:04:46,240 Sa chás is measa is an eagar in ord droim ar ais go hiomlán, 109 00:04:46,240 --> 00:04:49,870 agus mar sin ní mór dúinn a mboilgeog gach de na heilimintí móra go léir 110 00:04:49,870 --> 00:04:51,780 an mbealach trasna an eagar. 111 00:04:51,780 --> 00:04:55,350 Agus ní mór dúinn go héifeachtach chomh maith le mboilgeog gach ceann de na heilimintí beag ar ais 112 00:04:55,350 --> 00:04:57,050 léir ar an mbealach ar fud an eagar, freisin. 113 00:04:57,050 --> 00:05:01,950 Mar sin, tá gach ceann de na heilimintí n a bhogadh thar gach ceann de na heilimintí n eile. 114 00:05:01,950 --> 00:05:04,102 Mar sin, go bhfuil an cás is measa. 115 00:05:04,102 --> 00:05:05,810 Sa chás is fearr scéal áfach, is é seo 116 00:05:05,810 --> 00:05:07,880 beagán difriúil ó saghas roghnú. 117 00:05:07,880 --> 00:05:10,040 Is é an eagar cheana curtha in eagar nuair a théann muid i. 118 00:05:10,040 --> 00:05:12,550 Nach bhfuil againn a dhéanamh ar aon babhtálacha ar an chéad pas. 119 00:05:12,550 --> 00:05:14,940 Mar sin, d'fhéadfadh muid chun breathnú ag níos lú heilimintí, ceart? 120 00:05:14,940 --> 00:05:18,580 Ní chuirimid a athdhéanamh seo a phróiseáil roinnt huaire níos mó. 121 00:05:18,580 --> 00:05:19,540 >> Mar sin, cad a chiallaíonn? 122 00:05:19,540 --> 00:05:22,390 Mar sin, cad é an cás is measa do mboilgeog a shórtáil, agus cad atá 123 00:05:22,390 --> 00:05:25,330 an scéal chás is fearr le haghaidh mboilgeog saghas? 124 00:05:25,330 --> 00:05:27,770 An raibh tú buille faoi thuairim é seo? 125 00:05:27,770 --> 00:05:32,420 Sa chás is measa a bhfuil tú a iterate trasna na heilimintí n n amanna. 126 00:05:32,420 --> 00:05:34,220 Mar sin, tá an cás is measa cearnaithe n. 127 00:05:34,220 --> 00:05:36,550 >> Má tá an eagar breá sórtáilte áfach, tú ach 128 00:05:36,550 --> 00:05:38,580 chun breathnú ar gach ceann de na heilimintí uair amháin. 129 00:05:38,580 --> 00:05:42,670 Agus má tá an gcuntar babhtála fós 0, Is féidir leat a rá go bhfuil an eagar curtha in eagar. 130 00:05:42,670 --> 00:05:45,780 Agus mar sin sa chás is fearr, is é seo iarbhír níos fearr ná rogha 131 00:05:45,780 --> 00:05:49,230 sort-- tá sé óimige de n. 132 00:05:49,230 --> 00:05:50,270 >> Tá mé Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Is é seo an CS50. 134 00:05:52,140 --> 00:05:54,382