Bubble Sort vs Insertion Sort
Bubble sort, bitişik elementlərin cütlərini müqayisə edərkən dəfələrlə çeşidlənəcək siyahıdan keçərək fəaliyyət göstərən çeşidləmə alqoritmidir. Bir cüt element səhv qaydadadırsa, onları düzgün ardıcıllıqla yerləşdirmək üçün dəyişdirilir. Bu keçid başqa dəyişdirmə tələb olunmayana qədər təkrarlanır. Daxiletmə çeşidi həm də daxiletmə siyahısına elementi artıq çeşidlənmiş siyahıda düzgün mövqeyə daxil etməklə fəaliyyət göstərən çeşidləmə alqoritmidir. Siyahı çeşidlənənə qədər bu proses təkrarlanır.
Bubble Sort nədir?
Bubble sort, bitişik elementlərin cütlərini müqayisə edərkən dəfələrlə çeşidlənəcək siyahıdan keçərək fəaliyyət göstərən çeşidləmə alqoritmidir. Bir cüt element səhv qaydadadırsa, onları düzgün ardıcıllıqla yerləşdirmək üçün dəyişdirilir. Bu keçid əlavə dəyişdirmə tələb olunmayana qədər təkrarlanır (bu o deməkdir ki, siyahı sıralanır). Siyahıdakı kiçik elementlər qabarcıq səthə çıxan kimi yuxarıya çıxdığından ona qabarcıq çeşidi adı verilir. Bubble çeşidləmə çox sadə çeşidləmə alqoritmidir, lakin n elementli siyahını çeşidləyərkən orta iş vaxtı mürəkkəbliyi O(n2) olur. Buna görə qabarcıq çeşidləmə çox sayda elementi olan siyahıları çeşidləmək üçün uyğun deyil. Lakin sadəliyinə görə qabarcıq çeşidləmə alqoritmlərə giriş zamanı öyrədilir.
Daxiletmə çeşidi nədir?
Daxiletmə çeşidi başqa çeşidləmə alqoritmidir və giriş siyahısındakı elementi siyahıda düzgün mövqeyə daxil etməklə fəaliyyət göstərir (bu, artıq çeşidlənib). Siyahı sıralanana qədər bu proses təkrar-təkrar tətbiq edilir. Daxiletmə çeşidində çeşidləmə yerində həyata keçirilir. Beləliklə, alqoritmin i-ci təkrarlanmasından sonra siyahıdakı ilk i+1 qeydləri çeşidlənəcək və siyahının qalan hissəsi çeşidlənəcək. Hər təkrarlamada siyahının çeşidlənməmiş hissəsindəki ilk element götürüləcək və siyahının çeşidlənmiş bölməsində düzgün yerə daxil ediləcək. Daxiletmə çeşidi O(n2) orta iş vaxtı mürəkkəbliyinə malikdir. Buna görə əlavə çeşidləmə böyük siyahıları çeşidləmək üçün də uyğun deyil.
Bubble Sort və Insertion Sort arasında fərq nədir?
Həm qabarcıq çeşidləmə, həm də daxiletmə çeşidləmə alqoritmlərinin orta iş vaxtı mürəkkəbliyi O(n2) olsa da, qabarcıq çeşidləmə demək olar ki, hər zaman daxiletmə növündən üstündür. Bu, iki alqoritm üçün lazım olan svopların sayı ilə bağlıdır (qabarcık növləri üçün daha çox svop lazımdır). Lakin qabarcıq çeşidləmənin sadəliyinə görə onun kod ölçüsü çox kiçikdir. Bundan əlavə, O(n3/2) zaman mürəkkəbliyinə malik olan qabıq çeşidi adlanan əlavə çeşidləmə variantı da var ki, bu da ondan praktiki olaraq istifadə etməyə imkan verir. Bundan əlavə, daxiletmə çeşidi qabarcıq çeşidləmə ilə müqayisədə "demək olar ki, çeşidlənmiş" siyahıları çeşidləmək üçün çox səmərəlidir.
