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

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

პივოტის არჩევის შემდეგ ვყოფთ ქვემასივს მასში გავლით, მარცხნიდან მარჯვნივ, თითოეულ ელემენტს ვადარებთ პივოტს. ვინარჩუნებთ ორ ინდექსს — q-სა და j-ს ქვემასივში, რომელიც მას ოთხ ნაწილამდე ყოფს. ვიყენებთ ცვლადის სახელს q, რადგან ეს ინდექსი ბოლოს მიუთითებს ჩვენს პივოტს. ვიყენებთ j-ს, რადგან ის ხშირად გამოყენებადი სახელია „კონტრ“ ცვლადისთვის, და ცვლადს უგულებელვყოფთ, როგორც კი დავასრულებთ.

თავდაპირველად ორივე, q და j, უდრის p-ს. თითოეულ ნაბიჯზე ვადარებთ A[j]-ს, ჯგუფ U-ში ყველაზე მარცხნივ მდებარე ელემენტს, პივოტს. თუ A[j] მეტია პივოტზე, მაშინ ერთით ვზრდით j-ს, ასე რომ, G-სა და U-ს გამყოფი ხაზი ერთი პოზიციით მარჯვნივ გადაინაცვლებს:

თუ საპირისპირო შემთხვევა მოხდა და A[j] ნაკლებია ან ტოლია პივოტზე, მაშინ წავანაცვლებთ A[j]-სა და A[q] (ყველაზე მარცხნივ მყოფი ელემენტი ჯგუფ G-ში), ერთით გავზრდით j-ს და ერთით გავზრდით q-ს, L და G ჯგუფების გამყოფ ხაზს გადავასრიალებთ და აგრეთვე გადავასრიალებთ G და U ჯგუფების გამყოფ ხაზს ერთი პოზიციით მარჯვნივ:

როგორც კი პივოტამდე მივალთ, ჯგუფი U ცარიელია. პივოტს ვუცვლით ადგილს ჯგუფ G-ში მყოფ ყველაზე მარცხნივ ელემენტთან: წავანაცვლოთ A[r] და A[q]. ეს წანაცვლება ჩასვამს პივოტს L და G ჯგუფებს შორის და ის მაინც სწორად იქცევა იმ შემთხვევაშიც კი, როცა ჯგუფი L ან ჯგუფი G ცარიელია.

partition ფუნქცია, რომელიც ამ იდეის იმპლემენტაციას ახდენს აგრეთვე აბრუნებს ინდექს q-ს, სადაც ბოლოს დასვა პივოტი, რათა quicksort ფუნქციამ, რომელიც მას იძახებს, იცოდეს, სად მოხდა დაყოფები.

აი, ნაბიჯები [12, 7, 14, 9, 10, 11] ქვემასივის დაყოფაში array[4..9]-ში:

$n$‍-ელემენტიანი ქვემასივის დაყოფას ესაჭიროება $\mathrm{\Theta }(n)$‍ დრო. თითოეული ელემენტი A[j] ედრება პივოტს ერთჯერ. A[j] შეიძლება, წაენაცვლოს ან არ წაენაცვლოს A[q]-ს, q შეიძლება, გაიზარდოს ერთით ან არ გაიზარდოს და j ყოველთვის იზრდება. ქვემასივის თითოეულ ელემენტზე განხორციელებული კოდის ხაზების რაოდენობა არის მუდმივი (კონსტანტა). ვინაიდან ქვემასივს აქვს $n$‍ ცალი ელემენტი, დაყოფისთვის საჭირო დრო არის $\mathrm{\Theta }(n)$‍: წრფივ დროში დაყოფა.

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