შერწყმით სორტირება: დაყავი და იბატონე

შერწყმითი სორტირება „დაყავი და იბატონეს“ ყველაზე სუფთა მაგალითია და ნებისმიერ შემავალ მონაცემებზე O(n log n)-ს იძლევა. ასევე ასე ალაგებენ მონაცემთა ბაზები მეხსიერებაში ვერ დატეულ მონაცემებს.

საშუალო⏱ 12 წთ

←ეყრდნობა

0რეკურსია და გამოძახებათა სტეკიშერწყმით სორტირება თავის თავს იძახებს თითო ნახევარზე და უკან დაბრუნებისას აერთიანებს.2მარტივი სორტირებებისამუშაოს შუაზე გაყოფა არის ის, რაც მარტივი სორტირებების O(n²)-ს ამარცხებს.

გზას უხსნის→

2სწრაფი სორტირება და დაყოფასწრაფი სორტირებაც „დაყავი და იბატონე“ არის, ოღონდ სამუშაოს რეკურსიულ გამოძახებებამდე აკეთებს და არა მერე.2დათვლითი სორტირებაშედარებაზე დაფუძნებული სორტირება n log n-ს ვერ აჯობებს; დათვლითი სორტირება საერთოდ არ ადარებს.2კომპარატორები და სტაბილურობაstd::stable_sort შერწყმით სორტირებაა, ამიტომ ტოლი ელემენტები თავის რიგს ინარჩუნებენ.+სუფიქსური მასივისუფიქსები პრეფიქსის სიგრძის გაორმაგებით ლაგდება: არსებითად ეს O(n log n) სორტირების ამოცანაა.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01დაყავი და იბატონე

შერწყმითი სორტირება სამბიჯიან რეცეპტს მისდევს:

დაყავი: გაყავი მასივი ორ ნახევრად mid = (lo + hi) / 2-ზე.
იბატონე: თითოეული ნახევარი რეკურსიულად დაალაგე. ერთელემენტიანი ნაწილი უკვე დალაგებულია: ეს საბაზისო შემთხვევაა.
გააერთიანე: შეარწყი ორი დალაგებული ნახევარი ერთ დალაგებულ მასივად.

მთელი ნამდვილი სამუშაო გაერთიანების ბიჯში ხდება. გაყოფა უბრალოდ ჭრის, სანამ ნაწილები 1-ის ზომის არ გახდება, მერე კი შერწყმები მასივს ქვემოდან ზემოთ აღადგენს, ყოველ ჯერზე ორ დალაგებულ ნაწილს უფრო გრძელად აერთებს.

02შერწყმა: ორი მაჩვენებელი

ორი დალაგებული სიის შერწყმა ორი მაჩვენებლით გავლაა. მაჩვენებელი i მარცხენა ნახევრის თავში დგას, j მარჯვენასი.

შეადარე a[i] და a[j]; უმცირესი ბუფერში დააკოპირე და მისი მაჩვენებელი წაწიე.
როცა ერთი მხარე ამოიწურება, მეორის დანარჩენი დააკოპირე.
ბუფერი უკან a[lo..hi]-ში გადაწერე.

ყოველი ბიჯი ერთ ელემენტს გამოსცემს, ამიტომ m ელემენტის შერწყმა O(m) ღირს. ბუფერის გამო სჭირდება შერწყმით სორტირებას O(n) დამატებითი მეხსიერება.

შედარებისას გამოიყენე <=: ტოლობისას ჯერ მარცხენა აიღე. ასე ტოლი გასაღებები თავდაპირველ რიგს ინარჩუნებს და შერწყმითი სორტირება სტაბილური ხდება.

03რატომ n log n

დახატე რეკურსია დონეებად. დონე 0-ზე ერთი n ზომის ნაწილია, დონე 1-ზე ორი n/2 ზომის, დონე 2-ზე ოთხი n/4 ზომის და ა.შ.

ყოველ დონეზე შერწყმები ერთად ყველა n ელემენტს ერთხელ ეხება: O(n) სამუშაო დონეზე. n-ის განმეორებითი განახევრება 1-ს log₂ n დონის შემდეგ აღწევს. ჯამში: O(n log n).

რეკურენტული სახით: T(n) = 2·T(n/2) + O(n) = O(n log n). სწრაფი სორტირებისგან განსხვავებით ეს შემავალ მონაცემებზე საერთოდ არ არის დამოკიდებული: დალაგებული, უკუღმა თუ შემთხვევითი, შერწყმითი სორტირება ყოველთვის ერთსა და იმავე სამუშაოს აკეთებს. n = 10⁶-ისთვის ეს დაახლოებით 2·10⁷ ბიჯია, O(n²) სორტირების 10¹²-ის ნაცვლად.

04სად ბრწყინავს შერწყმითი სორტირება

აირჩიე შერწყმითი სორტირება (ან ბიბლიოთეკის სტაბილური სორტირება, რომელიც ჩვეულებრივ შერწყმაზეა აგებული), როცა:

გჭირდება სტაბილურობა: std::stable_sort, Java-ს ობიექტების სორტირება და Python-ის Timsort შერწყმითი სორტირებებია
ალაგებ ბმულ სიას: შერწყმას არც პირდაპირი წვდომა სჭირდება და არც დამატებითი მასივი
მონაცემი მეხსიერებაში არ ეტევა: გარე სორტირება დისკიდან დალაგებულ ნაწილებს არწყამს
გჭირდება გარანტირებული უარესი შემთხვევა

შერწყმის ბიჯი თავისთავადაც ინსტრუმენტია. შერწყმისას ყოველ ჯერზე, როცა მარჯვენა ნახევრიდან იღებ, მარცხენაში დარჩენილი ყველა ელემენტი მასზე დიდია: დაუმატე მათი რაოდენობა და O(n log n)-ში დათვლი ინვერსიებს.

ფასი: O(n) დამატებითი მეხსიერება და რიცხვების ჩვეულებრივ მასივებზე პრაქტიკაში სწრაფ სორტირებაზე ოდნავ ნელი.

ფასი ერთი შეხედვით

დრო (ყოველთვის)O(n log n)

ჯამში m ელემენტის შერწყმაO(m)

დამატებითი მეხსიერებაO(n)

რეკურსიის სიღრმეO(log n)

დაიმახსოვრე

შერწყმითი სორტირება ნახევრად ყოფს, თითოეულ ნახევარს რეკურსიულად ალაგებს და ორი მაჩვენებლით არწყამს.
არსებობს log n დონე და თითოეული O(n) შერწყმას აკეთებს, ამიტომ ის ნებისმიერ შემავალ მონაცემებზე O(n log n)-ია.
ის სტაბილურია და ბმულ სიებზეც მუშაობს, მასივებისთვის O(n) დამატებითი მეხსიერების ფასად.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე, როგორ მცირდება აქტიური შუალედი გაყოფისას, მერე როგორ ივსება ბუფერი შერწყმისას ყოველ ჯერზე უმცირესი თავით.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

შერწყმით სორტირება · აქტიური შუალედი [0, 7]

დამხმარე ბუფერი

∅

შერწყმით სორტირება „დაყავი და იბატონე“-თი: 8-ელემენტიან მასივს ვყოფთ, სანამ ნაწილები 1-ზომამდე არ დაიყვანება, მერე დალაგებულ ნაწილებს ვაერთებთ.

ფსევდოკოდი

 1 mergeSort(lo, hi): 2   if lo >= hi: return       // one element is sorted 3   mid = (lo+hi)/2 4   mergeSort(lo,mid); mergeSort(mid+1,hi) 5   merge: pick the smaller front of the two halves 6   … until one half empties 7   copy the merged buffer back

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

[2, 7, 9]-ისა და [3, 4, 10]-ის შერწყმისას რომელია ბუფერში ჩაწერილი პირველი ოთხი ელემენტი?

№2

როგორ შედარდება შერწყმითი სორტირების დრო უკვე დალაგებულ მასივზე შემთხვევითთან?

№3

რატომ ვადარებთ <=-ით (ტოლობისას მარცხნიდან ვიღებთ) შერწყმისას?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeMerge Sorted Array დამწყები↗LeetCodeMerge Two Sorted Lists დამწყები↗LeetCodeSort an Array საშუალო↗LeetCodeSort List საშუალო↗LeetCodeCount of Smaller Numbers After Self მოწინავე↗