[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.