1 00:00:00,000 --> 00:00:07,270 2 00:00:07,270 --> 00:00:10,390 >> MARK GROZEN-SMITH: Dia duit, Tá mé Mark Grozen-Smith, agus tá sé seo Quicksort. 3 00:00:10,390 --> 00:00:13,520 Díreach cosúil le saghas a chur isteach agus mboilgeog saghas, tá Quicksort algartaim do 4 00:00:13,520 --> 00:00:15,720 sórtáil liosta nó sraith de rudaí. 5 00:00:15,720 --> 00:00:19,080 Chun simplíocht, a ligean ar glacadh leis go bhfuil sin Tá rudaí ach slánuimhreacha, ach 6 00:00:19,080 --> 00:00:22,060 Tá a fhios go n-oibríonn Quicksort do níos mó ná díreach uimhreacha. 7 00:00:22,060 --> 00:00:24,720 Is Mearthosú le beagán níos casta ná a chur isteach nó mboilgeog, ach tá sé 8 00:00:24,720 --> 00:00:27,560 freisin i bhfad níos éifeachtaí i bhformhór na gcásanna. 9 00:00:27,560 --> 00:00:28,150 Fan dara. 10 00:00:28,150 --> 00:00:30,760 An ndúirt sé ach "an chuid is mó cásanna, "ní" gach "? 11 00:00:30,760 --> 00:00:31,710 Suimiúil go leor, uimh. 12 00:00:31,710 --> 00:00:33,560 Tá Níl gach cás mar an gcéanna. 13 00:00:33,560 --> 00:00:36,650 Ná bíodh imní ort faoi seo go mion má tá tú nach bhfuil le feiceáil nodaireacht O mór go fóill, ach 14 00:00:36,650 --> 00:00:39,730 Is Quicksort O (n cearnógach) algartam ag measa, díreach cosúil 15 00:00:39,730 --> 00:00:41,430 a chur isteach nó mboilgeog saghas. 16 00:00:41,430 --> 00:00:44,950 Mar sin féin, gníomhaíonn sé de ghnáth i bhfad níos mó cosúil le aschur sean m algartam. 17 00:00:44,950 --> 00:00:45,750 Cén fáth? 18 00:00:45,750 --> 00:00:46,810 Beidh muid a fháil ar ais go dtí sin ina dhiaidh sin. 19 00:00:46,810 --> 00:00:49,610 Ach do anois, a ligean ar fhoghlaim ach conas a oibríonn Quicksort. 20 00:00:49,610 --> 00:00:53,080 >> Mar sin, a ligean ar siúl tríd Quicksorting seo sraith de slánuimhreacha ón gceann is lú 21 00:00:53,080 --> 00:00:54,260 a is mó. 22 00:00:54,260 --> 00:01:00,110 Anseo ní mór dúinn an slánuimhreacha 6, 5, 1, 3, 8, 4, 7, 9, agus 2. 23 00:01:00,110 --> 00:01:03,480 Gcéad dul síos, roghnaigh muid an eilimint deiridh de seo sraith - sa chás seo, dhá - 24 00:01:03,480 --> 00:01:06,870 agus glaoch go bhfuil an "pivot." Next, ní mór dúinn tús a chur chun breathnú ar dhá rud - 25 00:01:06,870 --> 00:01:10,220 ceann amháin, an t-innéacs is ísle, a beidh mé tagairt mar atá ag fanacht leis an gceart 26 00:01:10,220 --> 00:01:13,970 an balla, agus, dhá cheann, an leftmost eilimint, a beidh mé glaoch ar an "reatha 27 00:01:13,970 --> 00:01:17,260 eilimint. "Cad tá muid ag dul a dhéanamh ná breathnú ar fad na gnéithe eile, eile 28 00:01:17,260 --> 00:01:20,930 ná an mhaighdeog, agus go léir a chur ar na gnéithe níos lú ná an mhaighdeog ar an 29 00:01:20,930 --> 00:01:24,140 d'fhág an bhalla agus dóibh siúd go léir níos mó ná an mhaighdeog ar an 30 00:01:24,140 --> 00:01:25,570 ceart an bhalla. 31 00:01:25,570 --> 00:01:29,560 Ansin, ar deireadh, beidh muid ag titim ar an mhaighdeog ar dheis ar an mballa chun é a chur idir 32 00:01:29,560 --> 00:01:32,970 na huimhreacha níos lú ná sé agus na uimhreacha níos mó. 33 00:01:32,970 --> 00:01:34,460 >> Mar sin, a ligean ar é sin a dhéanamh. 34 00:01:34,460 --> 00:01:38,540 Pioc suas an 2, a chur ar an bhalla ag an ag tosú, agus glaoch ar an 6 "reatha 35 00:01:38,540 --> 00:01:41,590 eilimint. "Mar sin, ba mhaith linn chun breathnú ar ár n-eilimint ann faoi láthair, an 6. 36 00:01:41,590 --> 00:01:44,200 Agus ós rud é tá sé níos mó ná an 2, a fhágann muid é ansin go dtí an 37 00:01:44,200 --> 00:01:45,610 ceart an bhalla. 38 00:01:45,610 --> 00:01:48,980 Ansin, táimid ag bogadh ar aghaidh chun breathnú ar an 5 mar ár eilimint reatha agus a fheiceáil go bhfuil an 39 00:01:48,980 --> 00:01:51,840 is é, arís, níos mó ná an mhaighdeog, mar sin againn fág é ina bhfuil sé ar dheis 40 00:01:51,840 --> 00:01:53,190 taobh den bhalla. 41 00:01:53,190 --> 00:01:53,880 Táimid bogadh ar aghaidh. 42 00:01:53,880 --> 00:01:56,750 Is é ár gné reatha anois 1, agus - OH. 43 00:01:56,750 --> 00:01:58,030 Tá sé seo difriúil anois. 44 00:01:58,030 --> 00:02:00,890 Is é an ghné reatha anois níos lú ná an mhaighdeog, mar sin ba mhaith linn a chur air 45 00:02:00,890 --> 00:02:02,570 ar an taobh clé den bhalla. 46 00:02:02,570 --> 00:02:06,555 Chun seo a dhéanamh, a ligean ar aistriú ach an eilimint ann faoi láthair leis an innéacs is ísle 47 00:02:06,555 --> 00:02:07,970 ach suí do cheart an bhalla. 48 00:02:07,970 --> 00:02:14,050 49 00:02:14,050 --> 00:02:17,570 Anois, sinn ag dul ar an bhalla suas innéacs amháin mar sin tá an 1 ar chlé 50 00:02:17,570 --> 00:02:19,750 taobh den bhalla anois. 51 00:02:19,750 --> 00:02:20,310 >> Fan. 52 00:02:20,310 --> 00:02:23,450 Measctha mé díreach suas na heilimintí ar an taobh na láimhe deise den bhalla, ní raibh mé? 53 00:02:23,450 --> 00:02:23,890 Ná bíodh imní ort. 54 00:02:23,890 --> 00:02:24,930 Sin breá. 55 00:02:24,930 --> 00:02:27,570 An rud amháin a cúram againn faoi do anois is é sin na heilimintí go léir ar an 56 00:02:27,570 --> 00:02:29,570 ceart an bhalla go bhfuil níos mó ná an mhaighdeog. 57 00:02:29,570 --> 00:02:31,760 Níl aon ordú iarbhír Glactar leis go fóill. 58 00:02:31,760 --> 00:02:33,200 >> Anois, ar ais go dtí a shórtáil. 59 00:02:33,200 --> 00:02:35,840 Mar sin, leanaimid ar aghaidh ar ag féachaint ar an chuid eile de na heilimintí. 60 00:02:35,840 --> 00:02:39,075 Agus sa chás seo, feicimid go bhfuil aon eilimintí eile lú ná an 61 00:02:39,075 --> 00:02:42,100 mhaighdeog, mar sin a fhágáil dúinn iad go léir ar an taobh na láimhe deise den bhalla. 62 00:02:42,100 --> 00:02:45,980 Mar fhocal scoir, a fháil againn chun an eilimint atá ann faoi láthair agus a fheiceáil go bhfuil sé an mhaighdeog. 63 00:02:45,980 --> 00:02:48,830 Anois, Ciallaíonn sé sin go bhfuil muid beirt codanna de na eagar, an chéad á 64 00:02:48,830 --> 00:02:51,820 beag ar an mhaighdeog agus ar an taobh clé an bhalla, agus an dara á 65 00:02:51,820 --> 00:02:54,500 níos mó ná an mhaighdeog ar an taobh na láimhe deise den bhalla. 66 00:02:54,500 --> 00:02:57,040 Ba mhaith linn a chur ar an eilimint mhaighdeog idir an dá, agus ansin beidh a fhios againn 67 00:02:57,040 --> 00:03:01,000 go bhfuil an pivot ina cheart áit deiridh curtha in eagar. 68 00:03:01,000 --> 00:03:04,980 Mar sin, táimid ag aistriú an chéad eilimint ar an taobh na láimhe deise den bhalla leis an mhaighdeog, 69 00:03:04,980 --> 00:03:06,410 agus tá a fhios againn ar an mhaighdeog ar ina sheasamh ceart. 70 00:03:06,410 --> 00:03:11,130 71 00:03:11,130 --> 00:03:15,650 >> Táimid arís ansin an próiseas seo do na subarrays chlé agus ar dheis ar an mhaighdeog. 72 00:03:15,650 --> 00:03:18,700 Ós rud é go bhfuil an subarray seo caite ach amháin eilimint fada, tá a fhios againn go bhfuil cheana féin 73 00:03:18,700 --> 00:03:22,480 sórtáilte mar gheall ar conas is féidir leat a bheith as a ordú má tá tú ach eilimint amháin? 74 00:03:22,480 --> 00:03:28,860 Chun an taobh dheis de na subarray, táimid ag a fheiceáil go bhfuil an pivot 5, agus an balla 75 00:03:28,860 --> 00:03:32,250 fágtha ach na 6. 76 00:03:32,250 --> 00:03:34,970 Agus an eilimint atá ann faoi láthair chomh maith Tosaíonn amach mar an 6. 77 00:03:34,970 --> 00:03:36,200 Mar sin, tá 6 níos mó ná 5. 78 00:03:36,200 --> 00:03:38,590 Saoire againn sé i gcás ina bhfuil sé ar an taobh na láimhe deise den bhalla. 79 00:03:38,590 --> 00:03:41,060 Anois, ag bogadh ar aghaidh, tá 3 níos lú ná 5. 80 00:03:41,060 --> 00:03:44,160 Mar sin, táimid ag aistriú sé leis an chéad eilimint díreach i gceart ar an bhalla. 81 00:03:44,160 --> 00:03:47,944 82 00:03:47,944 --> 00:03:50,750 Anois, bhog mé an balla suas amháin. 83 00:03:50,750 --> 00:03:53,010 Anois, ag bogadh ar aghaidh go dtí an 8. 84 00:03:53,010 --> 00:03:56,480 8 Tá níos mó ná 5, agus mar sin a fhágann muid é. 85 00:03:56,480 --> 00:03:58,720 Is é an 4 níos lú ná 5, mar sin athrú dúinn é. 86 00:03:58,720 --> 00:04:02,950 87 00:04:02,950 --> 00:04:03,570 Agus ar. 88 00:04:03,570 --> 00:04:04,820 Agus ar. 89 00:04:04,820 --> 00:04:10,190 90 00:04:10,190 --> 00:04:13,670 >> Gach uair arís againn ar an bpróiseas ar an taobh chlé agus ar dheis ar an eagar. againn 91 00:04:13,670 --> 00:04:17,010 roghnú mhaighdeog agus a dhéanann na comparáidí agus a chruthú ar leibhéal eile ar chlé agus 92 00:04:17,010 --> 00:04:18,240 subarrays ceart. 93 00:04:18,240 --> 00:04:21,500 Beidh an glao athchúrsach ar aghaidh go dtí a bhaint amach againn an deireadh nuair a tá muid 94 00:04:21,500 --> 00:04:25,290 roinnte suas an sraith iomlán i ach subarrays d'fhad 1. 95 00:04:25,290 --> 00:04:28,060 Ó ann, tá a fhios againn go bhfuil an sraith curtha in eagar toisc go bhfuil gach eilimint, ag 96 00:04:28,060 --> 00:04:29,330 pointe áirithe, ina mhaighdeog. 97 00:04:29,330 --> 00:04:32,720 I bhfocail eile, do gach eilimint, gach Is iad na huimhreacha ar an taobh clé lú 98 00:04:32,720 --> 00:04:36,420 luachanna agus na huimhreacha go dtí an Tá luachanna níos mó ceart. 99 00:04:36,420 --> 00:04:38,980 >> Oibríonn an modh seo an-maith má tá an Is é luach an mhaighdeog roghnaithe 100 00:04:38,980 --> 00:04:41,930 thart i lár raon de luachanna liosta. 101 00:04:41,930 --> 00:04:45,630 Chiallódh sé seo go, tar éis dúinn bogadh eilimintí thart, tá thart ar an oiread 102 00:04:45,630 --> 00:04:48,390 gnéithe ar an taobh clé den mhaighdeog mar go bhfuil go dtí an ceart. 103 00:04:48,390 --> 00:04:52,380 Agus nádúr scoilt-agus-conquer an Tá algartam Quicksort tógadh ansin 104 00:04:52,380 --> 00:04:53,850 buntáiste iomlán de. 105 00:04:53,850 --> 00:04:57,500 Cruthaíonn sé seo runtime O (n logáil n,) an n toisc go bhfuil muid a dhéanamh n lúide 1 106 00:04:57,500 --> 00:05:01,640 comparáidí ar gach glúin agus logáil n toisc go bhfuil muid a roinnt ar an liosta 107 00:05:01,640 --> 00:05:03,210 logáil amanna n. 108 00:05:03,210 --> 00:05:06,160 Mar sin féin, sna cásanna is measa, an Is féidir le algartam a iarbhír O (n 109 00:05:06,160 --> 00:05:09,850 cearnógach.) Cuir ar gach glúin, an mhaighdeog tharlaíonn ach sin a bheith ar an 110 00:05:09,850 --> 00:05:12,520 is lú nó an ceann is mó de na uimhreacha táimid ag sórtáil. 111 00:05:12,520 --> 00:05:15,870 Chiallódh sé seo a bhriseadh síos ar an liosta n amanna agus ag déanamh n lúide 1 112 00:05:15,870 --> 00:05:17,690 comparáidí gach uair amháin. 113 00:05:17,690 --> 00:05:20,490 Dá bhrí sin, o n cearnógach. 114 00:05:20,490 --> 00:05:22,000 >> Conas is féidir linn feabhas a chur ar an modh? 115 00:05:22,000 --> 00:05:25,100 Is é ceann bhealach maith chun feabhas a chur ar an modh a ghearradh síos ar an dóchúlacht go 116 00:05:25,100 --> 00:05:28,150 Is é an runtime riamh iarbhír o n cearnógach. 117 00:05:28,150 --> 00:05:31,860 Cuimhnigh seo measa, cás is measa Is féidir tarlú ach amháin nuair a 118 00:05:31,860 --> 00:05:35,320 Is mhaighdeog a roghnaíodh i gcónaí ar an airde nó an luach is ísle sa eagar. 119 00:05:35,320 --> 00:05:38,630 Chun a chinntiú go bhfuil sé seo níos lú seans ann go dtarlódh, is féidir linn teacht ar an mhaighdeog ag 120 00:05:38,630 --> 00:05:42,610 roghnú eilimintí éagsúla agus ag cur an luach meánach. 121 00:05:42,610 --> 00:05:44,650 >> Is é mo ainm Mark Grozen-Smith, agus tá sé seo CS50. 122 00:05:44,650 --> 00:05:47,790 123 00:05:47,790 --> 00:05:50,930 >> Chun simplíocht, a ligean ar glacadh leis go bhfuil sin Tá rudaí ach slánuimhreacha, ach 124 00:05:50,930 --> 00:05:51,970 Tá a fhios go bhfuil Quicksert - 125 00:05:51,970 --> 00:05:53,160 Quicksert? 126 00:05:53,160 --> 00:05:55,200 Tá brón orm. 127 00:05:55,200 --> 00:06:02,000 >> Anseo ní mór dúinn an slánuimhreacha 6, 5, 1, 3, 8, 4, 9. 128 00:06:02,000 --> 00:06:03,200 >> Cainteoir 1: really? 129 00:06:03,200 --> 00:06:04,850 >> Cainteoir 2: Ná stop a chur ann. 130 00:06:04,850 --> 00:06:06,100 >> Cainteoir 1: really? 131 00:06:06,100 --> 00:06:08,491