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

კომპიუტერული მეცნიერება

კურსი: კომპიუტერული მეცნიერება > თემა 1

გაკვეთილი 9: სწრაფი დახარისხება

სწრაფი სორტირების მიმოხილვა

როგორც შერწყმით სორტირება, სწრაფი სორტირებაც იყენებს „დაყავი და იბატონეს“ და, შესაბამისად, ის არის რეკურსიული ალგორითმი. სწრაფი სორტირება შერწყმით სორტირებისაგან ცოტა უფრო სხვანაირად იყენებს „დაყავი და იბატონეს“ პრინციპს. შერწყმით სორტირებაში დაყოფის ნაბიჯი თითქმის არაფერს აკეთებს და ნამდვილი საქმე გაერთიანების ნაბიჯში სრულდება. სწრაფი სორტირება პირიქითაა: ნამდვილი საქმე კეთდება დაყოფის ნაბიჯში. ფაქტობრივად, გაერთიანების ნაბიჯში სწრაფი სორტირება აბსოლუტურად არაფერს აკეთებს.

სწრაფ სორტირებას კიდევ აქვს რამდენიმე სხვა განსხვავება შერწყმით სორტირებასთან. სწრაფი სორტირება ადგილზე მუშაობს და მისი მუშაობის უარესი დრო არის ისეთივე ცუდი, როგორიც შერჩევით სორტირებისა და ჩასმით სორტირების:

Θ (n^{2})

. მაგრამ მისი საშუალო შემთხვევის მუშაობის დრო არის იმდენად კარგი, რამდენადაც შერწყმით სორტირების:

Θ (n \log_{2} n)

მაშინ რაში გვჭირდება სწრაფი სორტირება, თუ შერწყმით სორტირება ისედაც მინიმუმ ამდენადვე კარგად მუშაობს? ეს იმიტომ, რომ დიდ-Θ ნოტაციაში დამალული მუდმივი მამრავლი სწრაფი სორტირებისთვის საკმაოდ კარგია. პრაქტიკაში სწრაფი სორტირება უკეთ მუშაობს, ვიდრე შერწყმით სორტირება და ის გაცილებით უკეთ მუშაობს, ვიდრე შერჩევით სორტირება და ჩასმით სორტირება.

აი, როგორ იყენებს სწრაფი სორტირება დაყავი და იბატონეს. როგორც შერწყმით სორტირების შემთხვევაში, იფიქრეთ ქვემასივ 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].

აი, როგორ მიმდინარეობს სწრაფი სორტირების მთლიანი ალგორითმი. მასივის გალურჯებული პოზიციები იყვნენ პივოტები წინა რეკურსიულ გამოძახებებში და ამიტომ ამ პოზიციებზე მყოფ მნიშვნელობებს აღარც შევამოწმებთ და აღარც გადავაადგილებთ:

დიაგრამა, რომელზეც ნაჩვენებია მასივის სწრაფი სორტირების გამოყენებით სორტირების ხუთი ნაბიჯი.

მასივი იწყებს ელემენტებით [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], ინდექსი p მიუთითებს პირველ ელემენტზე და ინდექსი r მიუთითებს ბოლო ელემენტზე.
მასივის ელემენტები ახლა დალაგებულია შემდეგნაირად: [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. მასივს ახლა აქვს ინდექსი q, რომელიც მეოთხე ელემენტზე მიუთითებს, რომელიც შეიცავს მნიშვნელობა 6-ს.
მასივის ელემენტები არც ასე არიან დალაგებული: [2, 3, 5, 6, 7, 9, 10, 11, 14, 12]. მასივს ახლა აქვს რამდენიმე ინდექსი სახელად p, q და r. პირველი p მიუთითებს მეორე ელემენტზე, პირველი r მიუთითებს მესამე ელემენტზე. მეორე p მიუთითებს მეხუთე ელემენტზე, მეორე q მიუთითებს მერვე ელემენტზე და მეორე p მიუთითებს ბოლო ელემენტზე.
მასივის ელემენტები ახლა დალაგებულია შემდეგნაირად: [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. პირველი p და r წყვილი მიუთითებენ პირველ ელემენტზე, მეორე p და r წყვილი მიუთითებენ მესამე ელემენტზე. მესამე p მიუთითებს მეხუთე ელემენტზე, q და მესამე r მიუთითებენ მე-7 ელემენტზე. მეოთხე p და q მიუთითებენ მეცხრე ელემენტზე და მეოთხე r მიუთითებს ბოლო ელემენტზე.
მასივის ელემენტები ისევ დალაგებულია, როგორც: [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. პირველი p მიუთითებს მეხუთე ელემენტზე, პირველი q და პირველი r მიუთითებენ მეექვსე ელემენტზე. p და r წყვილი მიუთითებს ბოლო ელემენტზე.
მასივის ელემენტები ისევ დალაგებულია, როგორც: [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. ერთი p და r წყვილი მიუთითებს მეხუთე ელემენტზე.

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

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

შესვლა

დავალაგოთ:

პოსტები ჯერ არ არის.

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