წრფივ დროში შერწყმა

შერწყმით სორტირების დარჩენილი ნაწილი არის merge ფუნქცია, რომელიც ორ მხებ დასორტირებულ ქვესიმრავლეს - array[p..q]-ს და array[q+1..r]-ს - შერწყავს ერთ დასორტირებულ ქვესიმრავლედ: array[p..r]. ვნახავთ, როგორ უნდა შევქმნათ ეს ფუნქცია ისე, რომ ის მაქსიმალურად ეფექტური იყოს. ვთქვათ, ორ ქვესიმრავლეს ჯამში აქვს $n$n ელემენტი. უნდა გავაანალიზოთ თითოეული ელემენტი, რათა ისინი ერთმანეთს შევრწყათ და, შესაბამისად, საუკეთესო დრო, რისი იმედიც შეიძლება, გვქონდეს არის $\Theta(n)$\Theta, left parenthesis, n, right parenthesis. ვნახავთ, როგორ შევრწყათ $n$n ცალი ელემენტი $\Theta(n)$\Theta, left parenthesis, n, right parenthesis დროში.

დასორტირებული ქვესიმრავლეების array[p..q]-ისა და array[q+1..r]-ის შერწყმისათვის და შედეგის array[p..r]-ში ქონისათვის ჯერ უნდა შევქმნათ დროებითი მასივები და array[p..q] და array[q+1..r] დავაკოპიროთ ამ დროებით მასივებში. ზემოდან ვერ გადავაწერთ array[p..r]-ს მანამ, სანამ array[p..q]-სა და array[q+1..r]-ში თავდაპირველად მყოფი ელემენტები უსაფრთხოდ დაკოპირებული არ გვექნება.

შესაბამისად, merge ფუნქციაში უპირველესი საქმე არის ორი დროებითი მასივის შექმნა, lowHalf და highHalf, რათა array[p..q]-ის ყველა ელემენტი გადავწეროთ lowHalf-ში და array[q+1..r]-ის ყველა ელემენტი გადავწეროთ highHalf-ში. რამდენად დიდი უნდა იყოს lowHalf? ქვესიმრავლე array[p..q] შეიცავს $q-p+1$q, minus, p, plus, 1 ელემენტს. და highHalf? ქვესიმრავლე array[q+1..r] შეიცავს $r-q$r, minus, q ელემენტს (JavaScript-ში მასივის შექმნისას არ გვჭირდება მისი ზომის მითითება, მაგრამ ვინაიდან პროგრამირების ბევრ ენაში ეს საჭიროა, ალგორითმის აღწერისას მას მაინც განვიხილავთ).

ჩვენი მაგალითის მასივში [14, 7, 3, 12, 9, 11, 6, 2], აი, როგორ გამოიყურება ყველაფერი მას შემდეგ, რაც რეკურსიულად დავასორტირეთ array[0..3] და array[4..7] ($p=0$p, equals, 0, $q=3$q, equals, 3 და $r=7$r, equals, 7) და გადავწერეთ ეს ქვემასივები lowHalf-სა და highHalf-ში:

array-ში რიცხვები გაფერმკრთალებულია (ნაცრისფრად) იმის საჩვენებლად, რომ იმის მიუხედავად, რომ მასივის ეს პოზიციები ინახავენ მნიშვნელობებს, „ნამდვილი“ მნიშვნელობები ახლა lowHalf-სა და highHalf-შია. სურვილის შემთხვევაში, შეგვიძლია, გაფერმკრთალებულ რიცხვებს ზემოდან გადავაწეროთ.

შემდეგ, შევრწყავთ ორ სორტირებულ ქვემასივს, lowHalf-სა და highHalf-დან array[p..r]-ში. ამ ორი ქვემასივიდან უმცირესი მნიშვნელობა უნდა ჩავსვათ array[p]-ში. სად შეიძლება იყოს ეს უმცირესი მნიშვნელობა? ვინაიდან ქვესიმრავლეები დასორტირებულია, უმცირესი მნიშვნელობა უნდა იყოს მხოლოდ ორი ადგილიდან ერთ-ერთში: ან lowHalf[0]-ში, ან highHalf[0]-ში. (შესაძლებელია, რომ იგივე მნიშვნელობა არის ორივე ადგილას. ამ შემთხვევაში ამ ორიდან ნებისმიერს ვიღებთ.) მხოლოდ ერთი შედარებით შეგვიძლია, გავარკვიოთ, lowHalf[0] გადავწეროთ array[p]-ში თუ - highHalf[0]. ჩვენს მაგალითში highHalf[0] იყო უფრო მცირე. აგრეთვე დავთქვათ სამი ცვლადი, რომლებიც მასივების დაინდექსებისთვის გამოგვადგება:

მას შემდეგ, რაც lowHalf-დან ან highHalf-დან გადავწერთ array-ში, უნდა გავზარდოთ (1 მივუმატოთ) k, რათა შემდეგი უმცირესი ელემენტი ჩავწეროთ array-ს შემდეგ პოზიციაზე. აგრეთვე უნდა გავზარდოთ i იმ შემთხვევაში, თუ გადმოვწერეთ lowHalf-დან, ან გავზარდოთ j იმ შემთხვევაში, თუ გადმოვწერეთ highHalf-იდან. აქ მოცემულია რამდენიმე მასივი მანამ და მას შემდეგ, რაც პირველი ელემენტი გადმოიწერება array-ში:

ჩვენ გავაფერმკრთალეთ (ნაცრისფრად) highHalf[0] იმის საჩვენებლად, რომ ის აღარ შეიცავს იმ მნიშვნელობას, რომელსაც ჩვენ კიდევ განვიხილავთ. highHalf მასივის შეურწყმელი ნაწილი იწყება ინდექს j-ზე, რომელიც ახლა არის 1. array[p]-ში მყოფი მნიშვნელობა აღარ არის გაფერმკრთალებული, რადგან მასში „ნამდვილი“ მნიშვნელობა ჩავწერეთ.

სად შეიძლება, იყოს array-ში გადმოსაკოპირებელი შემდეგი მნიშვნელობა? ის არის ან პირველი აუღებელი ელემენტი lowHalf-ში (lowHalf[0]) ან პირველი აუღებელი ელემენტი highHalf-ში (highHalf[1]). ერთი შედარებით ვარკვევთ, რომ lowHalf[0] არის უფრო მცირე და მას ვაკოპირებთ array[k]-ში და k-სა და i-ს ვზრდით ერთით:

შემდეგ, ვადარებთ lowHalf[1]-სა და highHalf[1]-ს, ვარკვევთ, რომ უნდა გადავწეროთ highHalf[1] array[k]-ში. შემდეგ ერთით ვზრდით k-სა და j-ს:

განაგრძეთ, ყოველთვის შეადარეთ lowHalf[i] და highHalf[j], გადაწერეთ მათ შორის უმცირესი array[k]-ში და ერთით გაზარდეთ ან i ან j:

საბოლოოდ lowHalf-ს ყველა ელემენტი ან highHalf-ს ყველა ელემენტი იქნება გადაწერილი array-ში. ამ მაგალითში, highHalf-ის ყველა ელემენტი გადაიწერება ისე, რომ lowHalf-ში კიდევ იქნება რამდენიმე ელემენტი დარჩენილი. ვასრულებთ lowHalf-ში ან highHalf-ში დარჩენილი ელემენტების გადაწერით:

ჩვენ ვთქვით, რომ $n$n ცალი ელემენტის შერწყმა საჭიროებს $\Theta(n)$\Theta, left parenthesis, n, right parenthesis დროს და, შესაბამისად, შერწყმის სამუშაო დრო არის წრფივი ქვემასივის ზომასთან მიმართებაში. ვნახოთ, რატომ არის ეს ჭეშმარიტი. ჩვენ ვნახეთ შერწყმის სამი ნაწილი:

რამდენხაზიანი კოდი გვჭირდება ამ ნაბიჯების განსახორციელებლად? ეს არის მუდმივი რაოდენობა ელემენტზე. თითოეული ელემენტი გადაიწერება array მასივიდან ან lowHalf-ში ან highHalf-ში ზუსტად ერთჯერ ნაბიჯ 1-ში. თითოეული შედარება ნაბიჯ 2-ში საჭიროებს მუდმივ (კონსტანტა) დროს, რადგან ის ადარებს მხოლოდ ორ ელემენტს და თითოეული ელემენტი „იგებს“ შედარებას მაქსიმუმ ერთჯერ. თითოეული ელემენტი გადაიწერება array-ში ზუსტად ერთჯერ ნაბიჯ 2-ში და 3-ში ჯამურად. ვინაიდან კოდის თითოეულ ხაზს ვუშვებთ ელემენტზე მუდმივ რაოდენობაჯერ და დაშვებული გვაქვს, რომ array[p..q] ქვემასივი შეიცავს $n$n ელემენტს, შერწყმის სამუშაო დრო არის $\Theta(n)$\Theta, left parenthesis, n, right parenthesis.

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

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.