1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: Laten we een kijkje nemen op selectie sorteren, een algoritme 2 00:00:09,980 --> 00:00:12,800 voor het nemen van een lijst van nummers en ze te sorteren. 3 00:00:12,800 --> 00:00:15,750 Een algoritme onthouden is gewoon een stap-voor-stap 4 00:00:15,750 --> 00:00:18,370 procedure voor het uitvoeren van een taak. 5 00:00:18,370 --> 00:00:21,470 Het basisidee achter selection sort is te verdelen naar 6 00:00:21,470 --> 00:00:23,390 onze lijst in twee delen - 7 00:00:23,390 --> 00:00:26,810 een gesorteerd deel en een ongesorteerd deel. 8 00:00:26,810 --> 00:00:30,200 Bij elke stap van het algoritme wordt een aantal verplaatst van de 9 00:00:30,200 --> 00:00:33,800 ongesorteerde deel aan de gesorteerde gedeelte totdat uiteindelijk de 10 00:00:33,800 --> 00:00:35,880 hele lijst is gesorteerd. 11 00:00:35,880 --> 00:00:38,510 Dus hier is een lijst van zes cijfers - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8 en 15. 13 00:00:44,010 --> 00:00:47,680 Op dit moment de hele lijst wordt beschouwd als ongesorteerd. 14 00:00:47,680 --> 00:00:51,770 Hoewel een aantal als 16 mogelijk al in de juiste 15 00:00:51,770 --> 00:00:56,040 locatie, ons algoritme heeft geen manier om te weten dat tot de 16 00:00:56,040 --> 00:00:57,980 hele lijst is gesorteerd. 17 00:00:57,980 --> 00:01:01,355 Dus we zullen beschouwen elk nummer worden ongesorteerde totdat we sorteren 18 00:01:01,355 --> 00:01:03,800 het zelf. 19 00:01:03,800 --> 00:01:06,890 We weten dat we de lijst moet worden in oplopende volgorde. 20 00:01:06,890 --> 00:01:10,200 Dus we willen de opbouw van het gesorteerd deel van onze lijst 21 00:01:10,200 --> 00:01:13,280 van links naar rechts, van klein naar groot. 22 00:01:13,280 --> 00:01:17,970 Om dat te doen, moeten we tot het minimum ongesorteerde element te vinden 23 00:01:17,970 --> 00:01:21,350 en het voor het einde van het gedeelte gesorteerd. 24 00:01:21,350 --> 00:01:25,370 Aangezien deze lijst niet gesorteerd, de enige manier om dat te doen is 25 00:01:25,370 --> 00:01:29,330 kijken naar elk element in de ongesorteerde deel, herinneren 26 00:01:29,330 --> 00:01:32,010 welk element de laagste en vergelijken 27 00:01:32,010 --> 00:01:33,770 elk element dat. 28 00:01:33,770 --> 00:01:36,150 Dus we zullen eerst eens kijken naar de 23. 29 00:01:36,150 --> 00:01:38,650 Dit is het eerste element die we hebben gezien, dus we herinneren zullen 30 00:01:38,650 --> 00:01:40,050 als het minimum. 31 00:01:40,050 --> 00:01:42,320 Vervolgens zullen we kijken naar 42. 32 00:01:42,320 --> 00:01:46,720 42 is groter dan 23, dus 23 is nog minimum. 33 00:01:46,720 --> 00:01:51,210 Vervolgens is de 4 die kleiner is dan 23, dus we zullen herinneren 4 34 00:01:51,210 --> 00:01:52,880 als nieuwe minimum. 35 00:01:52,880 --> 00:01:56,380 Vervolgens is 16 die groter is dan 4, dus 4 36 00:01:56,380 --> 00:01:57,980 blijft het minimum. 37 00:01:57,980 --> 00:02:03,670 8 is groter dan 4 en 15 groter is dan 4, dus 4 moet 38 00:02:03,670 --> 00:02:05,980 de kleinste ongesorteerde element. 39 00:02:05,980 --> 00:02:09,350 Dus ook al als mensen kunnen we direct zien dat 4 is 40 00:02:09,350 --> 00:02:12,300 de minimale element, ons algoritme moet om naar te kijken 41 00:02:12,300 --> 00:02:15,710 elke ongesorteerd element, zelfs nadat we de 4 gevonden - de 42 00:02:15,710 --> 00:02:16,860 minimum element. 43 00:02:16,860 --> 00:02:19,900 Dus nu dat we de minimale element, 4 gevonden, dan willen we 44 00:02:19,900 --> 00:02:23,410 te verplaatsen naar de gesorteerd deel van de lijst. 45 00:02:23,410 --> 00:02:27,320 Aangezien dit de eerste stap betekent willen we vier geschat op 46 00:02:27,320 --> 00:02:29,680 het begin van de lijst. 47 00:02:29,680 --> 00:02:33,040 23 is nu aan het begin van de lijst zodat 48 00:02:33,040 --> 00:02:36,080 Laten we ruilen de 4 en de 23. 49 00:02:36,080 --> 00:02:38,870 Dus nu onze lijst ziet er als volgt. 50 00:02:38,870 --> 00:02:42,710 We weten dat 4 moet in zijn definitieve plaats, omdat het 51 00:02:42,710 --> 00:02:45,890 zowel de kleinste element en het element aan het begin 52 00:02:45,890 --> 00:02:46,960 van de lijst. 53 00:02:46,960 --> 00:02:50,650 Dit betekent dus dat we niet ooit nog een keer verplaatsen. 54 00:02:50,650 --> 00:02:53,910 Dus laten we dit proces herhalen om een ​​ander element toe te voegen aan de 55 00:02:53,910 --> 00:02:55,910 gesorteerd deel van de lijst. 56 00:02:55,910 --> 00:02:58,950 We weten dat we niet moeten kijken naar de 4, want het is 57 00:02:58,950 --> 00:03:00,000 al gesorteerd. 58 00:03:00,000 --> 00:03:03,540 Dus we kunnen beginnen bij de 42, die we zullen herinneren als de 59 00:03:03,540 --> 00:03:05,290 minimum element. 60 00:03:05,290 --> 00:03:08,700 Dus de volgende zullen we kijken naar de 23 die kleiner is dan 42, dus we 61 00:03:08,700 --> 00:03:11,620 herinner me 23 is het nieuwe minimum. 62 00:03:11,620 --> 00:03:14,870 Vervolgens geschikte 16 die kleiner is dan 23, zodat 63 00:03:14,870 --> 00:03:16,800 16 is het nieuwe minimum. 64 00:03:16,800 --> 00:03:19,720 Nu kijken we naar de 8 die kleiner is dan 16, zodat 65 00:03:19,720 --> 00:03:21,130 8 is het nieuwe minimum. 66 00:03:21,130 --> 00:03:25,900 En tenslotte 8 is minder dan 15, dus we weten dat 8 een minimum 67 00:03:25,900 --> 00:03:27,780 ongesorteerde element. 68 00:03:27,780 --> 00:03:30,660 Dus dat betekent dat we moeten 8 toe te voegen aan de gesorteerde 69 00:03:30,660 --> 00:03:32,450 deel van de lijst. 70 00:03:32,450 --> 00:03:35,990 Op dit moment 4 is het enige gesorteerd element, dus we willen plaatsen 71 00:03:35,990 --> 00:03:38,410 de 8 naast het 4. 72 00:03:38,410 --> 00:03:41,920 Aangezien 42 het eerste element in de ongesorteerde deel van de 73 00:03:41,920 --> 00:03:47,260 lijst, we willen de 42 en de 8 om te wisselen. 74 00:03:47,260 --> 00:03:49,680 Dus nu onze lijst ziet er als volgt. 75 00:03:49,680 --> 00:03:53,830 4 en 8 stellen de gesorteerde deel van de lijst en de 76 00:03:53,830 --> 00:03:56,440 resterende cijfers vertegenwoordigen de ongesorteerde 77 00:03:56,440 --> 00:03:58,260 deel van de lijst. 78 00:03:58,260 --> 00:04:00,630 Dus laten we verder gaan met een andere iteratie. 79 00:04:00,630 --> 00:04:03,850 We beginnen met 23 dit keer, omdat we niet moeten kijken naar 80 00:04:03,850 --> 00:04:05,770 de 4 en de 8 meer omdat ze hebben 81 00:04:05,770 --> 00:04:07,660 al gesorteerd. 82 00:04:07,660 --> 00:04:10,270 16 is minder dan 23, dus we herinneren zullen 83 00:04:10,270 --> 00:04:12,070 16 als de nieuwe minimum. 84 00:04:12,070 --> 00:04:18,149 16 is minder dan 42, maar 15 is minder dan 16, dus 15 te zijn moet 85 00:04:18,149 --> 00:04:20,480 de minimum ongesorteerde element. 86 00:04:20,480 --> 00:04:24,580 Dus nu willen we de 15 en de 23 om te ruilen 87 00:04:24,580 --> 00:04:26,310 geef ons deze lijst. 88 00:04:26,310 --> 00:04:30,500 De gesorteerd deel van de lijst bevat 4, 8 en 15, en 89 00:04:30,500 --> 00:04:33,210 deze elementen zijn nog steeds gesorteerd. 90 00:04:33,210 --> 00:04:36,900 Maar het gewoon zo gebeurt het dat de volgende ongesorteerde element, 16, 91 00:04:36,900 --> 00:04:38,480 al gesorteerd. 92 00:04:38,480 --> 00:04:42,060 Echter, er is geen manier voor ons algoritme om te weten dat 16 93 00:04:42,060 --> 00:04:45,230 is al in de juiste locatie, dus we moeten nog steeds 94 00:04:45,230 --> 00:04:47,870 zeg precies hetzelfde proces. 95 00:04:47,870 --> 00:04:53,750 We zien dus dat 16 is minder dan 42, en 16 is minder dan 23, dus 96 00:04:53,750 --> 00:04:56,230 16 moet de minimale element. 97 00:04:56,230 --> 00:04:59,010 Het is onmogelijk om dit element te wisselen met zichzelf, dus we kunnen 98 00:04:59,010 --> 00:05:01,780 gewoon laten op deze locatie. 99 00:05:01,780 --> 00:05:04,660 Dus we moeten nog een pas van ons algoritme. 100 00:05:04,660 --> 00:05:09,370 42 is groter dan 23, dus 23 moet de 101 00:05:09,370 --> 00:05:10,970 minimum ongesorteerde element. 102 00:05:10,970 --> 00:05:17,410 Zodra we ruilen de 23 en de 42, we eindigen met onze laatste 103 00:05:17,410 --> 00:05:18,530 gesorteerde lijst - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 We weten dat 42 moeten op de juiste plaats, want het is de 106 00:05:26,830 --> 00:05:30,210 enige element links, en dat is selectie sorteren. 107 00:05:30,210 --> 00:05:32,100 Laten we nu formaliseren ons algoritme met een aantal 108 00:05:32,100 --> 00:05:34,540 pseudocode. 109 00:05:34,540 --> 00:05:37,760 Op lijn een, kunnen we zien dat we nodig hebben om te integreren dan 110 00:05:37,760 --> 00:05:39,530 elk element van de lijst. 111 00:05:39,530 --> 00:05:42,150 Behalve het laatste element, omdat het een element 112 00:05:42,150 --> 00:05:44,230 lijst is al gesorteerd. 113 00:05:44,230 --> 00:05:48,100 Op lijn twee, beschouwen we het eerste element van het ongesorteerde 114 00:05:48,100 --> 00:05:51,080 deel van de lijst tot het minimum te zijn, zoals wij deden met onze 115 00:05:51,080 --> 00:05:53,750 Zo, dus we hebben iets te vergelijken. 116 00:05:53,750 --> 00:05:57,260 Lijn drie begint een tweede lus waarin we itereren over 117 00:05:57,260 --> 00:05:59,170 elk ongesorteerde element. 118 00:05:59,170 --> 00:06:02,150 We weten dat nadat ik iteraties, de gesorteerde gedeelte 119 00:06:02,150 --> 00:06:05,330 van onze lijst moet ik elementen in het sinds elke stap 120 00:06:05,330 --> 00:06:06,890 soorten een element. 121 00:06:06,890 --> 00:06:11,770 Dus de eerste ongesorteerde element moet in stand i plus 1. 122 00:06:11,770 --> 00:06:15,440 Op lijn vier, vergelijken we het huidige element tot het minimum 123 00:06:15,440 --> 00:06:17,750 element dat we tot nu toe hebben gezien. 124 00:06:17,750 --> 00:06:20,560 Als de huidige element kleiner is dan de minimum 125 00:06:20,560 --> 00:06:23,870 element, dan kunnen we denken aan de huidige element als de nieuwe 126 00:06:23,870 --> 00:06:26,250 minimum op lijn vijf. 127 00:06:26,250 --> 00:06:29,900 Tot slot, op de lijnen zes en zeven, wisselen we de minimale 128 00:06:29,900 --> 00:06:33,080 element met het eerste element ongesorteerde, waardoor 129 00:06:33,080 --> 00:06:36,990 toe te voegen aan de gesorteerde deel van de lijst. 130 00:06:36,990 --> 00:06:40,030 Zodra we een algoritme, een belangrijke vraag te stellen 131 00:06:40,030 --> 00:06:43,370 onszelf als programmeurs is hoe lang duurde dat duren? 132 00:06:43,370 --> 00:06:46,970 We zullen eerst de vraag stellen hoe lang duurt het voor deze 133 00:06:46,970 --> 00:06:50,070 algoritme om te draaien in het ergste geval? 134 00:06:50,070 --> 00:06:51,640 Recall wij vertegenwoordigen deze werking 135 00:06:51,640 --> 00:06:55,060 tijd met grote O notatie. 136 00:06:55,060 --> 00:06:58,650 Om het minimum ongesorteerde element bepalen we 137 00:06:58,650 --> 00:07:01,880 had in wezen elk element vergelijken de lijst 138 00:07:01,880 --> 00:07:04,040 elk ander element in de lijst. 139 00:07:04,040 --> 00:07:08,430 Intuïtief, dit klinkt als een O van n kwadraat werking. 140 00:07:08,430 --> 00:07:12,050 Kijkend naar onze pseudocode, hebben we ook een lus genest binnen 141 00:07:12,050 --> 00:07:14,420 een andere lus, die inderdaad klinkt als een O 142 00:07:14,420 --> 00:07:16,480 n kwadraat van werking. 143 00:07:16,480 --> 00:07:19,250 Vergeet echter niet dat we hebben geen behoefte om te kijken over de 144 00:07:19,250 --> 00:07:23,460 hele lijst bij het bepalen van de minimale ongesorteerde element? 145 00:07:23,460 --> 00:07:26,600 Zodra we wisten dat de 4 werd gesorteerd, bijvoorbeeld, hebben we niet 146 00:07:26,600 --> 00:07:28,170 nog een keer naar kijken. 147 00:07:28,170 --> 00:07:31,020 Dus betekent dit lager de looptijd? 148 00:07:31,020 --> 00:07:34,510 Voor onze lijst met lengte 6, moesten we om vijf te maken 149 00:07:34,510 --> 00:07:37,990 vergelijkingen voor het eerste element, vier vergelijkingen voor 150 00:07:37,990 --> 00:07:40,750 het tweede element, enzovoort. 151 00:07:40,750 --> 00:07:44,690 Dat betekent dat het totale aantal stappen is de som van 152 00:07:44,690 --> 00:07:49,160 de getallen van 1 tot de lengte van de lijst minus 1. 153 00:07:49,160 --> 00:07:51,005 We kunnen vertegenwoordigen dit met een sommatie. 154 00:07:57,980 --> 00:07:59,910 We zullen hier niet ingaan op sommaties. 155 00:07:59,910 --> 00:08:04,900 Maar het blijkt dat deze optelling is gelijk aan n maal 156 00:08:04,900 --> 00:08:07,540 n minus 1 over 2. 157 00:08:07,540 --> 00:08:14,220 Of gelijkwaardig, n kwadraat meer dan 2 min n meer dan 2. 158 00:08:14,220 --> 00:08:18,860 Wanneer we spreken over asymptotische runtime, deze n kwadraat term 159 00:08:18,860 --> 00:08:22,070 gaat dit n termijn domineren. 160 00:08:22,070 --> 00:08:27,850 Dus selection sort is O van n in het kwadraat. 161 00:08:27,850 --> 00:08:31,460 Bedenk dat in ons voorbeeld, nog steeds selectie sorteren die nodig zijn om 162 00:08:31,460 --> 00:08:33,850 controleren of een nummer dat al werd gesorteerd 163 00:08:33,850 --> 00:08:35,450 moest worden verplaatst. 164 00:08:35,450 --> 00:08:38,929 Dus dat betekent dat als we liepen selection sort over een reeds 165 00:08:38,929 --> 00:08:43,070 gesorteerde lijst, zou het nodig hetzelfde aantal stappen als het 166 00:08:43,070 --> 00:08:46,340 zou bij het berijden van een volledig gesorteerde lijst. 167 00:08:46,340 --> 00:08:51,470 Dus selectie sorteren heeft een best case prestaties van n kwadraat, 168 00:08:51,470 --> 00:08:56,820 die wij vertegenwoordigen met omega n kwadraat. 169 00:08:56,820 --> 00:08:58,600 En dat is het voor selectie sorteren. 170 00:08:58,600 --> 00:09:00,630 Slechts een van de vele algoritmen kunnen we 171 00:09:00,630 --> 00:09:02,390 gebruiken om een ​​lijst te sorteren. 172 00:09:02,390 --> 00:09:05,910 Mijn naam is Tommy, en dit is CS50.