[MUSIC PLAYING] DOUG LLOYD: Seçim sort bir deyil Siz gözləyə bilər kimi, alqoritm, elementlərin bir sıra növ. Və alqoritm geri bir addım-addım müəyyən edilir bir vəzifə doldurulması təlimatlar. 

Seçimi sort Əsas ideyası, bu kiçik çeşidlənməmiş element tapmaq və sorted siyahısı sonuna əlavə edin. Səmərəli, bu nə build edir bir sıralanır siyahısı bir-bir element. Pseudocode onu Breaking bu alqoritm bəyan edə bilər aşağıdakı qədər bu təkrar heç bir çeşidlənməmiş elementləri qalır. Çeşidlənməmiş vasitəsilə axtarış data kiçik dəyər tapmaq üçün, sonra ilə kiçik dəyər dəyişdirmək çeşidlənməmiş hissəsi ilk element. 

Bu, bu görüntüləmək kömək edə bilər Belə ki, bu nəzər salaq. Belə ki, bu, I yarışmaq, bir deyil çeşidlənməmiş array və mən var bütün olduğunu ifadə edən tərəfindən göstərilən elementləri qırmızı rəngli onlar hələ sıralanır deyil. Bu, bütün deyil serialın çeşidlənməmiş hissəsi. 

Belə ki, addımlar vasitəsilə getmək imkan seçim sort bu array sort. Belə ki, yenə, biz edəcəyimizi təkrar edirik heç bir çeşidlənməmiş elementləri qalır qədər. Biz vasitəsilə mý axtarış etdiyiniz data kiçik dəyər tapmaq üçün, və sonra ki, dəyəri dəyişdirmək çeşidlənməmiş hissəsi ilk element. 

Hal-hazırda, yenə bütün array çeşidlənməmiş hissəsidir. Qırmızı elementləri bütün çeşidlənməmiş var. Beləliklə, biz vasitəsilə axtarış və biz kiçik dəyər tapmaq. Biz başında Biz sonuna qədər getmək biz kiçik dəyər, bir tapa bilərsiniz. Belə ki, bir hissəsi biridir. Və sonra hissəsi iki, ilə ki, dəyəri dəyişdirmək çeşidlənməmiş hissəsi ilk element, və ya ilk qırmızı element. 

Bu halda ola bilər ki, beş, belə ki, biz bir və beş dəyişdirmək. Bunu zaman, biz vizual biz ki, görəcəksiniz kiçik qiymətli element köçürülüb serialın çox əvvəlinə. Səmərəli element çeşidlənməsi. 

Və belə ki, biz, həqiqətən, təsdiq edə bilər və dövlət var, çeşidlənir. Və belə ki, biz sıralanır hissəsi göstərir lazımdır bizim serialın, mavi boyayıcı. 

İndi biz yalnız yenidən prosesi təkrar edin. Biz çeşidlənməmiş hissəsi vasitəsilə axtarış array ən kiçik element tapmaq. Bu halda, iki deyil. 

Biz ilk ilə dəyişdirmək çeşidlənməmiş hissəsi element. Bu halda iki də olur çeşidlənməmiş hissəsi ilk element. Belə ki, biz özü ilə iki dəyişdirmək, həqiqətən yalnız iki yaradır Bu və bu sıralanır harada. Davam, biz vasitəsilə axtarış kiçik element tapmaq üçün. Bu üç var. Biz ilk ilə dəyişdirmək Beş edir element. İndi üç çeşidlənir. 

Biz yenə vasitəsilə axtarış və biz kiçik element dörd tapa bilərsiniz. Biz ilk element ilə dəyişdirmək çeşidlənməmiş hissəsi, indi dörd çeşidlənir. 

Biz beş olduğunu tapmaq kiçik element. Biz ilk ilə dəyişdirmək çeşidlənməmiş hissəsi element. İndi beş çeşidlənir. 

Və sonra nəhayət, bizim çeşidlənməmiş hissəsi ibarətdir yalnız bir element, belə ki, biz vasitəsilə axtarış və biz altı olduğunu tapmaq kiçik və əslində, yalnız element. Və sonra biz bu çeşidlənir ki, olar. İndi biz array geçtiğinizi tamamilə çeşidlənməmiş olan qırmızı, tamamilə sıralanır üçün mavi, seçki növ istifadə. 

Belə ki, ən pis ssenari burada nə var? Yaxşı mütləq pis halda, biz artıq baxmaq serialın elementləri bütün kiçik çeşidlənməmiş element tapmaq, və biz təkrar var bu proses n dəfə. Serialın hər bir element üçün Once biz yalnız, çünki bu alqoritm, vaxt sort bir element. 

Ən yaxşı ssenari nədir? Yaxşı doğru, eyni var? Biz, həqiqətən, hələ gezinmek üçün var serialın hər bir element üçün, bu olduğunu təsdiq etmək əslində, kiçik element. 

Belə ki, ən pis halda uzunluğu, biz bir proses n dəfə təkrar etmək lazımdır, n elementlərin hər biri üçün bir dəfə. Və ən yaxşı halda, biz eyni var. 

Belə ki, geri düşüncə bizim hesablama mürəkkəblik qutusu, nə düşünürsünüz pis seçim sort üçün işi uzunluğu? Nə düşünürsünüz ən yaxşı seçim sort üçün işi uzunluğu? 

N kvadrat siz Big O tahmin mi, Böyük Omega n kvadrat? Siz doğru olarıq. Həmin, əslində, ən pis halda və ən yaxşı halda run seçim sort üçün dəfə. 

Mən Doug Lloyd edirəm. Bu CS50 edir.