Python'da merge sort: bosqichma-bosqich qo'llanma + kod

Sizda ma'lumotlar bor. Ularni sort qilish kerak. Yetarlicha oddiy masaladek tuyuladi, lekin ma'lum bo'lishicha, tanlash uchun bir nechta turli sorting algoritmlari mavjud. Bubble sort, quicksort, merge sort, Timsort… agar natija bir xil bo'lsa, ular bir-biridan qanchalik farq qilishi mumkin? Javob: metodologiya jihatidan va, ehtimol, bundan ham muhimrog'i, tezlik jihatidan ancha farq qiladi.

Ushbu maqola Python'ning asosiy sintaksisini yaxshi biladigan va merge sort nima ekanligini hamda u qiymatlar list'ingizni divide and conquer usulida qayta ishlab, qanday ishlashini tushunmoqchi bo'lgan Python dasturchilari uchun. Siz uni Python'da qanday amalga oshirishni va qachon Python'ning built-in sorted() funksiyasi o'rniga undan foydalanish kerakligini bilib olasiz. Asosiy tushunchalarni o'rganishingizga yordam beramiz va bu masalani bir yo'la hal qilib beramiz, faqat o'qishda davom eting.

Merge sort algoritmi nima?

1945-yilda matematik John von Neumann tomonidan ishlab chiqilgan merge sort — qiymatlarni eng kichigidan eng kattasiga qarab sort qilish uchun mo'ljallangan divide-and-conquer algoritmi. Bu usul sort qilinmagan massivni kichikroq qismlarga bo'ladi, o'sha kichik bo'laklarni sort qiladi va so'ngra ularni strategik tarzda qaytadan birlashtiradi, natijada qiymatlarning butun to'plami sort qilinadi.

Dasturlash tillarida odatda top-down, recursive yondashuv bilan amalga oshiriladigan merge sort — oldindan aytib bo'ladigan unumdorlikka ega stable sorting algoritmi. Python'da built-in merge sort funksiyasi yo'q, lekin shunga qaramay bu algoritmni konseptual jihatdan tushunish muhim va u ba'zi vaziyatlarda foydali bo'lib chiqadi. Hatto uni tuple'lar yoki boshqa obyektlarni muayyan maydonlar asosida sort qiladigan qilib moslashtirishingiz ham mumkin.

Merge sort qanday ishlaydi

Qiymatlar to'plami uchun merge sort'ni bajarish uchun avval to'plamingizni taxminan ikki yarmiga bo'lasiz. Har bir sub array faqat bitta elementdan iborat bo'lguncha bo'lishda davom eting. Bu kichikroq massivlar allaqachon sort qilingan, chunki ularning har birida faqat bittadan element bor.

Keyin sublist'laringizni birlashtirishni boshlang. Ikkita qo'shni list'ni oling, ularning har biridan birinchi — va demak, eng kichik — elementni solishtiring va qaysi biri kichikroq bo'lsa, uni alohida birlashtirilgan list'ga qo'shing. Sub array'lardan biri tugaguncha shunday davom eting. Siz sort qilingan segmentlardan boshlaganingiz uchun shundan so'ng boshqa sublist'dagi qolgan elementlarni shunchaki birlashtirilgan list'ingiz oxiriga qo'shishingiz mumkin.

Bu birlashtirish strategiyasini yakuniy yechimga — to'liq sort qilingan to'plamga — yetib kelguningizcha tobora kattaroq sub array'larda takrorlaysiz. Natijada yakuniy sort qilingan list yoki sorting algoritmlari haqidagi muhokamalarda ko'pincha ta'riflanganidek, sort qilingan massiv hosil bo'ladi.

Recursive (top-down) merge sort'ning Python'dagi implementatsiyasi

Python'da merge sort yozishning eng keng tarqalgan usuli — yuqorida tasvirlaganimiz recursive, top-down yondashuv. Bu usul butun list'dan boshlaydi va qaytadan birlashtirishdan oldin uni qayta-qayta kichikroq list'larga bo'ladi.

Recursive merge sort algoritmining Python'dagi implementatsiyasi ikki vazifadan iborat: bo'lish va birlashtirish. Butun merge sort algoritmi uchun bitta Python funksiyasini yaratishingiz mumkin bo'lsa-da, uni har bir ish uchun bir-birini to'ldiruvchi ikkita funksiya sifatida tushunish biroz osonroq:

• merge_sort() — recursive bo'lishni boshqarish uchun (merge() funksiyasini chaqiradi)

• merge() — sort qilingan bo'laklarni birlashtirish uchun

Divide and Conquer: merge_sort()

Bu asosiy funksiyaning maqsadi qiymatlarning dastlabki list'ini uzluksiz bo'lib borish va sublist'larni qayta birlashtirish uchun merge()'ni chaqirish orqali merge sort algoritmini bajarishdir.

def merge_sort(values): if len(values) <= 1:
        return values

    midpoint = len(values) // 2

    left = merge_sort(values[:midpoint])
    right = merge_sort(values[midpoint:])

    return merge(left, right)

Umumiy tarzda aytganda, bu kod avval list bo'shmi yoki bitta elementdan iboratmi, shuni tekshiradi. Agar shunday bo'lsa, list'ni qaytaradi. Biroq agar list'da bittadan ortiq element bo'lsa, merge_sort() floor division (//) yordamida uning o'rta nuqtasini topadi va list'ni ikki yarmiga — chap va o'ngga — bo'ladi... U o'zini o'zi recursive tarzda chaqiradi va bitta yoki undan kam elementli list'dan iborat base case'ga yetguncha chap yarmini ham, o'ng yarmini ham uzluksiz bo'lib boradi.

Faqat bitta elementli kichikroq sub array'larga ega bo'lgach, chaqiruvlar qiymat qaytara boshlaydi va merge(left, right) ikkita sort qilingan yarmni birlashtirishni boshlaydi. Kod to'liq sort qilingan list'ni qaytarish uchun merge()'ni qancha kerak bo'lsa, shuncha marta chaqirish orqali davom etadi.

Sort: merge()

merge() yordamchi funksiyasi ikkita sort qilingan yarmni qabul qiladi va ularni bitta sort qilingan massivga birlashtiradi.

def merge(left, right):
    merged = []
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])

    return merged

merge() bo'sh natija list'i va har bir sublist'dagi joriy pozitsiyani kuzatib boradigan ikkita index bilan boshlanadi. Index'lardan birortasi sub array oxiriga yetmaguncha funksiya sublist'lardagi joriy qiymatlarni solishtiradi va kichigini oladi. U o'sha kichikroq qiymatni natija list'iga qo'shadi va o'sha sublist'ning index'ini oshiradi. Shuningdek, e'tibor bering, qiymatlar teng bo'lgan holatda bu solishtirish chap qiymatni afzal ko'radi, bu esa algoritmning stability'siga hissa qo'shadi.

Kod list segmentlaridan birining oxiriga yetgach, birlashtirilgan list'ni qaytarishdan oldin boshqa segmentdagi qolgan elementlarni .extend() method'i yordamida natijaga qo'shadi.

merge_sort()'ni chaqirish

Hammasini birlashtirsak, kiritilgan massivda merge_sort()'ni chaqirish uchun kerak bo'ladigan yakuniy Python kodi mana bunday. Yodda tuting, merge_sort() funksiyasi merge()'ni chaqiradi:

numbers = [7, 1, 10, 8, 2, 4, 6, 9]

sorted_numbers = merge_sort(numbers)

print(sorted_numbers)

# Expected result:
# [1, 2, 4, 6, 7, 8, 9, 10]

Python'da merge sort'ni amalga oshirishning iterative (bottom-up) yondashuvi

Muqobil ravishda, merge sort algoritmini recursion'siz, iterative, bottom-up yondashuvda ham tasavvur qilishingiz mumkin. Merge sort'ga bunday qarash har bir alohida elementni 1 o'lchamli sort qilingan guruh sifatida ko'radi va qo'shni guruhlarni birlashtiradi. Keyingi qadamda u 2 tadan, so'ng 4 tadan va hokazo guruhlarni birlashtiradi. Har bir o'tishda algoritm butun list'ni qayta ishlab chiqquncha tobora kattaroq sort qilingan yarmlarni birlashtiradi.

Mana merge_sort()'ning iterative versiyasi uchun Python kodi. Bu usul ham list'ning kichik qismlarini sort qilish uchun o'sha merge() yordamchi funksiyasiga tayanadi:

def merge_sort_iterative(values):
    result = values[:]
    width = 1

    while width < len(result):
        merged = []

        for i in range(0, len(result), 2 * width):
            left = result[i:i + width]
            right = result[i + width:i + 2 * width]
            merged.extend(merge(left, right))

        result = merged
        width *= 2

    return result

Bu usul recursion'dan qochish uchun loop'lardan foydalanadi, lekin oxir-oqibat top-down yondashuv bilan bir xil umumiy time va auxiliary-space complexity'ga ega. Ba'zilar bu Python kodini recursive versiyaga qaraganda o'qish va amalga oshirish biroz qiyinroq deb ham hisoblashadi.

Linked list'larda merge sort

Istalgan index pozitsiyasidagi elementlarga oson murojaat qilish mumkin bo'lgan oddiy Python list'laridan farqli o'laroq, linked list'ning har bir node'i faqat keyingi node qayerdaligini biladi. Merge sort bunday linked list'lar uchun ayniqsa yaxshi ishlaydi, chunki u node'larga index bo'yicha qayta-qayta murojaat qilish o'rniga ularni ketma-ket qayta ishlay oladi.

Top-down yondashuvga amal qilib, linked list'ning o'rta nuqtasini slow va fast pointer'lar yordamida topishingiz mumkin. Chap va o'ng linked list'larni olish uchun o'rta nuqtadagi bog'lanishni uzasiz va so'ng har bir yarmini recursive tarzda sort qilasiz. Linked list'larni joriy node'lardagi qiymatlarni solishtirib va kichikroq node'ni birlashtirilgan list'ga ulab, qaytadan birlashtiring. Shundan so'ng jarayon standart Python list implementatsiyasidagi kabi bog'langan sublist'lar bo'ylab oldinga siljishda davom etadi.

E'tibor bering, linked list'lar uchun mavjud node'larni qayta ulash orqali birlashtirishingiz mumkin va merge amalining o'zi uchun juda kam auxiliary space kerak bo'ladi. Shuning uchun dasturchilar linked list'lar uchun ko'pincha quicksort kabi boshqa sorting algoritmlaridan ko'ra merge sort'ni afzal ko'rishadi.

Vaqt, xotira va unumdorlik tahlili

Time va space complexity haqida eng samarali tarzda alohida amallarni sanash orqali emas, balki to'plamingiz hajmi o'sgani sari algoritmning umumiy xatti-harakatini ko'rib chiqish orqali fikr yuritishingiz mumkin. Mutaxassislar buning uchun odatda big O notation'dan foydalanadi. Uzunligi n bo'lgan list berilganda, O(1) algoritmning vaqti va xotirasi list uzunligiga bog'liq emasligini anglatadi; O(n) usul hajm bilan chiziqli o'sishini anglatadi; O(n2) — kvadratik va hokazo. Shuningdek, algoritmning big-O unumdorligini best, worst va average case uchun ham ko'rib chiqishingiz mumkin.

Merge sort — best, average va worst case ssenariylarida O(n log n) time complexity bilan ishlaydigan, oldindan aytib bo'ladigan darajada barqaror algoritm. Bu algoritmning ikki asosiy qadamini eslang: bo'lish va birlashtirish. Masalani qayta-qayta ikki yarmga bo'lish O(log n) darajani hosil qiladi, har bir darajadagi birlashtirish ishi esa taxminan n ta elementni qayta ishlaydi. Umuman olganda, dastlabki elementlar allaqachon sort qilingan bo'ladimi yoki butunlay tasodifiy tartibda bo'ladimi, merge sort O(n log n) vaqt talab qiladi.

Bu yerda keltirilgan standart Python implementatsiyasi birlashtirish jarayonida yaratiladigan turli vaqtinchalik list'larni saqlash uchun O(n) auxiliary space talab qiladi. Recursive call stack ham O(log n) joydan foydalanadi, lekin umumiy space complexity O(n), chunki O(n) O(log n)'dan ustun keladi. Iterative yondashuv bilan recursion'ni olib tashlash space complexity'ga ta'sir qilmaydi, chunki vaqtinchalik sublist'lar uchun baribir O(n) joy kerak bo'ladi. Biroq linked list'lar bilan ishlaganingizda recursive stack uchun O(log n) auxiliary space'li Python implementatsiyasini yaratishingiz mumkin, chunki birlashtirish paytida node'larni qayta ulay olasiz va bu faqat O(1) joy talab qiladi.

Unumdorlik jihatidan merge sort — O(n log n) unumdorlikka ega stable algoritm. Uning asosiy muammosi vaqtinchalik oraliq list'lar uchun talab qilinadigan qo'shimcha xotira. Sizga stability kerak bo'lganda, oldindan aytib bo'ladigan worst-case ssenariy kerak bo'lganda yoki linked list'lar bilan ishlayotganingizda bu algoritmga murojaat qilishingiz ehtimoli ko'proq.

Merge sort va boshqa sorting algoritmlari

Ushbu maqola davomida merge sort'ni puxta o'rgandingiz, lekin yana bir nechta boshqa sorting algoritmlari ham mavjudligini ta'kidlab o'tish joiz. Bu bo'limda ulardan ba'zilarini muhokama qilamiz va Python'ning built-in sorted() funksiyasi asosida yotgan algoritm — timsort bilan yakunlaymiz.

Bubble Sort

Bubble sort — oddiy algoritm va ko'pincha computer science kurslarida birinchilardan bo'lib o'rgatiladigan algoritmlardan biri. U qo'shni qiymatlarni qayta-qayta solishtiradi va noto'g'ri tartibda turganlarining o'rnini almashtiradi, odatda barcha elementlarni to'g'ri joyiga qo'yishdan oldin list bo'ylab bir necha marta o'tishga to'g'ri keladi. Konseptual jihatdan tushunish oson bo'lsa-da, katta list'lardagi past unumdorligi tufayli bubble sort'ni amaliy sorting usuli sifatida emas, balki ko'pincha o'quv vositasi sifatida ko'rasiz. Worst case'da bubble sort O(n2) time complexity'ga ega, garchi odatiy in-place implementatsiyasi uchun atigi O(1) auxiliary space'dan foydalansa ham.

Quicksort

Quicksort ham merge sort kabi divide-and-conquer algoritmi, lekin qiymatlarni qayta-qayta ikki yarmga bo'ladigan merge sort'dan farqli o'laroq, quicksort bitta qiymatni pivot sifatida tanlaydi. So'ng qolgan elementlarni pivot'dan kichik yoki katta bo'lgan partition'larga ajratadi. Keyin partition'lar ham quicksort barcha elementlarni sort qilguncha recursive tarzda xuddi shunday ishlov oladi.

Bu usulning samaradorligi pivot tanloviga juda bog'liq. Best yoki average case'da quicksort vaqt jihatidan O(n log n) algoritm, lekin worst case'da u O(n2) bo'lishi mumkin. U odatda merge sort'ga qaraganda kamroq qo'shimcha xotira talab qiladi, lekin quicksort odatda stable algoritm emas, ya'ni teng elementlar yangi tartibda joylashib qolishi mumkin.

sorted(): Timsort

O'z yaratuvchisi Tim Peters sharafiga nomlangan Timsort Python'ning sorted() funksiyasi hamda uning list.sort() method'i asosida ishlaydi. Bu merge sort'dan ham, insertion sort'dan ham g'oyalar olgan gibrid sorting algoritmi.

Timsort aynan real hayotdagi ma'lumotlarni hisobga oladi; masalan, u qisman sort qilingan qiymatlardan foydalana oladi. An'anaviy merge sort'dan farqli o'laroq, Timsort recursive tarzda ikkita sort qilingan yarm yaratish o'rniga mavjud sort qilingan run'larni, ya'ni allaqachon to'g'ri tartibda turgan ketma-ketliklarni qidiradi. U qisqaroq run'larni insertion sort yordamida uzaytiradi va so'ngra butun to'plamni sort qilguncha run'larni merge sort uslubida birlashtiradi.

Worst case'da Timsort xuddi merge sort kabi O(n log n) vaqtda ishlaydi; biroq best-case ssenariylarda u O(n) bo'lishi mumkin. Bu Python dasturchilari ham sorted()'da, ham .sort() method'ida amalga oshirgan stable algoritm.

sorted()'ni list'lar ham kiradigan istalgan iterable'da ishlatishingiz mumkin, .sort() esa list method'i. Ikkala method ham ixtiyoriy key va reverse argumentlarini qo'llab-quvvatlaydi. Bu ikkisi o'rtasidagi asosiy farq shundaki, .sort() method'i list'ni in place sort qiladi, sorted() esa list ustida ishlaydi va o'sha list'ning sort qilingan versiyasini qaytaradi.

Python'da qiymatlar list'ini sort qilmoqchi bo'lganingizda odatda merge sort yoki boshqa biror sorting algoritmini noldan amalga oshirish o'rniga shunchaki sorted() yoki .sort()'dan foydalanasiz. Shunga qaramay, linked list'lar bilan ishlaganda, muayyan algoritmik talablarni hisobga olganda yoki boshqa maxsus holatlarda o'zingizning sorting usulingizni yozishni tanlashingiz mumkin.

Merge sort'ning real hayotda qo'llanilishi

Sort qilingan list'lar yaratish uchun odatda sorted() yoki list.sort()'ga tayansangiz-da, brauzer tarixini, musiqa playlist'larini yoki tez-tez o'zgarib turadigan tartiblangan ketma-ketliklarni kuzatish kabi linked list'lar bilan ishlaganda merge sort'ni amalga oshirish foydali bo'lishi mumkin. Shuningdek, xotiraga sig'maydigan darajada katta hajmdagi kiruvchi ma'lumotlarni sort qilishda ham merge sort'ga murojaat qilishingiz mumkin. Katta dataset'lar bilan ma'lumotlarning alohida bo'laklarini sort qilib, keyinroq sort qilingan bo'laklarni birlashtirishingiz mumkin. Merge sort'ni distributed computing yordamida ma'lumotlar qismlarini parallel sort qilishda ham foydali deb topishingiz mumkin.

Xulosa

Merge sort qiymatlaringizni sort qilishning stable va oldindan aytib bo'ladigan usulini beradi. Python'da merge sort'ning built-in versiyasi bo'lmasa-da, o'zingiznikini top-down (recursive) yoki bottom-up (iterative) yondashuv bilan nisbatan oson amalga oshirishingiz mumkin. Merge sort best, average va worst case'lar uchun oldindan aytib bo'ladigan O(n log n) time complexity'ga ega, lekin odatda O(n) auxiliary space talab qiladi, bu esa ba'zi boshqa sorting algoritmlari talab qiladiganidan ko'proq. Merge sort'ni noldan yozish o'rniga, ehtimol, ko'p hollarda Python'ning sorted() funksiyasi yoki uning list.sort() method'iga murojaat qilasiz, ularning ikkalasi ham ichki tomondan Timsort'dan foydalanadi.

Sort qilingan massivlar yaratadigan boshqa algoritmlar singari merge sort ham o'zining afzalliklari va kamchiliklariga ega. Merge sort'ni boshqa variantlar bilan taqqoslash uchun quyidagi prompt'dan boshlab AI Tutor'ni sinab ko'ring: