[Powered by Google Translate] [Insertion Sort] [Tommy MacWilliam] [Harvard Universiteti] [Bu CS50.TV edir] Nin durub sırala nəzər, nömrə bir siyahısı alaraq və onları çeşidlənməsi üçün alqoritm edək. Alqoritmi, xatırlayıram, sadəcə bir vəzifə yerinə bir addım-addım prosedurdur. Durub sırala əsas ideyası, iki hissəni bizim siyahı bölmək üçün bir sıralanır hissəsi və çeşidlənməmiş hissəsi. 

Alqoritmi hər addım da, bir sıra köçürülüb bu çeşidlənməmiş hissəsi olan sıralanır hissəsini nəhayət qədər tam siyahısı çeşidlənir. 23, 42, 4, 16, 8, 15 - Burada altı çeşidlənməmiş nömrələri siyahısı. Bu nömrələri üçün artan bütün deyil olduğundan, onlar çeşidlənməmiş edirik. Biz hələ çeşidlənməsi açılmış deyil ildən, biz bütün altı elementləri bizim çeşidlənməmiş hissəsi hesab edəcəyik. 

Sonra biz çeşidlənməsi başlamaq, bu solunda Bu sıralanır nömrələri qoymaq lazımdır. Belə ki, 23 bizim siyahıda ilk element ilə başlamaq imkan verir. Biz, hələ bizim sıralanır hissəsi hər hansı elementləri yoxdur belə-nin sadəcə bizim sıralanır hissəsinin başlanğıc və son 23 nəzər salaq. İndi bizim sıralanır hissəsi bir sıra, 23, var və çeşidlənməmiş hissəsi bu beş ədəd var. Indi də sıralanır hissəsi bizim çeşidlənməmiş hissəsi, 42, növbəti sayı daxil edək. 

Bunu etmək üçün, biz 23-42 müqayisə etmək lazımdır - bizim sıralanır hissəsi yalnız element günə qədər. Qırx iki 23 böyükdür, belə ki, biz sadəcə sonuna 42 əlavə edə bilərsiniz siyahının ən sıralanır hissəsi. Böyük! İndi sıralanır hissəsi iki elementlər vardır və bizim çeşidlənməmiş hissəsi dörd elementlər vardır. Belə ki, çeşidlənməmiş hissəsi növbəti element, indi isə 4 hərəkət edək. Belə ki, bu sıralanır hissəsində yerləşir qoyulmalıdır? 

Unutmayın, biz sıralanır üçün bu sayı yerləşdirmək istəyirəm bizim sıralanır hissəsi düzgün dəfə sıralanır qalır. Biz 42 sağ üçün 4 yer, onda bizim siyahı üçün həyata olacaq. Belə ki, bizim sort hissəsi sağ-sola hərəkət davam edək. Biz hərəkət olaraq, yeni sayı otaq etmək üçün bir yer aşağı hər bir nömrə keçmək bildirin. Okay, 4 də az 23, belə ki, biz burada yerləşdirmək mümkün deyil. Nin 23 doğru bir yerdə hərəkət edək. 

Biz sıralanır hissəsi ilk yuvasına 4 yerləşdirmək istəyirsinizsə deməkdir. Siyahıda bu məkan artıq boş necə edək, biz onlara karşılaştıysanız kimi sıralanır elementləri aşağı hərəkət etdik çünki. Bütün hüquqlar. Belə ki, biz orada ortasında istəyirik. Nin sıralanır hissəsi daxil 16 daxil bizim alqoritm davam edək. On altı az 42-dən, belə ki, bu və sağ üçün 42 keçmək qoy edir. On altı az 23-dən, belə nin də element keçmək qoy edir. 

İndi, 16 4-dən çoxdur. Biz 4 və 23 arasında 16 əlavə etmək istədiyiniz kimi Belə ki, görünür. Sağ sol siyahısı sıralanır hissəsi ilə hərəkət edərkən, 4 Nömrəni daha kiçik olduğunu biz gördük ilk sayı biz daxil çalışdığınız. Belə ki, indi biz bu boş yuvasına 16 əlavə edə bilərsiniz ki, unutmayın, biz artıq sort hissəsində hərəkət elementləri ilə yaratdıq biz onlara karşılaştıysanız kimi. 

Bütün hüquqlar. İndi dörd sıralanır elementlər və iki çeşidlənməmiş elementləri var. Belə ki, ən sıralanır hissəsi daxil 8 hərəkət edək. Səkkiz az 42 edir. Səkkiz az 23. Və 8-dən az 16. Amma 8 4 çoxdur. Beləliklə, biz 4 və 16 arasında 8 daxil etmək istərdim. 15 - Və indi biz yalnız sort tərk daha bir element var. On beş az 42 edir On beş az 23. Və 15-dən az 16. Amma 15 8 çoxdur. 

Bizim son daxil etmək istədiyiniz Belə ki, burada. Və biz tamamlayın. Biz, çeşidlənməmiş hissəsi artıq elementləri var və bizim sıralanır hissəsi doğru üçün deyil. Ədədlər kiçik olan ən böyük əmr edir. Belə ki, biz yalnız ifa addımlar təsvir bəzi pseudocode nəzər salaq. 

Line 1, biz siyahıda hər element üzərində təkrarlamaq lazımdır görə bilərsiniz ilk istisna olmaqla, çeşidlənməmiş hissəsi ilk element bəri sadəcə olacaq bu sıralanır hissəsi ilk element. Xətləri, 2 və 3-biz çeşidlənməmiş hissəsi bizim cari yer takip saxlanılması edirik. Element, hazırda sıralaması hissəsi daxil hərəkət sayını və j də çeşidlənməmiş hissəsi bizim index təmsil edir. 

Line 4, biz sağ sol sıralanır hissəsi vasitəsilə iterating edirik. Biz cari vəziyyəti sol element dəfə iterating dayandırmaq istəyirəm biz daxil çalışdığınız element azdır. 5 satırında, biz doğru bir yer qarşılaşa hər element dəyişkən edirik. Biz ilk element tapmaq zaman Beləliklə, biz daxil aydın kosmik olacaq biz hərəkət etdiyiniz element azdır. Line 6, biz sıralanır hissəsi ilə sol hərəkət davam üçün counter təzələyirik,. Nəhayət, line 7-də, biz siyahısı sıralanır hissəsi daxil element daxil edirik. 

Biz, bu mövqe j daxil etmək üçün OK bilirik ki, biz artıq sağ orada bir yer olmaq üçün istifadə ki element taşıdıktan çünki. Unutmayın, biz sol sağdan sıralanır hissəsi ilə hərəkət edirik ancaq sol sağ çeşidlənməmiş hissəsi ilə hərəkət edirik. Bütün hüquqlar. Indi alqoritm etdi ki, çalışan nə qədər nəzər salaq. Biz ilk bu alqoritm pis halda çalıştırmak üçün necə sürer sual edəcəyik. Biz Big O notation ilə çalışan zaman təmsil Xatırladaq ki,. Bizim siyahısı düzmək üçün, biz, çeşidlənməmiş hissəsi elementləri üzərində təkrarlamaq idi və potensial sıralanır hissəsi bütün elementləri üzərində həmin elementlərin hər biri üçün. Daxilən, bir O (n ^ 2) əməliyyat kimi bu səslər. 

Bizim pseudocode baxanda, biz başqa loop daxili iç içə bir loop var olan, həqiqətən, bir O (n ^ 2) əməliyyat kimi səslənir. Lakin siyahı sıralanır hissəsi çox sonuna qədər bütün siyahısı vermədi. Hələ ki, biz potensial sıralanır hissəsinin başında yeni element daxil edə bilər alqoritmi hər iteration haqqında olan biz sıralanır hissəsi hazırda hər element baxmaq istədiyiniz deməkdir. Belə ki, biz potensial, ikinci element üçün bir müqayisə edə bilər deməkdir Üçüncü element üçün iki müqayisə, və s. Belə ki, addımlar ümumi sayı 1-dən siyahı minus 1 uzunluğu integers cəmidir. Biz bir toplama ilə təmsil edə bilər. 

Biz burada summations daxil deyil, lakin bu toplama bərabər çıxır ki, n / 2 - ekvivalent n ^ 2/2 olan 2-dən çox, - n (1 n). Asimptotik iş haqqında danışarkən, bu n ^ 2 termini n müddət hakim gedir. Belə ki, durub sırala Big O (n ^ 2). Biz artıq sıralaması siyahısına daxil sort qaçdı əgər. Bu halda, biz sadəcə soldan sağa sıralanır hissəsi qurmaq istiyorum. Belə ki, biz yalnız n addımlar qaydada lazımdır. 

Yəni, durub sırala n ən yaxşı halda performans o deməkdir ki, olan biz Ω (n) ilə təmsil edir. Və ki, durub sırala üçün bu yalnız çox alqoritmlər biri siyahısını düzmək üçün istifadə edə bilərsiniz. My name Tommy və bu CS50 edir. [CS50.TV] Oh, siz yalnız bir dəfə başlayır ki, dayandırmaq bilməz. Oh, biz etdi - >> Boom!