1 00:00:00,000 --> 00:00:03,360 >> [MUSIC PLAYING] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD: Omni jure, ita borrire modi est an algorithm 4 00:00:06,730 --> 00:00:08,730 exstat possis statuto elementis redditus extat. 5 00:00:08,730 --> 00:00:10,850 Vide quam sit amet facit. 6 00:00:10,850 --> 00:00:13,240 >> Ita basic idea post borrire modi est. 7 00:00:13,240 --> 00:00:17,340 Plerumque vis movet superiora aestimantur elementa communiter ad dextram, 8 00:00:17,340 --> 00:00:20,340 et generaliter inferiora elementa aestimantur ad sinistram, ut debebat. 9 00:00:20,340 --> 00:00:23,256 Volumus inferiora esse initio superiora 10 00:00:23,256 --> 00:00:24,970 quod sit ad finem. 11 00:00:24,970 --> 00:00:26,130 >> Quomodo nos hoc facere? 12 00:00:26,130 --> 00:00:28,040 Bene in pseudocode codice, dicere possimus, lets ' 13 00:00:28,040 --> 00:00:30,320 contra id quod positum est PERMUTO non-nulla valorem. 14 00:00:30,320 --> 00:00:32,570 Nos faciemus cur altero. 15 00:00:32,570 --> 00:00:36,090 Et tunc dicimus sequentibus processus usque ad occurro PERMUTO est 0, 16 00:00:36,090 --> 00:00:39,910 donec vel omnino nihil strigili. 17 00:00:39,910 --> 00:00:43,170 >> Reset PERMUTO contra 0 si suus 'non iam 0. 18 00:00:43,170 --> 00:00:46,420 Et respiciens omnem adjacent par elementorum. 19 00:00:46,420 --> 00:00:49,550 Si illa duo elementa sunt non ordine, PERMUTO eos 20 00:00:49,550 --> 00:00:51,620 et addere I ad PERMUTO occurro. 21 00:00:51,620 --> 00:00:53,870 Si vestri 'ratus de hac in conspectu tuo visualize it, 22 00:00:53,870 --> 00:00:57,471 animadvertit sic hoc esse movebo inferiora aestimantur elementa ad sinistram 23 00:00:57,471 --> 00:01:00,720 et superiora elementa aestimantur ad dextram, efficaciter ea quae uolumus, 24 00:01:00,720 --> 00:01:03,940 quod move illorum coetuum elementorum in viam illam. 25 00:01:03,940 --> 00:01:07,035 Lets visualize quomodo hoc ut viderem nostris utentibus array 26 00:01:07,035 --> 00:01:10,504 usi sumus, ut in ipsis experiretur haec algorithms. 27 00:01:10,504 --> 00:01:13,420 Habemus hic unsorted array iterum, indicatur per omnes elementorum 28 00:01:13,420 --> 00:01:14,840 sit in rufam habuerit cicatricem. 29 00:01:14,840 --> 00:01:17,970 Et posui faciem meam PERMUTO counter nonzero ad valorem. 30 00:01:17,970 --> 00:01:20,610 I finxerat negative 1-- suus 'non 0. 31 00:01:20,610 --> 00:01:23,840 Volumus Repetere hoc processus usque ad occurro PERMUTO est 0. 32 00:01:23,840 --> 00:01:26,540 Hanc ipsam ob causam meam PERMUTO contra aliquod non-nulla valorem, 33 00:01:26,540 --> 00:01:29,400 quia aliter PERMUTO occurro esset 0. 34 00:01:29,400 --> 00:01:31,610 Non essemus socii etiam incipiant processus algorithm. 35 00:01:31,610 --> 00:01:33,610 Sic conversus cogitavi, in gradibus are-- reset PERMUTO counter 36 00:01:33,610 --> 00:01:37,900 0, respiciens omnem deinceps Geminos et haerent extra ordinem 37 00:01:37,900 --> 00:01:40,514 PERMUTO eos, et addere I ad PERMUTO occurro. 38 00:01:40,514 --> 00:01:41,680 Eamus ergo hoc primum. 39 00:01:41,680 --> 00:01:44,430 Primum igitur facimus constituimus VERTO contra 0, 40 00:01:44,430 --> 00:01:46,660 et tunc satus vultus at quisque adjacent par. 41 00:01:46,660 --> 00:01:49,140 >> Ita et nos primoris satus aspiciens ad V et II. 42 00:01:49,140 --> 00:01:52,410 Videmus enim quod e Sic PERMUTO eos iubet. 43 00:01:52,410 --> 00:01:53,830 I Et addimus ad PERMUTO lorem. 44 00:01:53,830 --> 00:01:57,860 Ita nunc nostra PERMUTO is occurro I, et II et V sunt switched. 45 00:01:57,860 --> 00:01:59,370 Nunc autem soluti sumus rursus repetere processus. 46 00:01:59,370 --> 00:02:03,540 >> Nos respice in contiguo proximo pari V et 1-- haerent etiam extra ordinem 47 00:02:03,540 --> 00:02:06,960 ita et nos PERMUTO eos add I ad PERMUTO occurro. 48 00:02:06,960 --> 00:02:08,900 Videamus ergo in III et V. 49 00:02:08,900 --> 00:02:13,830 Sunt extra ordinem ita RES et I ad PERMUTO addimus lorem. 50 00:02:13,830 --> 00:02:15,550 V et VI et videamus. 51 00:02:15,550 --> 00:02:18,630 Nulla ut sic dicendo non utimur PERMUTO quicquam eget nunc. 52 00:02:18,630 --> 00:02:20,250 IV et VI et videamus. 53 00:02:20,250 --> 00:02:24,920 Sunt etiam ex ordine, ita RES et I ad PERMUTO addimus lorem. 54 00:02:24,920 --> 00:02:26,230 >> Nunc intendat quid acciderit. 55 00:02:26,230 --> 00:02:29,514 VI moti sumus usque ad finem. 56 00:02:29,514 --> 00:02:32,180 In electione huiusmodi, si quid habes quod video, quae faciebat 57 00:02:32,180 --> 00:02:35,290 nos nisus sursum movens minima elementa in aedificando 58 00:02:35,290 --> 00:02:39,640 in sorted array essentialiter ad dextrum perveniam minima maxima. 59 00:02:39,640 --> 00:02:43,200 In bulla sort si nos sequentem hoc algorithm, 60 00:02:43,200 --> 00:02:46,720 sumus actu iens ut aedificarem in sorted array a dextro 61 00:02:46,720 --> 00:02:49,100 sinistra, ut maximis minima. 62 00:02:49,100 --> 00:02:53,840 VI ebulliit efficaciter nos et maximi momenti, usque ad finem. 63 00:02:53,840 --> 00:02:56,165 >> Et ideo non possumus nunc renuntiate quod est sorted, 64 00:02:56,165 --> 00:02:59,130 et in futuro iterations-- perambulabat array again-- 65 00:02:59,130 --> 00:03:01,280 non amplius considerandum VI. 66 00:03:01,280 --> 00:03:03,850 Nos eis tantummodo schismatis considerandum elementa in unsorted 67 00:03:03,850 --> 00:03:06,299 cum nos 'vultus procul adjacent paria. 68 00:03:06,299 --> 00:03:08,340 Ita consummavi unum pertransibo borrire modi. 69 00:03:08,340 --> 00:03:11,941 Nunc ergo ad propositum revertamur, repetere usque ad occurro PERMUTO est 0. 70 00:03:11,941 --> 00:03:13,690 Tam PERMUTO counter IV est, ita dicturi sumus 71 00:03:13,690 --> 00:03:15,410 ut iterum repetens hoc processu. 72 00:03:15,410 --> 00:03:19,180 >> Erant 'iens ad reset PERMUTO counter 0, contemplo adjacent coniugatione. 73 00:03:19,180 --> 00:03:21,890 Sic nos satus cum II et 1-- haerent de ordine, et nos PERMUTO 74 00:03:21,890 --> 00:03:23,620 et I ad PERMUTO addimus lorem. 75 00:03:23,620 --> 00:03:25,490 II et III, ut agant. 76 00:03:25,490 --> 00:03:27,060 Non opus est. 77 00:03:27,060 --> 00:03:28,420 III et V sunt in ordinem confectae. 78 00:03:28,420 --> 00:03:30,150 Non opus est aliquo. 79 00:03:30,150 --> 00:03:32,515 >> IV et V agunt ordinis, et sic 80 00:03:32,515 --> 00:03:35,130 opus ad PERMUTO eos et add I ad PERMUTO occurro. 81 00:03:35,130 --> 00:03:38,880 Nunc eget V movetur, altera pretium elementum, 82 00:03:38,880 --> 00:03:40,920 ad finem capitis pars music. 83 00:03:40,920 --> 00:03:44,360 Considerari ergo potest nunc appello illud ipsum part of the sorted portio. 84 00:03:44,360 --> 00:03:47,180 >> Nunc vestri 'vultus procul screen et probabiliter scire potest nuntio, 85 00:03:47,180 --> 00:03:50,130 ut possum, illam aciem est iam sorted ius. 86 00:03:50,130 --> 00:03:51,820 Sed tamen non potest. 87 00:03:51,820 --> 00:03:54,359 Nos non habent spondet quod suus 'sorted. 88 00:03:54,359 --> 00:03:56,900 Sed hoc est ubi PERMUTO occurro futurum exoriri. 89 00:03:56,900 --> 00:03:59,060 >> Itaque nos confecto saltum. 90 00:03:59,060 --> 00:04:00,357 VERTO occurro est II. 91 00:04:00,357 --> 00:04:02,190 Ita et nos erant 'iens ut repetere hoc processu iterum, 92 00:04:02,190 --> 00:04:04,290 repetere usque ad occurro PERMUTO est 0. 93 00:04:04,290 --> 00:04:05,550 Reset PERMUTO contra 0. 94 00:04:05,550 --> 00:04:06,820 Sic puteus reset it. 95 00:04:06,820 --> 00:04:09,810 >> Auditis hostium copiis respicerent singulis adjacent coniugatione. 96 00:04:09,810 --> 00:04:11,880 Hoc ordine I et II. 97 00:04:11,880 --> 00:04:13,590 II et III sunt in ordinem confectae. 98 00:04:13,590 --> 00:04:15,010 III et IV in ordine. 99 00:04:15,010 --> 00:04:19,250 Et hic adverte diximus completur respiciens omnem adjacent par, 100 00:04:19,250 --> 00:04:22,530 sed PERMUTO occurro adhuc 0. 101 00:04:22,530 --> 00:04:25,520 >> Si non habeat artem cuiusquam elementi, tunc 102 00:04:25,520 --> 00:04:28,340 oportet esse in ordinem, Vi huius processus. 103 00:04:28,340 --> 00:04:32,000 Vnde efficientia generis ut computatrum scientists amant, 104 00:04:32,000 --> 00:04:35,560 is nunc possumus quinam annuntiabit totius array esse 105 00:04:35,560 --> 00:04:38,160 replent, quia non habent PERMUTO cuiusquam elementi. 106 00:04:38,160 --> 00:04:40,380 Quod suus 'pulchellus nice quod. 107 00:04:40,380 --> 00:04:43,260 >> Quid pessimum casu missione cum bulla modi? 108 00:04:43,260 --> 00:04:46,240 Maxime in re ad bellum omnino in inverso ordine, 109 00:04:46,240 --> 00:04:49,870 et sic uterque ebullire magna elementa omnia 110 00:04:49,870 --> 00:04:51,780 per viam ordinata. 111 00:04:51,780 --> 00:04:55,350 Et efficaciter etiam consequenter habent bulla omnes small elementa back 112 00:04:55,350 --> 00:04:57,050 per viam ordinata est. 113 00:04:57,050 --> 00:05:01,950 Ita unaquaeque n elementa moveri per omnes alias n elementis redditus extat. 114 00:05:01,950 --> 00:05:04,102 Et quod pessimum casu missione. 115 00:05:04,102 --> 00:05:05,810 In optimo casu missione licet, hoc est 116 00:05:05,810 --> 00:05:07,880 paulo aliter de Selectionem huiusmodi. 117 00:05:07,880 --> 00:05:10,040 In aciem est iam si ierimus in sorted. 118 00:05:10,040 --> 00:05:12,550 Neque enim quicquam swaps ad primum saltum. 119 00:05:12,550 --> 00:05:14,940 Ut habeamus respicere at pauciores elementa, ius? 120 00:05:14,940 --> 00:05:18,580 Non habemus hic repetere aliquoties in processu. 121 00:05:18,580 --> 00:05:19,540 >> Et quid est istuc? 122 00:05:19,540 --> 00:05:22,390 Quid peius casu missione in bulla genus quid 123 00:05:22,390 --> 00:05:25,330 optimus casu missione pro bulla modi? 124 00:05:25,330 --> 00:05:27,770 Did vos coniecto hoc? 125 00:05:27,770 --> 00:05:32,420 Maxime in re abs te repetere per omnia elementa n vicibus n. 126 00:05:32,420 --> 00:05:34,220 Ita pessimum casu n quadrat. 127 00:05:34,220 --> 00:05:36,550 >> Si array est perfecte sorted licet, vos solos pervenit 128 00:05:36,550 --> 00:05:38,580 ad singula inspiciamus elementorum semel. 129 00:05:38,580 --> 00:05:42,670 Et si PERMUTO occurro adhuc 0, possis dicere eiusmodi obicitur. 130 00:05:42,670 --> 00:05:45,780 Itaque optimum est, quod actu melius quam lectio 131 00:05:45,780 --> 00:05:49,230 Sort-- suus omega n. 132 00:05:49,230 --> 00:05:50,270 >> Im Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Hoc est CS50. 134 00:05:52,140 --> 00:05:54,382