ძირითადი მასალა
კომპიუტერული მეცნიერება
კურსი: კომპიუტერული მეცნიერება > თემა 1
გაკვეთილი 9: სწრაფი დახარისხებადაყოფა წრფივ დროში
სწრაფი სორტირების ნამდვილი საქმე კეთდება დაყოფის ნაბიჯში, რომელიც ყოფს მასივს
array[p..r]
მასივიდან ამოღებული პივოტის გარშემო. მიუხედავად იმისა, რომ ნებისმიერი ელემენტის არჩევა შეგვიძლია ქვემასივში პივოტად, დანაწევრების იმპლემენტაცია ადვილია, თუ ყოველ ჯერზე ყველაზე მარჯვნივ მყოფ ელემენტს, A[r]
-ს, ავირჩევთ პივოტად.პივოტის არჩევის შემდეგ ვყოფთ ქვემასივს მასში გავლით, მარცხნიდან მარჯვნივ, თითოეულ ელემენტს ვადარებთ პივოტს. ვინარჩუნებთ ორ ინდექსს —
q
-სა და j
-ს ქვემასივში, რომელიც მას ოთხ ნაწილამდე ყოფს. ვიყენებთ ცვლადის სახელს q
, რადგან ეს ინდექსი ბოლოს მიუთითებს ჩვენს პივოტს. ვიყენებთ j
-ს, რადგან ის ხშირად გამოყენებადი სახელია „კონტრ“ ცვლადისთვის, და ცვლადს უგულებელვყოფთ, როგორც კი დავასრულებთ.- ელემენტები
array[p..q-1]
-ში არიან „ჯგუფი L“, შედგება ელემენტებისგან, რომლებიც ვიცით, რომ ნაკლებია ან ტოლია პივოტზე. - ელემენტები მასივში
array[q..j-1]
არიან „ჯგუფი G“, შედგება ელემენტებისგან, რომლებიც ვიცით, რომ მეტია პივოტზე. - ელემენტები
array[j..r-1]
-ში არიან „ჯგუფი U“, შედგება ელემენტებისგან, რომელთა დამოკიდებულება პივოტის მიმართ არის უცნობი, რადგან ჯერ ისინი არ შეგვიდარებია. - საბოლოოდ,
array[r]
არის „ჯგუფი P,“ პივოტი.
თავდაპირველად ორივე,
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]
-ში:A[j]
ედრება პივოტს ერთჯერ. A[j]
შეიძლება, წაენაცვლოს ან არ წაენაცვლოს A[q]
-ს, q
შეიძლება, გაიზარდოს ერთით ან არ გაიზარდოს და j
ყოველთვის იზრდება. ქვემასივის თითოეულ ელემენტზე განხორციელებული კოდის ხაზების რაოდენობა არის მუდმივი (კონსტანტა). ვინაიდან ქვემასივს აქვს ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.
გსურთ, შეუერთდეთ დისკუსიას?
პოსტები ჯერ არ არის.