If you're seeing this message, it means we're having trouble loading external resources on our website.

თუ ვებფილტრს იყენებთ, დარწმუნდით, რომ *.kastatic.org და *.kasandbox.org დომენები არ არის დაბლოკილი.

ძირითადი მასალა

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

სწრაფი სორტირების ნამდვილი საქმე კეთდება დაყოფის ნაბიჯში, რომელიც ყოფს მასივს 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-ს გამყოფი ხაზი ერთი პოზიციით მარჯვნივ გადაინაცვლებს:
დიაგრამა, რომელზეც ნაჩვენები ქვემასივის დაყოფის ერთი ნაბიჯი. ქვემასივი იწყებს ინდექს p-ზე და ჯგუფ L-ში ოთხი ელემენტით, შემდეგ გვაქვს ინდექსი q და 6 ელემენტი ჯგუფში G, შემდეგ ინდექსი j და 5 ელემენტი ჯგუფში U, ბოლოს - ინდექსი r. ამ ნაბიჯის შემდეგ ქვემასივი თითქმის იგივეა, მაგრამ ჯგუფ G-ს აქვს 7 ელემენტი, ჯგუფ U-ს აქვს 4 ელემენტი და ინდექსი j მიუთითებს ჯგუფი U-ს პირველ ელემენტზე.
თუ საპირისპირო შემთხვევა მოხდა და A[j] ნაკლებია ან ტოლია პივოტზე, მაშინ წავანაცვლებთ A[j]-სა და A[q] (ყველაზე მარცხნივ მყოფი ელემენტი ჯგუფ G-ში), ერთით გავზრდით j-ს და ერთით გავზრდით q-ს, L და G ჯგუფების გამყოფ ხაზს გადავასრიალებთ და აგრეთვე გადავასრიალებთ G და U ჯგუფების გამყოფ ხაზს ერთი პოზიციით მარჯვნივ:
დიაგრამა, რომელზეც ნაჩვენებია ქვემასივის დაყოფის ერთი ნაბიჯი. ქვემასივი იწყებს ინდექს p-ზე და ჯგუფ L-ში ოთხი ელემენტით, შემდეგ გვაქვს ინდექსი q და 6 ელემენტი ჯგუფში G, შემდეგ ინდექსი j და 5 ელემენტი ჯგუფში U, ბოლოს — ინდექსი r. ამ ნაბიჯის შემდეგ ქვემასივს ახლა აქვს ხუთი ელემენტი ჯგუფში L (ბოლო ელემენტს უკავია j ინდექსზე მყოფი წინა მნიშვნელობა) და ოთხი ელემენტი ჯგუფ U-ში.
როგორც კი პივოტამდე მივალთ, ჯგუფი U ცარიელია. პივოტს ვუცვლით ადგილს ჯგუფ G-ში მყოფ ყველაზე მარცხნივ ელემენტთან: წავანაცვლოთ A[r] და A[q]. ეს წანაცვლება ჩასვამს პივოტს L და G ჯგუფებს შორის და ის მაინც სწორად იქცევა იმ შემთხვევაშიც კი, როცა ჯგუფი L ან ჯგუფი G ცარიელია.
partition ფუნქცია, რომელიც ამ იდეის იმპლემენტაციას ახდენს აგრეთვე აბრუნებს ინდექს q-ს, სადაც ბოლოს დასვა პივოტი, რათა quicksort ფუნქციამ, რომელიც მას იძახებს, იცოდეს, სად მოხდა დაყოფები.
აი, ნაბიჯები [12, 7, 14, 9, 10, 11] ქვემასივის დაყოფაში array[4..9]-ში:
n-ელემენტიანი ქვემასივის დაყოფას ესაჭიროება Θ(n) დრო. თითოეული ელემენტი A[j] ედრება პივოტს ერთჯერ. A[j] შეიძლება, წაენაცვლოს ან არ წაენაცვლოს A[q]-ს, q შეიძლება, გაიზარდოს ერთით ან არ გაიზარდოს და j ყოველთვის იზრდება. ქვემასივის თითოეულ ელემენტზე განხორციელებული კოდის ხაზების რაოდენობა არის მუდმივი (კონსტანტა). ვინაიდან ქვემასივს აქვს n ცალი ელემენტი, დაყოფისთვის საჭირო დრო არის Θ(n): წრფივ დროში დაყოფა.

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

გსურთ, შეუერთდეთ დისკუსიას?

პოსტები ჯერ არ არის.
გესმით ინგლისური? დააწკაპუნეთ აქ და გაეცანით განხილვას ხანის აკადემიის ინგლისურენოვან გვერდზე.