ძირითადი მასალა
კომპიუტერული მეცნიერება
კურსი: კომპიუტერული მეცნიერება > თემა 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]
-ში:n-ელემენტიანი ქვემასივის დაყოფას ესაჭიროება \Theta, left parenthesis, n, right parenthesis დრო. თითოეული ელემენტი
A[j]
ედრება პივოტს ერთჯერ. A[j]
შეიძლება, წაენაცვლოს ან არ წაენაცვლოს A[q]
-ს, q
შეიძლება, გაიზარდოს ერთით ან არ გაიზარდოს და j
ყოველთვის იზრდება. ქვემასივის თითოეულ ელემენტზე განხორციელებული კოდის ხაზების რაოდენობა არის მუდმივი (კონსტანტა). ვინაიდან ქვემასივს აქვს n ცალი ელემენტი, დაყოფისთვის საჭირო დრო არის \Theta, left parenthesis, n, right parenthesis: წრფივ დროში დაყოფა.ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.
გსურთ, შეუერთდეთ დისკუსიას?
პოსტები ჯერ არ არის.