1 00:00:00,000 --> 00:00:03,360 >> [Musik spiller] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD: Okay, så boble sortere er en algoritme 4 00:00:06,730 --> 00:00:08,730 du kan bruge til at sortere et sæt af elementer. 5 00:00:08,730 --> 00:00:10,850 Lad os tage et kig på, hvordan det fungerer. 6 00:00:10,850 --> 00:00:13,240 >> Så den grundlæggende idé bag boble sortere er dette. 7 00:00:13,240 --> 00:00:17,340 Vi generelt ønsker at flytte højere værdsatte elementer generelt til højre, 8 00:00:17,340 --> 00:00:20,340 og sænk værdsatte elementer generelt til venstre, som vi ville forvente. 9 00:00:20,340 --> 00:00:23,256 Vi ønsker de nederste ting at være på begyndelsen, og de højere ting 10 00:00:23,256 --> 00:00:24,970 at være ved enden. 11 00:00:24,970 --> 00:00:26,130 >> Hvordan gør vi det? 12 00:00:26,130 --> 00:00:28,040 Godt i pseudokode kode, vi kunne sige, lad os 13 00:00:28,040 --> 00:00:30,320 sætte en swap mod en ikke-nul værdi. 14 00:00:30,320 --> 00:00:32,570 Vi vil se, hvorfor vi gør det i en anden. 15 00:00:32,570 --> 00:00:36,090 Og derefter gentage vi følgende proces, indtil swap tælleren er 0, 16 00:00:36,090 --> 00:00:39,910 eller indtil vi gør ingen swaps overhovedet. 17 00:00:39,910 --> 00:00:43,170 >> Nulstil swap imod 0, hvis den ikke allerede er 0. 18 00:00:43,170 --> 00:00:46,420 Derefter se på hver tilstødende par af elementer. 19 00:00:46,420 --> 00:00:49,550 Hvis disse to elementer er ikke i orden, bytte dem, 20 00:00:49,550 --> 00:00:51,620 og der tilsættes 1 til swap tæller. 21 00:00:51,620 --> 00:00:53,870 Hvis du tænker på dette, før du visualisere det, 22 00:00:53,870 --> 00:00:57,471 bemærke, at dette vil bevæge lavere værdsatte elementer til venstre 23 00:00:57,471 --> 00:01:00,720 og højere værdsat elementer til højre, effektivt gør, hvad vi ønsker at gøre, 24 00:01:00,720 --> 00:01:03,940 som er flytte disse grupper elementer i den måde. 25 00:01:03,940 --> 00:01:07,035 Lad os forestille sig, hvordan dette kan se ved hjælp af vores vifte 26 00:01:07,035 --> 00:01:10,504 som vi brugte til at teste disse algoritmer. 27 00:01:10,504 --> 00:01:13,420 Vi har en usorteret matrix her igen, angivet ved alle elementerne 28 00:01:13,420 --> 00:01:14,840 være rødt. 29 00:01:14,840 --> 00:01:17,970 Og jeg satte mit bytte tæller til en værdi forskellig fra nul. 30 00:01:17,970 --> 00:01:20,610 Jeg vilkårligt valgte negativ 1-- det er ikke 0. 31 00:01:20,610 --> 00:01:23,840 Vi ønsker at gentage denne proces indtil swap tælleren er 0. 32 00:01:23,840 --> 00:01:26,540 Det er derfor, jeg indstille min bytte imod nogle ikke-nul, 33 00:01:26,540 --> 00:01:29,400 fordi ellers swap tæller ville være 0. 34 00:01:29,400 --> 00:01:31,610 Vi ville ikke engang begynde processen med algoritmen. 35 00:01:31,610 --> 00:01:33,610 Så igen, are-- trinnene nulstille swap tælleren 36 00:01:33,610 --> 00:01:37,900 til 0, så kig på hver tilstødende par, og hvis de er ude af orden, 37 00:01:37,900 --> 00:01:40,514 bytte dem, og der tilsættes 1 til swap tæller. 38 00:01:40,514 --> 00:01:41,680 Så lad os begynde denne proces. 39 00:01:41,680 --> 00:01:44,430 Så det første, vi gør, er vi satte swap imod 0, 40 00:01:44,430 --> 00:01:46,660 og så må vi begynde at kigge på hvert tilstødende par. 41 00:01:46,660 --> 00:01:49,140 >> Så vi først begynde at kigge på 5 og 2. 42 00:01:49,140 --> 00:01:52,410 Vi ser, at de er ude af bestille og så vi bytte dem. 43 00:01:52,410 --> 00:01:53,830 Og vi tilføjer 1 til swap tæller. 44 00:01:53,830 --> 00:01:57,860 Så nu er vores swap tælleren er 1, og 2 og 5 er blevet skiftet. 45 00:01:57,860 --> 00:01:59,370 Nu skal vi gentage processen igen. 46 00:01:59,370 --> 00:02:03,540 >> Vi ser på den næste tilstødende par, 5 og 1-- de er også ude af drift, 47 00:02:03,540 --> 00:02:06,960 så vi bytte dem og tilføje 1 til swap tælleren. 48 00:02:06,960 --> 00:02:08,900 Så ser vi på 5 og 3. 49 00:02:08,900 --> 00:02:13,830 De er ude af drift, så vi bytte dem, og vi tilføjer 1 til swap tæller. 50 00:02:13,830 --> 00:02:15,550 Så ser vi på 5 og 6. 51 00:02:15,550 --> 00:02:18,630 De er i orden, så vi faktisk ikke nødt til at bytte noget denne gang. 52 00:02:18,630 --> 00:02:20,250 Så ser vi på 6 og 4. 53 00:02:20,250 --> 00:02:24,920 De er også ude af drift, så vi bytte dem, og vi tilføjer 1 til swap tæller. 54 00:02:24,920 --> 00:02:26,230 >> Nu opdager hvad der er sket. 55 00:02:26,230 --> 00:02:29,514 Vi har flyttet 6 hele vejen til enden. 56 00:02:29,514 --> 00:02:32,180 Så i udvælgelsen sortere, hvis du har set, at video, hvad vi gjorde, var 57 00:02:32,180 --> 00:02:35,290 vi endte med at flytte den mindste elementer i bygningen 58 00:02:35,290 --> 00:02:39,640 det sorterede matrix hovedsagelig fra venstre til højre, mindste til den største. 59 00:02:39,640 --> 00:02:43,200 I tilfælde af boble sortere, hvis vi er efter denne bestemte algoritme, 60 00:02:43,200 --> 00:02:46,720 vi faktisk kommer til at bygge det sorterede vifte fra højre 61 00:02:46,720 --> 00:02:49,100 til venstre, største til mindste. 62 00:02:49,100 --> 00:02:53,840 Vi har effektivt boblet 6, den største værdi, hele vejen til enden. 63 00:02:53,840 --> 00:02:56,165 >> Og så kan vi nu erklære at det er sorteret, 64 00:02:56,165 --> 00:02:59,130 og i fremtiden iterations-- gennemgår array igen-- 65 00:02:59,130 --> 00:03:01,280 Vi behøver ikke at overveje 6 længere. 66 00:03:01,280 --> 00:03:03,850 Vi behøver kun at overveje de usorterede elementer 67 00:03:03,850 --> 00:03:06,299 når vi kigger på tilstødende par. 68 00:03:06,299 --> 00:03:08,340 Så vi er færdige én passere gennem boble slags. 69 00:03:08,340 --> 00:03:11,941 Så nu går vi tilbage til spørgsmålet, gentag indtil swap tælleren er 0. 70 00:03:11,941 --> 00:03:13,690 Nå swap counter er 4, så vi vil 71 00:03:13,690 --> 00:03:15,410 at holde at gentage denne proces igen. 72 00:03:15,410 --> 00:03:19,180 >> Vi kommer til at nulstille swap tælleren til 0, og se på hvert tilstødende par. 73 00:03:19,180 --> 00:03:21,890 Så vi starter med 2 og 1-- de er ude af drift, så vi bytte dem 74 00:03:21,890 --> 00:03:23,620 og vi tilføjer 1 til swap tæller. 75 00:03:23,620 --> 00:03:25,490 2 og 3, er de i orden. 76 00:03:25,490 --> 00:03:27,060 Vi behøver ikke at gøre noget. 77 00:03:27,060 --> 00:03:28,420 3 og 5 er i orden. 78 00:03:28,420 --> 00:03:30,150 Vi behøver ikke at gøre noget der. 79 00:03:30,150 --> 00:03:32,515 >> 5 og 4, de er ude af orden, og så vi 80 00:03:32,515 --> 00:03:35,130 nødt til at bytte dem og tilføje 1 til swap tælleren. 81 00:03:35,130 --> 00:03:38,880 Og nu har vi flyttet 5, den næststørste element, 82 00:03:38,880 --> 00:03:40,920 til slutningen af ​​usorteret del. 83 00:03:40,920 --> 00:03:44,360 Så kan vi nu kalder det del af sorteret del. 84 00:03:44,360 --> 00:03:47,180 >> Nu du kigger på den skærm og sandsynligvis kan fortælle, 85 00:03:47,180 --> 00:03:50,130 som kan jeg, at arrayet sorteres lige nu. 86 00:03:50,130 --> 00:03:51,820 Men vi kan ikke bevise, at endnu. 87 00:03:51,820 --> 00:03:54,359 Vi har ikke en garanti at det er ordnet. 88 00:03:54,359 --> 00:03:56,900 Men det er her swap tæller kommer til at komme i spil. 89 00:03:56,900 --> 00:03:59,060 >> Så vi har afsluttet et pass. 90 00:03:59,060 --> 00:04:00,357 Swap tæller er 2. 91 00:04:00,357 --> 00:04:02,190 Så vi kommer til at gentage denne proces igen, 92 00:04:02,190 --> 00:04:04,290 gentag indtil swap tælleren er 0. 93 00:04:04,290 --> 00:04:05,550 Nulstil swap imod 0. 94 00:04:05,550 --> 00:04:06,820 Så vi vil nulstille den. 95 00:04:06,820 --> 00:04:09,810 >> Nu ser på hvert tilstødende par. 96 00:04:09,810 --> 00:04:11,880 Det er i orden, 1 og 2. 97 00:04:11,880 --> 00:04:13,590 2 og 3 er i orden. 98 00:04:13,590 --> 00:04:15,010 3 og 4 er i orden. 99 00:04:15,010 --> 00:04:19,250 Så på dette punkt, mærke, vi har gennemført ser på hver hosliggende par, 100 00:04:19,250 --> 00:04:22,530 men swap tælleren er stadig 0. 101 00:04:22,530 --> 00:04:25,520 >> Hvis vi ikke behøver at skifte eventuelle elementer, så de 102 00:04:25,520 --> 00:04:28,340 skal være i orden, ved kraft af denne proces. 103 00:04:28,340 --> 00:04:32,000 Og så en effektivitet slags, At vi dataloger elsker, 104 00:04:32,000 --> 00:04:35,560 er kan vi nu erklære hele systemet skal 105 00:04:35,560 --> 00:04:38,160 sorteres, fordi vi ikke gjorde nødt til at skifte eventuelle elementer. 106 00:04:38,160 --> 00:04:40,380 Det er ret nice. 107 00:04:40,380 --> 00:04:43,260 >> Så hvad er den værste fald scenarie med boble slags? 108 00:04:43,260 --> 00:04:46,240 I værste fald array er i helt omvendt rækkefølge, 109 00:04:46,240 --> 00:04:49,870 og så vi er nødt til at boble hver af de store elementer alle 110 00:04:49,870 --> 00:04:51,780 vejen på tværs af array. 111 00:04:51,780 --> 00:04:55,350 Og vi effektivt også nødt til at boble alle de små elementer tilbage 112 00:04:55,350 --> 00:04:57,050 hele vejen på tværs af array, også. 113 00:04:57,050 --> 00:05:01,950 Så hver af de n elementer skal bevæge sig på tværs af alle de andre n elementer. 114 00:05:01,950 --> 00:05:04,102 Så det er det værst tænkelige scenarie. 115 00:05:04,102 --> 00:05:05,810 I bedste fald scenario om, det er 116 00:05:05,810 --> 00:05:07,880 lidt anderledes fra valg slags. 117 00:05:07,880 --> 00:05:10,040 Grupperingen er allerede sorteres, når vi går i. 118 00:05:10,040 --> 00:05:12,550 Vi har ikke at gøre nogen swaps på den første passage. 119 00:05:12,550 --> 00:05:14,940 Så vi måske nødt til at se på færre elementer, ikke? 120 00:05:14,940 --> 00:05:18,580 Vi behøver ikke at gentage dette behandle en række gange. 121 00:05:18,580 --> 00:05:19,540 >> Så hvad betyder det? 122 00:05:19,540 --> 00:05:22,390 Så hvad er den værst tænkelige scenarie til boble sortere, og hvad der er 123 00:05:22,390 --> 00:05:25,330 den bedste tænkelige scenario for boble slags? 124 00:05:25,330 --> 00:05:27,770 Vidste du gætte det? 125 00:05:27,770 --> 00:05:32,420 I værste fald er du nødt til gentage på tværs af alle n elementer n gange. 126 00:05:32,420 --> 00:05:34,220 Så det værste tilfælde er n potens. 127 00:05:34,220 --> 00:05:36,550 >> Hvis array er perfekt sorterede selv, kun du 128 00:05:36,550 --> 00:05:38,580 nødt til at se på hver af elementerne gang. 129 00:05:38,580 --> 00:05:42,670 Og hvis swap tælleren er stadig 0, du kan sige dette array er sorteret. 130 00:05:42,670 --> 00:05:45,780 Og så i bedste fald, er dette faktisk bedre end valg 131 00:05:45,780 --> 00:05:49,230 sort-- det er omega n. 132 00:05:49,230 --> 00:05:50,270 >> Jeg er Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Det er CS50. 134 00:05:52,140 --> 00:05:54,382