ძირითადი მასალა
კომპიუტერული მეცნიერება
კურსი: კომპიუტერული მეცნიერება > თემა 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.
გსურთ, შეუერთდეთ დისკუსიას?
პოსტები ჯერ არ არის.