ძირითადი მასალა
კურსი: კომპიუტერული მეცნიერება > თემა 1
გაკვეთილი 9: სწრაფი დახარისხებასწრაფი სორტირების მიმოხილვა
Google–ის საკლასო ოთახიროგორც შერწყმით სორტირება, სწრაფი სორტირებაც იყენებს „დაყავი და იბატონეს“ და, შესაბამისად, ის არის რეკურსიული ალგორითმი. სწრაფი სორტირება შერწყმით სორტირებისაგან ცოტა უფრო სხვანაირად იყენებს „დაყავი და იბატონეს“ პრინციპს. შერწყმით სორტირებაში დაყოფის ნაბიჯი თითქმის არაფერს აკეთებს და ნამდვილი საქმე გაერთიანების ნაბიჯში სრულდება. სწრაფი სორტირება პირიქითაა: ნამდვილი საქმე კეთდება დაყოფის ნაბიჯში. ფაქტობრივად, გაერთიანების ნაბიჯში სწრაფი სორტირება აბსოლუტურად არაფერს აკეთებს.
სწრაფ სორტირებას კიდევ აქვს რამდენიმე სხვა განსხვავება შერწყმით სორტირებასთან. სწრაფი სორტირება ადგილზე მუშაობს და მისი მუშაობის უარესი დრო არის ისეთივე ცუდი, როგორიც შერჩევით სორტირებისა და ჩასმით სორტირების:
მაშინ რაში გვჭირდება სწრაფი სორტირება, თუ შერწყმით სორტირება ისედაც მინიმუმ ამდენადვე კარგად მუშაობს? ეს იმიტომ, რომ დიდ-Θ ნოტაციაში დამალული მუდმივი მამრავლი სწრაფი სორტირებისთვის საკმაოდ კარგია. პრაქტიკაში სწრაფი სორტირება უკეთ მუშაობს, ვიდრე შერწყმით სორტირება და ის გაცილებით უკეთ მუშაობს, ვიდრე შერჩევით სორტირება და ჩასმით სორტირება.
აი, როგორ იყენებს სწრაფი სორტირება დაყავი და იბატონეს. როგორც შერწყმით სორტირების შემთხვევაში, იფიქრეთ ქვემასივ
array[p..r]-ს დასორტირებაზე, სადაც თავდაპირველად ქვესიმრავლე არის array[0..n-1].- დაყავით ქვემასივში ნებისმიერი ელემენტის არჩევით
array[p..r]. დაარქვით ამ ელემენტს პივოტი.გადაალაგეთ ელემენტებიarray[p..r]-ში ისე, რომ ყველა ელემენტიarray[p..r]-ში, რომელიც უფრო მცირე ან ნაკლებია პივოტზე იყოს მის მარცხნივ და პივოტზე მეტი ყველა ელემენტი იყოს მის მარჯვნივ. ამ პროცედურას ვეძახით დანაწევრებას (დაყოფას). ამ მომენტისთვის არა აქვს მნიშვნელობა, რა მიმდევრობითაა ელემენტები დალაგებული პივოტის მარცხნივ მდებარე ელემენტები ერთმანეთის მიმართ და იგივე რამ სრულდება პივოტის მარჯვნივ მდებარე ელემენტებისთვისაც. ჩვენ მხოლოდ გვაინტერესებს, რომ თითოეული ელემენტი იყოს პივოტისგან სწორ მხარეს ნებისმიერ ადგილას.ვარჯიშისთვის, ყოველთვის შევარჩევთ ქვემასივში ყველაზე მარჯვნივ მდებარე ელემენტს პივოტად,array[r]. ანუ, მაგალითად, თუ ქვემასივი შედგება [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]-ისგან, მაშინ პივოტად ვირჩევთ 6-ს. დანაწევრების შემდეგ ქვემასივი შეიძლება, ასე გამოიყურებოდეს: [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. ვთქვათ,qიყოს ინდექსი, რომელზეც პივოტი დარჩება. - იბატონეთ ქვემასივის რეკურსიულად დასორტირებით
array[p..q-1](ყველა ელემენტი პივოტის მარცხნივ, რომლებიც ნაკლები ან ტოლი უნდა იყოს პივოტზე) დაarray[q+1..r](ყველა ელემენტი პივოტის მარჯვნივ, რომლებიც მეტი ან ტოლი უნდა იყოს პივოტზე). - გავაერთიანოთ არაფრის გაკეთებით. როგორც კი ბატონობის ნაბიჯი რეკურსიულად დაასორტირებს, დამთავრებული გვაქვს. რატომ? ყველა ელემენტი პივოტის მარცხნივ,
array[p..q-1]-ში, არის ნაკლები ან ტოლი პივოტზე და დასორტირებული და ყველა ელემენტი პივოტის მარჯვნივ,array[q+1..r]-ში, არის პივოტზე მეტი და დასორტირებული. ელემენტები მასივშიarray[p..r]დასორტირებული არიან, სხვანაირად არ შეუძლიათ!იფიქრეთ ჩვენს მაგალითზე. პივოტის მარცხნივ და მარჯვნივ ელემენტების რეკურსიულად დასორტირების შემდეგ, ქვემასივი პივოტის მარცხნივ არის [2, 3, 5] და ქვემასივი პივოტის მარჯვნივ არის [7, 9, 10, 11, 12, 14]. ასე რომ, ქვემასივს აქვს [2, 3, 5], შემდეგ 6, შემდეგ [7, 9, 10, 11, 12, 14]. ქვემასივი დასორტირებულია.
ბაზისები არის ქვემასივები ორზე ნაკლები ელემენტით, ზუსტად ისე, როგორ შერწყმით სორტირების შემთხვევაში. შერწყმით სორტირებაში ვერასდროს იხილავთ უელემენტო ქვემასივს, მაგრამ სწრაფ სორტირებაში შეიძლება, შეგვხვდეს ასეთი ქვემასივი, თუ ყველა სხვა ელემენტი ქვემასივში არის პივოტზე ნაკლები ან ყველა სხვა ელემენტი ქვემასივში არის პივოტზე მეტი.
დავუბრუნდეთ ბატონობის ნაბიჯს და გავიაროთ ქვემასივების რეკურსიული სორტირება. პირველი დანაწევრების შემდეგ გვაქვს ქვემასივები [5, 2, 3] და [12, 7, 14, 9, 10, 11], პივოტი არის 6.
იმისთვის, რომ დავასორტიროთ ქვემასივი [5, 2, 3], პივოტად ვირჩევთ 3-ს. დანაწევრების შემდეგ გვაქვს [2, 3, 5]. ქვემასივი [2], პივოტის მარცხნივ, არის ბაზისი, ვბრუნდებით, ასევეა ქვემასივი [5], პივოტის მარჯვნივ.
ქვემასივი [12, 7, 14, 9, 10, 11]-ის დასასორტირებლად პივოტად ვირჩევთ 11-ს. დანაწევრების შემდეგ გვაქვს [7, 9, 10] პივოტის მარცხნივ და [14, 12] მის მარჯვნივ. შემდეგ ქვემასივები სორტირდება,
შედეგად გვაძლევს [7, 9, 10]-ს, შემდეგ 11, შემდეგ [12, 14].
აი, როგორ მიმდინარეობს სწრაფი სორტირების მთლიანი ალგორითმი. მასივის გალურჯებული პოზიციები იყვნენ პივოტები წინა რეკურსიულ გამოძახებებში და ამიტომ ამ პოზიციებზე მყოფ მნიშვნელობებს აღარც შევამოწმებთ და აღარც გადავაადგილებთ:
ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.
გსურთ, შეუერთდეთ დისკუსიას?
პოსტები ჯერ არ არის.