[Powered by Google Translate] TOMMY: seçim sort bir göz, bir alqoritm edək nömrələrin siyahısına alaraq və onları çeşidlənməsi üçün. Alqoritmi, xatırlayıram, sadəcə bir addım-addım bir vəzifə yerinə qaydası. Seleksiya sort əsas ideyası bölmək üçün iki hissəni bizim siyahısı - bir sıralanır hissəsi və çeşidlənməmiş hissəsi. Alqoritmi hər addım da, bir sıra hərəkət edir nəticədə qədər sıralanır hissəsini çeşidlənməmiş hissə bütün siyahısını çeşidlənir. Belə ki, burada altı ədəd bir siyahısı - 23, 42, 4, 16, 8, 15. Hal-hazırda bütün siyahısı çeşidlənməmiş hesab olunur. 16 kimi bir sıra artıq doğru ola bilər baxmayaraq, yeri, bizim alqoritm qədər ki, bilmədən heç bir yol var bütün siyahısını çeşidlənir. Biz sort qədər biz çeşidlənməmiş üçün hər sayı hesab edəcəyik bu özümüzü. Biz siyahısı üçün artan olmaq istəyirəm bilirik. Belə ki, biz siyahısını sıralanır hissəsi qurmaq lazımdır soldan sağa, ən böyük üçün kiçik. Bunu etmək üçün, biz minimum çeşidlənməmiş element tapmaq lazımdır və sıralanır hissəsinin sonunda qoyun. Bu siyahıda sıralanır deyil bəri, bunu yeganə yolu üçün xatırlayaraq, bu çeşidlənməmiş hissəsi hər element baxmaq element aşağı və müqayisə edir ki, hər bir element. Beləliklə, biz ilk 23 baxmaq lazımdır. Bu gördüm ilk element, belə ki, biz yadda olacaq minimum kimi. Sonrakı biz 42 baxmaq lazımdır. 42 23 böyükdür, belə ki, 23 hələ minimum edir. Sonrakı 23-dən az olan 4, belə ki, biz 4 xatırlamaq lazımdır yeni minimum kimi. Növbəti belə 4, 4-dən böyük olan 16 hələ minimum edir. 8 4 daha böyük, 15 4-dən böyük, 4 olmalıdır belə kiçik çeşidlənməmiş element. Belə olsa da insanlar kimi biz dərhal 4 olduğunu görə bilərsiniz minimum element, bizim alqoritmi baxmaq lazımdır biz 4 gördük hətta sonra hər çeşidlənməmiş element, - deyə minimum element. Belə ki, indi biz minimum element, 4 gördük ki, biz lazımdır siyahının ən sıralanır hissəsi onu hərəkət etmək. Bu ilk addımdır, bu, biz azı 4 qoymaq istəyirik deməkdir siyahısının başında. Hal-hazırda 23 belə, siyahının başında deyil nin 4 və 23 dəyişdirmək imkan verir. Belə ki, indi bizim siyahısı kimi görünür. Çünki biz, 4 yekun yeri olmalıdır bilirik ki, əvvəlində kiçik element və element həm siyahısı. Biz bir daha hərəkət etmək lazım deyil ki, bu o deməkdir ki. Beləliklə də başqa bir element əlavə etmək üçün bu prosesi təkrar edək siyahısı sıralanır hissəsi. Bu, çünki biz 4 baxmaq lazım deyil bilirik ki, artıq sıralanır. Belə ki, biz kimi yadda lazımdır ki, 42-də başlaya bilər minimum element. Belə ki, növbəti biz 42-dən az olan 23 baxmaq, belə ki, lazımdır, biz 23 yeni minimum xatırlayıram. Sonrakı biz az 23 olan 16 görmək 16 yeni minimum edir. İndi biz belə az 16 olan 8 baxmaq 8 yeni minimum edir. Və nəhayət 8 az 15, belə ki, biz 8 minimum bilirik ki, çeşidlənməmiş element. Belə ki, biz sıralanır 8 əlavə etməlidir deməkdir siyahısına hissəsi. Hal-hazırda 4-yalnız sıralanır element, belə ki, biz yer istəyirik 4 üçün 8 Növbəti. 42 ildən də çeşidlənməmiş hissəsi ilk element siyahısı, biz 42 və 8 dəyişdirmək lazımdır. Belə ki, indi bizim siyahısı kimi görünür. 4 və 8 siyahısı sıralanır hissəsi təmsil və qalan ədəd çeşidlənməmiş təmsil siyahısına hissəsi. Belə nin başqa iteration davam edək. Biz baxmaq ehtiyac yoxdur çünki, 23 bu dəfə başlamaq 4 və artıq 8 onlar var, çünki artıq sıralanır edilmişdir. 16-dən az 23, belə ki, biz yadda olacaq Yeni minimum 16. 15 olmalıdır, belə ki, 16-dən az 42, lakin 15-dən az 16 minimum çeşidlənməmiş element. Belə ki, indi biz 15 və 23 dəyişdirmək istədiyiniz Bu siyahı verir. Siyahı üzrə sıralanır hissəsi 4, 8 və 15 ibarətdir və Bu elementlərin hələ çeşidlənməmiş olunur. Amma bu yalnız belə olur ki, növbəti çeşidlənməmiş element, 16, artıq çeşidlənir. Lakin, bizim alqoritmi üçün heç bir yol var ki, 16 artıq doğru yeri var, belə ki, biz hələ də ehtiyac eyni prosesi təkrar. Belə ki, biz 16-dən az 42 olduğunu görmək, və 16-dən az 23 16 minimum element olmalıdır. Bu özü bu element dəyişdirmək mümkün deyil, biz belə sadəcə bu yeri tərk edir. Belə ki, bizim alqoritmi daha bir keçid lazımdır. 42 23 böyükdür, belə ki, 23 olmalıdır minimum çeşidlənməmiş element. Sonra biz son ilə qədər, 23 və 42 dəyişdirmək sıralanır siyahısı - 4, 8, 15, 16, 23, 42. Biz bu var-ci ildən 42 düzgün yer olmalıdır bilirik yalnız element tərk, və seleksiya sort var. Gəlin indi bəzi bizim alqoritm rəsmiləşdirilməsi pseudocode. Line biri, biz artıq inteqrasiya etmək lazımdır ki, edə bilərsiniz siyahısı hər element. Son element istisna olmaqla, ildən 1 element siyahısı artıq çeşidlənir. Line iki, biz çeşidlənməmiş ilk element hesab bizim ilə kimi siyahısına hissəsi, minimum olması Məsələn, biz müqayisə üçün bir şey var. Line üç biz artıq təkrarlamaq olan ikinci bir loop başlayır hər çeşidlənməmiş element. Biz bilirik ki, i tekrarlamalar sonra sıralanır hissə bizim siyahıda hər bir addım, çünki i elementləri olmalıdır növ bir element. Belə ki, ilk çeşidlənməmiş element mövqe i müsbət 1 olmalıdır. Line dörd, biz minimum cari element et biz belə uzaq gördüm ki element. Cari element minimum daha kiçik deyil element, sonra biz yeni kimi cari element xatırlayıram line beş üzrə minimum. Nəhayət, xətləri altı və yeddi haqqında, biz minimum dəyişdirmək bununla da ilk çeşidlənməmiş element element, siyahının ən sıralanır hissəsi üçün əlavə. Biz bir alqoritm var sonra, mühüm sual özümüzü proqramçılar kimi necə uzun idi olunur? Biz ilk sual lazımdır necə uzun bu qəbul etmir alqoritm ən pis halda çalışır? Biz bu davam təmsil Xatırladaq böyük O notation zaman. Minimum çeşidlənməmiş element müəyyən etmək üçün, mahiyyətcə üçün siyahıdan hər element müqayisə idi siyahıda hər element. Daxilən, n kvadrat əməliyyat bir O kimi bu səslər. Bizim pseudocode baxanda, biz də içində iç içə bir loop var bir O kimi həqiqətən səslənir başqa bir loop, n kvadrat əməliyyat. Ancaq biz artıq baxmaq lazım deyil ki, unutmayın minimum çeşidlənməmiş element müəyyən edərkən bütün siyahısını? Biz 4 sıralanır bilirdi ki sonra, misal üçün, biz etmədi yenidən baxmaq lazımdır. Bu çalışan zaman Belə ki, aşağı edir? Uzunluğu 6 listemize, biz beş etmək üçün lazım ilk element üçün müqayisə üçün dörd müqayisə İkinci element, və s. Bu addımların sayı cəmi o deməkdir ki, 1-dən siyahı minus 1 uzunluğu integers. Biz bir toplama ilə təmsil edə bilər. Biz burada summations daxil deyil. Lakin bu toplama n dəfə bərabər çıxır ki, n minus 2-dən 1. Və ya equivalently, n 2 üzərində mənfi N 2 üzərində kare. Asimptotik iş haqqında danışarkən, bu n kvadrat müddətli bu n müddət hakim gedir. Belə ki, seçim sort n kvadrat Ey edir. Bizim misalda, seçim sort hələ lazım Xatırladaq ki, yoxlamaq əgər artıq sıralanır ki, bir sıra köçürülüb lazımdır. Belə ki, deməkdir ki, biz artıq seçim sort qaçdı əgər siyahısı sorted, bu kimi addımlar eyni sayda tələb tamamilə çeşidlənməmiş siyahı üzərində çalışan zaman olacaq. Belə ki, seçim növ kvadrat n bir yaxşı halda performans olan biz omega n kvadrat ilə təmsil edir. Və seçim sort üçün var. Biz bir çox alqoritmlərin yalnız bir siyahısını düzmək üçün istifadə edin. My name Tommy və bu cs50 edir.