1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: seçim sort bir göz, bir alqoritm edək 2 00:00:09,980 --> 00:00:12,800 nömrələrin siyahısına alaraq və onları çeşidlənməsi üçün. 3 00:00:12,800 --> 00:00:15,750 Alqoritmi, xatırlayıram, sadəcə bir addım-addım 4 00:00:15,750 --> 00:00:18,370 bir vəzifə yerinə qaydası. 5 00:00:18,370 --> 00:00:21,470 Seleksiya sort əsas ideyası bölmək üçün 6 00:00:21,470 --> 00:00:23,390 iki hissəni bizim siyahısı - 7 00:00:23,390 --> 00:00:26,810 bir sıralanır hissəsi və çeşidlənməmiş hissəsi. 8 00:00:26,810 --> 00:00:30,200 Alqoritmi hər addım da, bir sıra hərəkət edir 9 00:00:30,200 --> 00:00:33,800 nəticədə qədər sıralanır hissəsini çeşidlənməmiş hissə 10 00:00:33,800 --> 00:00:35,880 bütün siyahısını çeşidlənir. 11 00:00:35,880 --> 00:00:38,510 Belə ki, burada altı ədəd bir siyahısı - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, 15. 13 00:00:44,010 --> 00:00:47,680 Hal-hazırda bütün siyahısı çeşidlənməmiş hesab olunur. 14 00:00:47,680 --> 00:00:51,770 16 kimi bir sıra artıq doğru ola bilər baxmayaraq, 15 00:00:51,770 --> 00:00:56,040 yeri, bizim alqoritm qədər ki, bilmədən heç bir yol var 16 00:00:56,040 --> 00:00:57,980 bütün siyahısını çeşidlənir. 17 00:00:57,980 --> 00:01:01,355 Biz sort qədər biz çeşidlənməmiş üçün hər sayı hesab edəcəyik 18 00:01:01,355 --> 00:01:03,800 bu özümüzü. 19 00:01:03,800 --> 00:01:06,890 Biz siyahısı üçün artan olmaq istəyirəm bilirik. 20 00:01:06,890 --> 00:01:10,200 Belə ki, biz siyahısını sıralanır hissəsi qurmaq lazımdır 21 00:01:10,200 --> 00:01:13,280 soldan sağa, ən böyük üçün kiçik. 22 00:01:13,280 --> 00:01:17,970 Bunu etmək üçün, biz minimum çeşidlənməmiş element tapmaq lazımdır 23 00:01:17,970 --> 00:01:21,350 və sıralanır hissəsinin sonunda qoyun. 24 00:01:21,350 --> 00:01:25,370 Bu siyahıda sıralanır deyil bəri, bunu yeganə yolu üçün 25 00:01:25,370 --> 00:01:29,330 xatırlayaraq, bu çeşidlənməmiş hissəsi hər element baxmaq 26 00:01:29,330 --> 00:01:32,010 element aşağı və müqayisə edir 27 00:01:32,010 --> 00:01:33,770 ki, hər bir element. 28 00:01:33,770 --> 00:01:36,150 Beləliklə, biz ilk 23 baxmaq lazımdır. 29 00:01:36,150 --> 00:01:38,650 Bu gördüm ilk element, belə ki, biz yadda olacaq 30 00:01:38,650 --> 00:01:40,050 minimum kimi. 31 00:01:40,050 --> 00:01:42,320 Sonrakı biz 42 baxmaq lazımdır. 32 00:01:42,320 --> 00:01:46,720 42 23 böyükdür, belə ki, 23 hələ minimum edir. 33 00:01:46,720 --> 00:01:51,210 Sonrakı 23-dən az olan 4, belə ki, biz 4 xatırlamaq lazımdır 34 00:01:51,210 --> 00:01:52,880 yeni minimum kimi. 35 00:01:52,880 --> 00:01:56,380 Növbəti belə 4, 4-dən böyük olan 16 36 00:01:56,380 --> 00:01:57,980 hələ minimum edir. 37 00:01:57,980 --> 00:02:03,670 8 4 daha böyük, 15 4-dən böyük, 4 olmalıdır belə 38 00:02:03,670 --> 00:02:05,980 kiçik çeşidlənməmiş element. 39 00:02:05,980 --> 00:02:09,350 Belə olsa da insanlar kimi biz dərhal 4 olduğunu görə bilərsiniz 40 00:02:09,350 --> 00:02:12,300 minimum element, bizim alqoritmi baxmaq lazımdır 41 00:02:12,300 --> 00:02:15,710 biz 4 gördük hətta sonra hər çeşidlənməmiş element, - deyə 42 00:02:15,710 --> 00:02:16,860 minimum element. 43 00:02:16,860 --> 00:02:19,900 Belə ki, indi biz minimum element, 4 gördük ki, biz lazımdır 44 00:02:19,900 --> 00:02:23,410 siyahının ən sıralanır hissəsi onu hərəkət etmək. 45 00:02:23,410 --> 00:02:27,320 Bu ilk addımdır, bu, biz azı 4 qoymaq istəyirik deməkdir 46 00:02:27,320 --> 00:02:29,680 siyahısının başında. 47 00:02:29,680 --> 00:02:33,040 Hal-hazırda 23 belə, siyahının başında deyil 48 00:02:33,040 --> 00:02:36,080 nin 4 və 23 dəyişdirmək imkan verir. 49 00:02:36,080 --> 00:02:38,870 Belə ki, indi bizim siyahısı kimi görünür. 50 00:02:38,870 --> 00:02:42,710 Çünki biz, 4 yekun yeri olmalıdır bilirik ki, 51 00:02:42,710 --> 00:02:45,890 əvvəlində kiçik element və element həm 52 00:02:45,890 --> 00:02:46,960 siyahısı. 53 00:02:46,960 --> 00:02:50,650 Biz bir daha hərəkət etmək lazım deyil ki, bu o deməkdir ki. 54 00:02:50,650 --> 00:02:53,910 Beləliklə də başqa bir element əlavə etmək üçün bu prosesi təkrar edək 55 00:02:53,910 --> 00:02:55,910 siyahısı sıralanır hissəsi. 56 00:02:55,910 --> 00:02:58,950 Bu, çünki biz 4 baxmaq lazım deyil bilirik ki, 57 00:02:58,950 --> 00:03:00,000 artıq sıralanır. 58 00:03:00,000 --> 00:03:03,540 Belə ki, biz kimi yadda lazımdır ki, 42-də başlaya bilər 59 00:03:03,540 --> 00:03:05,290 minimum element. 60 00:03:05,290 --> 00:03:08,700 Belə ki, növbəti biz 42-dən az olan 23 baxmaq, belə ki, lazımdır, biz 61 00:03:08,700 --> 00:03:11,620 23 yeni minimum xatırlayıram. 62 00:03:11,620 --> 00:03:14,870 Sonrakı biz az 23 olan 16 görmək 63 00:03:14,870 --> 00:03:16,800 16 yeni minimum edir. 64 00:03:16,800 --> 00:03:19,720 İndi biz belə az 16 olan 8 baxmaq 65 00:03:19,720 --> 00:03:21,130 8 yeni minimum edir. 66 00:03:21,130 --> 00:03:25,900 Və nəhayət 8 az 15, belə ki, biz 8 minimum bilirik ki, 67 00:03:25,900 --> 00:03:27,780 çeşidlənməmiş element. 68 00:03:27,780 --> 00:03:30,660 Belə ki, biz sıralanır 8 əlavə etməlidir deməkdir 69 00:03:30,660 --> 00:03:32,450 siyahısına hissəsi. 70 00:03:32,450 --> 00:03:35,990 Hal-hazırda 4-yalnız sıralanır element, belə ki, biz yer istəyirik 71 00:03:35,990 --> 00:03:38,410 4 üçün 8 Növbəti. 72 00:03:38,410 --> 00:03:41,920 42 ildən də çeşidlənməmiş hissəsi ilk element 73 00:03:41,920 --> 00:03:47,260 siyahısı, biz 42 və 8 dəyişdirmək lazımdır. 74 00:03:47,260 --> 00:03:49,680 Belə ki, indi bizim siyahısı kimi görünür. 75 00:03:49,680 --> 00:03:53,830 4 və 8 siyahısı sıralanır hissəsi təmsil və 76 00:03:53,830 --> 00:03:56,440 qalan ədəd çeşidlənməmiş təmsil 77 00:03:56,440 --> 00:03:58,260 siyahısına hissəsi. 78 00:03:58,260 --> 00:04:00,630 Belə nin başqa iteration davam edək. 79 00:04:00,630 --> 00:04:03,850 Biz baxmaq ehtiyac yoxdur çünki, 23 bu dəfə başlamaq 80 00:04:03,850 --> 00:04:05,770 4 və artıq 8 onlar var, çünki 81 00:04:05,770 --> 00:04:07,660 artıq sıralanır edilmişdir. 82 00:04:07,660 --> 00:04:10,270 16-dən az 23, belə ki, biz yadda olacaq 83 00:04:10,270 --> 00:04:12,070 Yeni minimum 16. 84 00:04:12,070 --> 00:04:18,149 15 olmalıdır, belə ki, 16-dən az 42, lakin 15-dən az 16 85 00:04:18,149 --> 00:04:20,480 minimum çeşidlənməmiş element. 86 00:04:20,480 --> 00:04:24,580 Belə ki, indi biz 15 və 23 dəyişdirmək istədiyiniz 87 00:04:24,580 --> 00:04:26,310 Bu siyahı verir. 88 00:04:26,310 --> 00:04:30,500 Siyahı üzrə sıralanır hissəsi 4, 8 və 15 ibarətdir və 89 00:04:30,500 --> 00:04:33,210 Bu elementlərin hələ çeşidlənməmiş olunur. 90 00:04:33,210 --> 00:04:36,900 Amma bu yalnız belə olur ki, növbəti çeşidlənməmiş element, 16, 91 00:04:36,900 --> 00:04:38,480 artıq çeşidlənir. 92 00:04:38,480 --> 00:04:42,060 Lakin, bizim alqoritmi üçün heç bir yol var ki, 16 93 00:04:42,060 --> 00:04:45,230 artıq doğru yeri var, belə ki, biz hələ də ehtiyac 94 00:04:45,230 --> 00:04:47,870 eyni prosesi təkrar. 95 00:04:47,870 --> 00:04:53,750 Belə ki, biz 16-dən az 42 olduğunu görmək, və 16-dən az 23 96 00:04:53,750 --> 00:04:56,230 16 minimum element olmalıdır. 97 00:04:56,230 --> 00:04:59,010 Bu özü bu element dəyişdirmək mümkün deyil, biz belə 98 00:04:59,010 --> 00:05:01,780 sadəcə bu yeri tərk edir. 99 00:05:01,780 --> 00:05:04,660 Belə ki, bizim alqoritmi daha bir keçid lazımdır. 100 00:05:04,660 --> 00:05:09,370 42 23 böyükdür, belə ki, 23 olmalıdır 101 00:05:09,370 --> 00:05:10,970 minimum çeşidlənməmiş element. 102 00:05:10,970 --> 00:05:17,410 Sonra biz son ilə qədər, 23 və 42 dəyişdirmək 103 00:05:17,410 --> 00:05:18,530 sıralanır siyahısı - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Biz bu var-ci ildən 42 düzgün yer olmalıdır bilirik 106 00:05:26,830 --> 00:05:30,210 yalnız element tərk, və seleksiya sort var. 107 00:05:30,210 --> 00:05:32,100 Gəlin indi bəzi bizim alqoritm rəsmiləşdirilməsi 108 00:05:32,100 --> 00:05:34,540 pseudocode. 109 00:05:34,540 --> 00:05:37,760 Line biri, biz artıq inteqrasiya etmək lazımdır ki, edə bilərsiniz 110 00:05:37,760 --> 00:05:39,530 siyahısı hər element. 111 00:05:39,530 --> 00:05:42,150 Son element istisna olmaqla, ildən 1 element 112 00:05:42,150 --> 00:05:44,230 siyahısı artıq çeşidlənir. 113 00:05:44,230 --> 00:05:48,100 Line iki, biz çeşidlənməmiş ilk element hesab 114 00:05:48,100 --> 00:05:51,080 bizim ilə kimi siyahısına hissəsi, minimum olması 115 00:05:51,080 --> 00:05:53,750 Məsələn, biz müqayisə üçün bir şey var. 116 00:05:53,750 --> 00:05:57,260 Line üç biz artıq təkrarlamaq olan ikinci bir loop başlayır 117 00:05:57,260 --> 00:05:59,170 hər çeşidlənməmiş element. 118 00:05:59,170 --> 00:06:02,150 Biz bilirik ki, i tekrarlamalar sonra sıralanır hissə 119 00:06:02,150 --> 00:06:05,330 bizim siyahıda hər bir addım, çünki i elementləri olmalıdır 120 00:06:05,330 --> 00:06:06,890 növ bir element. 121 00:06:06,890 --> 00:06:11,770 Belə ki, ilk çeşidlənməmiş element mövqe i müsbət 1 olmalıdır. 122 00:06:11,770 --> 00:06:15,440 Line dörd, biz minimum cari element et 123 00:06:15,440 --> 00:06:17,750 biz belə uzaq gördüm ki element. 124 00:06:17,750 --> 00:06:20,560 Cari element minimum daha kiçik deyil 125 00:06:20,560 --> 00:06:23,870 element, sonra biz yeni kimi cari element xatırlayıram 126 00:06:23,870 --> 00:06:26,250 line beş üzrə minimum. 127 00:06:26,250 --> 00:06:29,900 Nəhayət, xətləri altı və yeddi haqqında, biz minimum dəyişdirmək 128 00:06:29,900 --> 00:06:33,080 bununla da ilk çeşidlənməmiş element element, 129 00:06:33,080 --> 00:06:36,990 siyahının ən sıralanır hissəsi üçün əlavə. 130 00:06:36,990 --> 00:06:40,030 Biz bir alqoritm var sonra, mühüm sual 131 00:06:40,030 --> 00:06:43,370 özümüzü proqramçılar kimi necə uzun idi olunur? 132 00:06:43,370 --> 00:06:46,970 Biz ilk sual lazımdır necə uzun bu qəbul etmir 133 00:06:46,970 --> 00:06:50,070 alqoritm ən pis halda çalışır? 134 00:06:50,070 --> 00:06:51,640 Biz bu davam təmsil Xatırladaq 135 00:06:51,640 --> 00:06:55,060 böyük O notation zaman. 136 00:06:55,060 --> 00:06:58,650 Minimum çeşidlənməmiş element müəyyən etmək üçün, 137 00:06:58,650 --> 00:07:01,880 mahiyyətcə üçün siyahıdan hər element müqayisə idi 138 00:07:01,880 --> 00:07:04,040 siyahıda hər element. 139 00:07:04,040 --> 00:07:08,430 Daxilən, n kvadrat əməliyyat bir O kimi bu səslər. 140 00:07:08,430 --> 00:07:12,050 Bizim pseudocode baxanda, biz də içində iç içə bir loop var 141 00:07:12,050 --> 00:07:14,420 bir O kimi həqiqətən səslənir başqa bir loop, 142 00:07:14,420 --> 00:07:16,480 n kvadrat əməliyyat. 143 00:07:16,480 --> 00:07:19,250 Ancaq biz artıq baxmaq lazım deyil ki, unutmayın 144 00:07:19,250 --> 00:07:23,460 minimum çeşidlənməmiş element müəyyən edərkən bütün siyahısını? 145 00:07:23,460 --> 00:07:26,600 Biz 4 sıralanır bilirdi ki sonra, misal üçün, biz etmədi 146 00:07:26,600 --> 00:07:28,170 yenidən baxmaq lazımdır. 147 00:07:28,170 --> 00:07:31,020 Bu çalışan zaman Belə ki, aşağı edir? 148 00:07:31,020 --> 00:07:34,510 Uzunluğu 6 listemize, biz beş etmək üçün lazım 149 00:07:34,510 --> 00:07:37,990 ilk element üçün müqayisə üçün dörd müqayisə 150 00:07:37,990 --> 00:07:40,750 İkinci element, və s. 151 00:07:40,750 --> 00:07:44,690 Bu addımların sayı cəmi o deməkdir ki, 152 00:07:44,690 --> 00:07:49,160 1-dən siyahı minus 1 uzunluğu integers. 153 00:07:49,160 --> 00:07:51,005 Biz bir toplama ilə təmsil edə bilər. 154 00:07:57,980 --> 00:07:59,910 Biz burada summations daxil deyil. 155 00:07:59,910 --> 00:08:04,900 Lakin bu toplama n dəfə bərabər çıxır ki, 156 00:08:04,900 --> 00:08:07,540 n minus 2-dən 1. 157 00:08:07,540 --> 00:08:14,220 Və ya equivalently, n 2 üzərində mənfi N 2 üzərində kare. 158 00:08:14,220 --> 00:08:18,860 Asimptotik iş haqqında danışarkən, bu n kvadrat müddətli 159 00:08:18,860 --> 00:08:22,070 bu n müddət hakim gedir. 160 00:08:22,070 --> 00:08:27,850 Belə ki, seçim sort n kvadrat Ey edir. 161 00:08:27,850 --> 00:08:31,460 Bizim misalda, seçim sort hələ lazım Xatırladaq ki, 162 00:08:31,460 --> 00:08:33,850 yoxlamaq əgər artıq sıralanır ki, bir sıra 163 00:08:33,850 --> 00:08:35,450 köçürülüb lazımdır. 164 00:08:35,450 --> 00:08:38,929 Belə ki, deməkdir ki, biz artıq seçim sort qaçdı əgər 165 00:08:38,929 --> 00:08:43,070 siyahısı sorted, bu kimi addımlar eyni sayda tələb 166 00:08:43,070 --> 00:08:46,340 tamamilə çeşidlənməmiş siyahı üzərində çalışan zaman olacaq. 167 00:08:46,340 --> 00:08:51,470 Belə ki, seçim növ kvadrat n bir yaxşı halda performans 168 00:08:51,470 --> 00:08:56,820 olan biz omega n kvadrat ilə təmsil edir. 169 00:08:56,820 --> 00:08:58,600 Və seçim sort üçün var. 170 00:08:58,600 --> 00:09:00,630 Biz bir çox alqoritmlərin yalnız bir 171 00:09:00,630 --> 00:09:02,390 siyahısını düzmək üçün istifadə edin. 172 00:09:02,390 --> 00:09:05,910 My name Tommy və bu cs50 edir.