[MUSIC PLAYING] 

DOUG LLOYD: Belə ki, durub sırala başqa alqoritm biz bir sıra düzmək üçün istifadə edə bilərsiniz. Bu alqoritm arxasında ideyası Sizin sorted array qurmaq üçün yerdə, həyata elementləri dəyişkən Siz getmək kimi yol otaq etmək. Bu az fərqli seleksiya sort və ya bubble sort, məsələn, harada biz yerlərdə düzəliş edirik, biz svop edirik. 

Bu halda biz həqiqətən istəyirik bunu sürüşmə elementləri üzərində yol. Bu alqoritm Necə pseudocode işləmək? Yaxşı, yalnız özbaşına deyirlər ki, edək serialın ilk element çeşidlənir. Biz yerdə tikinti edirik. 

Biz mý bir-bir element getmək etdiyiniz və qurmaq, və ilk şey görürük bir element array edir. Və müəyyən, bir element array çeşidlənir. 

Sonra biz bu prosesi demək lazımdır until-- biz aşağıdakı prosesi demək lazımdır elementləri bütün ayrılır qədər. Növbəti çeşidlənməmiş element baxmaq və sıralanır hissəsi daxil edin, tələb olunan sayı dəyişkən tərəfindən yol elementləri. İnşallah bu vizual Siz var tam olaraq nə görmək kömək edəcək durub sırala ilə gedir. 

Belə ki, yenə, burada var Bütün çeşidlənməmiş array, elementləri bütün qırmızı göstərilən. Və əməl edək Bizim pseudocode addımlar. Biz nə ilk şey, biz zəng serialın ilk element sıralanır. Beləliklə, biz yalnız mý demək istəyirik beş, indi sıralanır edirik. 

Sonra biz növbəti baxmaq serialın çeşidlənməmiş element və biz bu daxil etmək istəyirəm sıralanır hissəsi daxil, elementləri üzərində dəyişkən tərəfindən. Belə ki, iki növbəti çeşidlənməmiş edir serialın element. Aydındır ki, bu əvvəl məxsusdur beş, belə ki, biz edəcəyimizi nə edirik sort bir ikinci kənara iki keçirəcək ki, artıq beş keçmək, sonra iki daxil Beş əvvəl getmək lazımdır. İndi biz iki çeşidlənir demək olar ki. 

Gördüyünüz kimi, belə ki, biz indiyə qədər yalnız var serialın iki elementləri baxdı. Biz baxdı yoxdur bütün istirahət, lakin biz var bu iki elementləri sıralaması oldu dəyişkən mexanizminin yol. 

Yəni biz yenidən prosesi təkrar edin. Növbəti çeşidlənməmiş baxın element ki, biri. , Bir ikinci kənara keçirilməsi edək artıq hər şey keçmək, və bir qoymaq harada getmək lazımdır. 

Yenə də, biz yalnız heç etdik Bir, iki, və beş baxdı. Biz gələn başqa nə bilmirəm, lakin biz bu üç elementləri sıralaması etdik. 

Next çeşidlənməmiş element üç, belə ki, biz kənara müəyyən edəcəyik. Biz artıq keçmək lazımdır nə biz ki, bu dəfə lazımdır Əvvəlki kimi hər şey deyil iki halda, yalnız beş var. Və sonra biz üç qalmaq lazımdır, iki və beş arasında. 

Six çeşidlənməmiş növbəti array element. Və əslində altı, belə ki, beş daha böyükdür Biz hətta hər hansı bir dəyişdirmə etmək lazım deyil. Biz yalnız sağ altı tack bilər sıralanır hissəsinin sonu. 

Nəhayət, dörd son çeşidlənməmiş element. Beləliklə, biz kənara qurmaq lazımdır, üzərində keçmək elementləri biz artıq keçmək lazımdır Bu aid olduğu və sonra dörd qoydu. İndi baxmaq biz sort var bütün elementləri. Durub ilə qeyd sort, biz yox idi geri və irəli array arasında getmək üçün. Biz yalnız array arasında getdi bir dəfə, və biz hər şeyi keçdikdə biz artıq üçün, rast istədiyiniz yeni elementlər üçün otaq etmək. 

Belə ki, nə ən pis halda var durub növ ilə ssenari? Ən pis halda, array əks qaydada deyil. Siz n elementlərin hər keçmək n vəzifələrdə qədər, hər bir zaman biz bir durub olun. Bu dəyişkən bir çox var. 

Ən yaxşı halda, array mükəmməl çeşidlənir. Və sort nə kimi Məsələn beş və altı ilə, biz yalnız tack biləcəyi Hər hansı bir dəyişkən olmadan, biz mahiyyətcə bunu görürük. 

Siz təsəvvür əgər bizim array, altı ilə bir idi biz ilə başlamaq istədiyiniz bir elan çeşidlənir. İki biz yalnız bilərsiniz sonra gəlir bir və iki sıralanır, həmçinin OK, deyirlər. Üç OK, belə ki, sonra iki gəlir, bir və iki və üç sıralanır. 

Biz istəyirik, hər hansı bir svopları edilməsi deyilik bu ixtiyari xətt hərəkət biz getmək kimi arasında sıralanır və çeşidlənməmiş. Kimi səmərəli biz nümunə kimi, biz davam kimi, mavi elementləri dönüş. Belə ki, ən pis halda uzunluğu sonra nə var? Biz hər keçmək varsa, saxla n elementləri bəlkə n vəzifələrdə, ümid edirəm ki, verir ən pis halda ki, bir fikir uzunluğu n Big O kvadrat edir. 

Array mükəmməl olarsa sıralaması bütün biz nə üçün hər bir element baxmaq bir dəfə, sonra biz tamamlayın. Belə ki, ən yaxşı halda, bu n omega var. 

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