Quicksort როგორც პროგრამირების მეთოდი

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

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

Quicksort არის ძალიან გავრცელებული, ეს შეიძლება იყოს ყველგან. მის საფუძველზე მეთოდით ხორციელდება TList.Sort, იმყოფება ყველა ვერსიები (გარდა 1) Delphi, ბიბლიოთეკის ფუნქცია დრო დასჭირდა დაასრულებს, qsort in C ++.

ძირითადი პრინციპი ოპერაცია შეიძლება ჩამოყალიბდეს როგორც "დაყავი და იბატონე". ეს ხდება არღვევს სია ორ ჯგუფად და დახარისხებულია თითოეული ნაწილი თავისთავად. აქედან გამომდინარეობს, რომ უფრო მეტი ყურადღება უნდა მიექცეს გამოყოფის პროცესს, რომლის დროსაც შემდეგ ხდება: განისაზღვრება ბაზის ელემენტს და შედარებით გადალაგება მთელი მისი სია. ჩამონტაჟებული მარცხნივ ჯგუფის კანდიდატი, რომლის ღირებულება ნაკლებია, ვიდრე ყველა სხვა გადაცემა წესები. გამოდის, რომ მთავარი ელემენტია დახარისხებული სია თავის კანონიერ ადგილას. შემდეგი ეტაპი - გამოწვევა რეკურსიული დახარისხება ფუნქციები ორივე მხარეს ელემენტები შედარებით ბაზა. ეს დამთავრდა პროცესში მუშაობს მხოლოდ იმ შემთხვევაში, სია შეიცავს მხოლოდ ერთ ელემენტს, რომელიც უნდა იყოს დახარისხებული. ამდენად, რათა დაეუფლონ პროგრამირების ფუნქცია, როგორც სწრაფი დალაგების, აუცილებელია იცოდეს მუშაობა ქვედა დონის ალგორითმები: ა) არჩევანი ბაზაზე წევრი; ბ) სიაში ყველაზე ეფექტური permutation წარმოების ორი კომპლექტი პატარა და დიდი ღირებულებები.

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

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

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