სწრაფი სორტირების ანალიზი

როგორ ხდება, რომ სწრაფი სორტირების უარესი და საშუალო შემთხვევების სამუშაო დროები განსხვავებულია? დავიწყოთ უარესი შემთხვევის სამუშაო დროის განხილვით. წარმოიდგინეთ, რომ ძალიან არ გაგვიმართლა და დანაწევრების ზომები ძალიან დაუბალანსებელია. კერძოდ, წარმოიდგინეთ, რომ partition ფუნქციის მიერ შერჩეული პივოტი არის ყოველთვის უმცირესი ან უდიდესი $n$‍ ელემენტიან ქვემასივში. მაშინ ერთ-ერთი დანაწევრებული ნაწილი არ შეიცავს არც ერთ ელემენტს და მეორე დანაწევრებული ნაწილი შეიცავს $n-1$‍ ელემენტს — ყველას, გარდა პივოტისა. შესაბამისად, რეკურსიულ გამოძახებები იქნება 0 და $n-1$‍ ზომის ქვემასივებზე.

როგორც შერწყმით სორტირებაში, $n$‍ ელემენტიან ქვემასივზე მოცემულ რეკურსიულ გამოძახებაზე დრო არის $\mathrm{\Theta }(n)$‍. შერწყმით სორტირების შემთხვევაში ეს იყო შერწყმის დრო, მაგრამ სწრაფი სორტირების შემთხვევაში ეს არის დანაწევრებისთვის საჭირო დრო.

როდესაც სწრაფ სორტირებას აქვს ყველაზე უფრო დაუბალანსებელი დანაწევრებები, თავდაპირველ გამოძახებას ესაჭიროება $cn$‍ დრო რაიმე მუდმივა $c$‍-სთვის, რეკურსიული გამოძახება $n-1$‍ ელემენტზე საჭიროებს $c(n-1)$‍ დროს, რეკურსიული გამოძახება $n-2$‍ ელემენტზე საჭიროებს $c(n-2)$‍ დროს და ა.შ. აქ მოცემულია ხე ქვეამოცანების ზომებისთვის მათი შესაბამისი დანაწევრების დროებთან ერთად:

როდესაც ვაჯამებთ დანაწევრების დროებს თითოეული დონისთვის, ვიღებთ

$1+2+3+\cdots +n$‍ არითმეტიკული მიმდევრობაა და ბოლო ხაზი ასე მივიღეთ, როგორც ეს ვნახეთ შერჩევითი სორტირების ანალიზისას. (ვაკლებთ 1-ს, რადგან სწრაფი სორტირების შემთხვევაში აჯამვა იწყება 2-იდან და არა 1-იდან.) გვაქვს დაბალი თანრიგის მქონე წევრები და მუდმივი კოეფიციენტები, მაგრამ, როდესაც ვიყენებთ დიდ-Θ ნოტაციას, მათ უგულებელვყოფთ. დიდ-Θ ნოტაციით სწრაფი სორტირების უარესი სამუშაო დრო არის $\mathrm{\Theta }(n^2)$‍.

სწრაფი სორტირების საუკეთესო შემთხვევა გვხვდება მაშინ, როცა დანაწევრებები მაქსიმალურად თანაბრადაა დაბალანსებული: მათი ზომები ან ტოლია, ან ერთით განსხვავდება ერთმანეთისგან. პირველი შემთხვევა გვხვდება მაშინ, როცა მასივს აქვს კენტი რაოდენობის ელემენტები და პივოტი არის დანაწევრების შემდეგ ზუსტად შუაში და თითოეულ დანაწევრებას აქვს $(n-1)/2$‍ ელემენტი. მეორე შემთხვევა გვხვდება მაშინ, როცა მასივს აქვს ლუწი $n$‍ რაოდენობის ელემენტები და ერთ დანაწევრებას აქვს $n/2$‍ ელემენტი და მეორე დანაწევრებას აქვს $n/2-1$‍. ამ შემთხვევებიდან თითოეულში თითოეულ დანაწევრებას აქვს მაქსიმუმ $n/2$‍ ელემენტი და ქვეამოცანების ზომების ხე საკმაოდ წააგავს შერწყმით სორტირების ქვეამოცანების ზომების ხეს, ხოლო დანაწევრების დროები წააგავს შერწყმის დროებს:

დიდი-Θ ნოტაციის გამოყენებით ვიღებთ იმავე შედეგს, რაც მივიღეთ შერწყმით სორტირებისთვის: $\mathrm{\Theta }(n{\log }_{2}n)$‍.

იმის ჩვენება, რომ საშუალო შემთხვევის სამუშაო დროც არის $\mathrm{\Theta }(n{\log }_{2}n)$‍ საჭიროებს საკმაოდ დიდი დოზით მათემატიკას და ამიტომ ამას არ გავაკეთებთ. მაგრამ გარკვეული ინტუიციის გამომუშავება შეგვიძლია რამდენიმე სხვა შემთხვევაზე შეხედვით, რათა გავიგოთ, რატომ შეიძლება, რომ ის იყოს $O(n{\log }_{2}n)$‍. (როგორც კი გვაქვს $O(n{\log }_{2}n)$‍, $\mathrm{\Theta }(n{\log }_{2}n)$‍ ზღვარი ავტომატურად გამომდინარეობს, რადგან საშუალო შემთხვევის სამუშაო დრო ვერ იქნება საუკეთესო შემთხვევის სამუშაო დროზე უკეთესი.) პირველ ყოვლისა, წარმოვიდგინოთ, რომ ყოველთვის ვერ ვიღებთ თანაბრად დაბალანსებულ დანაწევრებებს, მაგრამ ყოველთვის ვიღებთ უარეს შემთხვევაში სამი-ერთზე დაყოფას. ანუ, წარმოიდგინეთ, რომ ყოველ დანაწევრებაზე ერთ მხარეს ხვდება $3n/4$‍ ელემენტი და მეორე მხარეს ხვდება $n/4$‍ (იმისთვის, რომ საქმე მათემატიკურად არ გავირთულოთ, ნუ ვიდარდებთ პივოტზე). მაშინ ქვეამოცანებისა და დანაწევრებების დროების ხე შემდეგნაირი იქნებოდა:

თითოეული წვეროს მარცხენა შვილობილი წარმოადგენს ქვეამოცანის ზომას, რომელიც უდრის მისი ზომის 1/4-ს, ხოლო მისი მარჯვენა შვილობილი წარმოადგენს ქვეამოცანის ზომას, რომელიც არის მისი ზომის 3/4. ვინაიდან უფრო პატარა ქვეამოცანები არიან მარცხნივ, მარცხენა შვილობილების გზის მიყოლით ყველაზე უფრო მალე ჩავდივართ ფუძიდან ერთი ზომის ქვეამოცანამდე, ვიდრე ნებისმიერი სხვა გზის გაყოლით ჩავიდოდით. როგორც ფიგურაზე ხედავთ, ${\log }_{4}n$‍ დონის შემდეგ ჩამოვდივართ 1 ზომის ქვეამოცანამდე. რატომ ${\log }_{4}n$‍ დონე? დავიწყოთ ფიქრი 1 ზომის ქვეამოცანით დაწყებით და შემდეგ მისი გამრავლებით 4-ზე მანამ, სანამ მივალთ $n$‍-მდე. სხვა სიტყვებით, ჩვენ ვსვამთ შემდეგ კითხვას: $x$‍-ის რა მნიშვნელობისთვის არის $4^x=n$‍? პასუხი არის ${\log }_{4}n$‍. მარჯვენა შვილობილების გზაზე გაყოლის შემთხვევაში რა ხდება? ეს ფიგურა გვაჩვენებს, რომ დაგვჭირდება ${\log }_{4/3}n$‍ დონის გავლა იმისთვის, რომ 1 ზომის ქვეამოცანამდე ჩამოვიდეთ. რატომ ${\log }_{4/3}n$‍ დონე? ვინაიდან ყოველი მარჯვენა შვილობილი არის მის ზემოთ მყოფი წვეროს 3/4 (მისი მშობელი წვერო), ყოველი მშობელი არის 4/3-ჯერ მის მარჯვნივ მყოფი შვილობილი. ისევ ვიფიქროთ 1-ის ზომის ქვეამოცანით დაწყებით და ამ ზომის 4/3-ზე გამრავლებით მანამ, სანამ მივალთ $n$‍-მდე. $x$‍-ის რა მნიშვნელობისთვის არის $(4/3{)}^x=n$‍? პასუხია ${\log }_{4/3}n$‍.

პირველი ${\log }_{4}n$‍-დან ყოველ დონეზე არის $n$‍ წვერო (შეგახსენებთ, აქ ვთვლით პივოტებსაც, რომლებიც რეალურად დანაწევრებაში აღარ მონაწილეობენ) და, შესაბამისად, დანაწევრების ჯამური დრო ამ დონეებიდან თითოეულისთვის არის $cn$‍. მაგრამ რას იტყვით დანარჩენ დონეებზე? თითოეულს აქვს n-ზე ნაკლები დონე და, შესაბამისად, დანაწევრების დრო ყოველი დონისთვის არის მაქსიმუმ $cn$‍. ჯამში სულ არის ${\log }_{4/3}n$‍ დონე და, შესაბამისად დანაწევრების ჯამური დრო არის $O(n{\log }_{4/3}n)$‍. არსებობს შემდეგნაირი მათემატიკური ფაქტი

ნებისმიერი დადებითი რიცხვებისთვის $a$‍, $b$‍ და $n$‍. ვთქვათ, $a=4/3$‍ და $b=2$‍, მაშინ მივიღებთ

და, შესაბამისად, ${\log }_{4/3}n$‍ და ${\log }_{2}n$‍ განსხვავდებიან მხოლოდ ${\log }_2(4/3)$‍ მამრავლით, რაც მუდმივი რიცხვია. ვინაიდან დიდი-O ნოტაციის გამოყენებისას მუდმივი მამრავლები არ გვაინტერესებს, შეგვიძლია, ვთქვათ, რომ თუ ყველა დანაწევრება არის სამი-ერთზე, მაშინ სწრაფი სორტირების ალგორითმის სამუშაო დრო არის $O(n{\log }_{2}n)$‍, თუმცა უფრო დიდი მუდმივი მამრავლებით, ვიდრე ეს საუკეთესო შემთხვევაში იქნებოდა.

რამდენად ხშირად ვნახავთ სამი-ერთზე ან უკეთეს დაყოფას? ეს დამოკიდებულია იმაზე, თუ როგორ ვირჩევთ პივოტს. ვთქვათ, პივოტს აქვს თანაბარი შანსი, რომ $n$‍ ელემენტიან მასივში დანაწევრების შემდეგ ნებისმიერ ადგილას მოხვდეს. მაშინ იმისთვის, რო მივიღოთ სამი-ერთზე ან უკეთესი დაყოფა, პივოტი უნდა იყოს სადღაც „შუა ნახევარში“:

ასე რომ, თუ პივოტს აქვს თანაბარი შანსი იმისა, რომ ქვემასივში ნებისმიერ ადგილზე მოხვდეს დაყოფის (დანაწევრების) შემდეგ, უარეს შემთხვევაში სამი-ერთზე დაყოფის მიღების ალბათობა არის 50%. სხვა სიტყვებით, სამი-ერთზე ან უკეთეს დაყოფას მივიღებთ შემთხვევების დაახლოებით ნახევარში (საშუალოდ).

კიდევ ერთი შემთხვევა, რომელსაც შევხედავთ იმის გასაგებად, თუ რატომა რის სწრაფი სორტირების ალგორითმის საშუალო შემთხვევის სამუშაო დრო $O(n{\log }_{2}n)$‍ არის შემდეგი: რა მოხდება იმ შემთხვევაში, თუ შემთხვევების იმ ნახევარში, როცა ვერ ვიღებთ სამი-ერთზე დაყოფას ვიღებთ ყველაზე უარეს დაყოფას. ვთქვათ, რომ სამი-ერთზე და ყველაზე უარესი დაყოფა ერთმანეთს ენაცვლებიან და ვიფიქროთ წვეროზე ხეში $k$‍ ელემენტიანი ქვემასივით. მაშინ ვნახავდით ხის ნაწილს, რომელიც ამდაგვარად გამოიყურება:

ამის ნაცვლად:

ასე რომ, იმ შემთხვევაშიც კი, თუ შემთხვევების ნახევარში მივიღებდით ყველაზე უარეს დაყოფას და მეორე ნახევარში მივიღებდით სამი-ერთზე ან უკეთეს დაყოფას, სამუშაო დრო იქნებოდა დაახლოებით ორი გამრავლებული მხოლოდ სამი-ერთზე დაყოფის შემთხვევის სამუშაო დროზე. კიდევ ერთხელ, ეს მხოლოდ მუდმივი მამრავლია და ის შთაინთქმება დიდ-O ნოტაციაში და, შესაბამისად, იმ შემთხვევაში, როცა სამი-ერთზე და ყველაზე უარეს დაყოფებს ვანაცვლებთ სამუშაო დრო არის $O(n{\log }_{2}n)$‍.

გახსოვდეთ, რომ ეს არ არის მკაცრი მათემატიკური ანალიზი, მაგრამ ის გიქმნით ინტუიციურ წარმოდგენას იმის შესახებ, თუ რატომ შეიძლება, საშუალო შემთხვევის სამუშაო დრო იყოს $O(n{\log }_{2}n)$‍.

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

არ არის აუცილებელი, ყოველ ჯერზე ყველაზე მარჯვენა ელემენტი აირჩიოთ პივოტად ქვემასივში. ამის ნაცვლად შეგიძლიათ, შემთხვევითად აირჩიოთ ელემენტი ქვემასივში და ეს ელემენტი გამოიყენოთ პივოტად. მაგრამ მოიცათ — partition ფუნქცია თვლის, რომ ქვემასივის ყველაზე მარჯვენა პოზიციაზე მდებარეობს პივოტი. არაუშავს — უბრალოდ წაანაცვლეთ თქვენ მიერ პივოტად შერჩეული ელემენტი ყველაზე მარჯვნივ მყოფ ელემენტთან და შემდეგ ისევე დაანაწევრეთ, როგორც წინათ. თუ თქვენმა მეტოქემ წინასწარ არ იცის, როგორ ირჩევთ შემთხვევით მდებარეობებს ქვემასივში, თქვენ იმარჯვებთ!

რეალურად, თუ ცოტა უფრო მეტს მოინდომებთ, შეგიძლიათ, გაზარდოთ სამი-ერთზე დაყოფის მიღების შანსები. შემთხვევითად შეარჩიეთ არა ერთი, არამედ სამი წერტილი ქვემასივიდან და ამ სამი ელემენტის მედიანა აირჩიეთ პივოტად (წაანაცვლეთ ის ყველაზე მარჯვნივ მდებარე ელემენტთან). მედიანაში ვგულისხმობთ ამ სამიდან იმ ელემენტს, რომლის მნიშვნელობაც არის შუაში. ჩვენ არ დავამტკიცებთ, თუ რატომ, მაგრამ თუკი სამი შემთხვევითად შერჩეული ელემენტიდან აირჩევთ მედიანას პივოტად, მაშინ გაქვთ 68.75% ალბათობა (11/16) იმისა, რომ მიიღოთ სამი-ერთზე დაყოფა ან უკეთესი. უფრო შორსაც შეგიძლიათ წასვლა. თუ აირჩევთ ხუთ ელემენტს შემთხვევითად და აირჩევთ მედიანას პივოტად, უარეს შემთხვევაში სამი-ერთზე დაყოფის მიღების შანსი იზრდება 79.3%-მდე (203/256). თუ აიღებთ მედიანას შვიდი შემთხვევითად შერჩეული ელემენტიდან, მაშინ ის ადის 85.9%-მდე (1759/2048). 9 ელემენტის მედიანა? დაახლოებით 90.2% (59123/65536). 11 ელემენტის? About 93.1% (488293/524288). ზოგადი სურათი უკვე გასაგებია. რა თქმა უნდა, დიდი რაოდენობით ელემენტების შემთხვევითად არჩევა და მათი მედიანის აღება ყოველთვის დადებით შედეგს არ გვაძლევს, რადგან ამის გაკეთებისთვის დახარჯული დრო შეიძლება, არ გვიღირდეს თითქმის ყოველთვის კარგი დაყოფის მიღებად.

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