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

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

image: ბუშტები

დღეს ჩვენ ვისაუბრებთ უმარტივესზე დახარისხების გაცვლა.

თუ ვინმე დაინტერესდება, გეტყვით, რომ არის სხვა კლასები - შერჩევის დალაგება, ჩასმის დალაგება, შერწყმა დახარისხება, განაწილების დახარისხება, ჰიბრიდული სახეობებიდა პარალელური ჯიშები. სხვათა შორის, არსებობს ასევე ეზოთერული დახარისხება. ეს არის სხვადასხვა ყალბი, ფუნდამენტურად არარეალიზებადი, კომიკური და სხვა ფსევდო-ალგორითმები, რომელთა შესახებაც დავწერ რამდენიმე სტატიას "IT Humor" ჰაბში.

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

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

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

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

სულელური ტიპი

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

"ნებისმიერ სულელს შეუძლია ასე დალაგება", - იტყვით და აბსოლუტურად მართალი იქნებით. ამიტომ დახარისხებას უწოდებენ "სულელურს". ამ ლექციაში ჩვენ მუდმივად გავაუმჯობესებთ და შევცვლით ამ მეთოდით. ახლა მას დროებითი სირთულე აქვს ო(n 3), ერთი შესწორების გაკეთების შემდეგ, ჩვენ უკვე მივიყვანთ ო(n 2), შემდეგ კიდევ ცოტას დავაჩქარებთ, შემდეგ ცოტას და ბოლოს მივიღებთ ო(ნჟურნალი ნ) - და ეს საერთოდ არ იქნება "სწრაფი დახარისხება"!

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

ამ შემთხვევაში ჩვენ წინაშე არაფერია ცნობილი...

ბუშტის დალაგება

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

თუ მაქსიმუმებს არა მხოლოდ ბოლომდე მივაღწევთ, არამედ მინიმუმს თავიდანვე მივაღწევთ, მაშინ წარმატებას მივაღწევთ...

შეიკერის დახარისხება

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

შეიკერის დალაგება მუშაობს ოდნავ უფრო სწრაფად, ვიდრე ბუშტების დალაგება, რადგან მაქსიმუმები და მინიმუმები მონაცვლეობით გადადიან მასივის მეშვეობით საჭირო მიმართულებებით. გაუმჯობესება, როგორც ამბობენ, აშკარაა.

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

ლუწი-კენტი დახარისხება

ამჯერად ჩვენ არ დავბრუნდებით მასივის გასწვრივ წინ და უკან, არამედ კვლავ დავუბრუნდებით სისტემატური სიარულის იდეას მარცხნიდან მარჯვნივ, მაგრამ ჩვენ მხოლოდ უფრო ფართო ნაბიჯს გადავდგამთ. პირველ უღელტეხილზე კენტი კლავიშის მქონე ელემენტები შედარებულია ლუწ ადგილებზე დაფუძნებულ მეზობლებთან (1-ლი შედარებულია მე-2-თან, შემდეგ მე-3 მე-4-თან, მე-5-ე მე-6-თან და ა.შ.). შემდეგ, პირიქით, ვადარებთ/ვცვლით „ლუწი“ ელემენტებს „კენტებთან“. შემდეგ ისევ „კენტი-ლუწი“, შემდეგ ისევ „ლუწი-კენტი“. პროცესი ჩერდება, როდესაც მასივის ზედიზედ ორი გავლის შემდეგ („კენტი-ლუწი“ და „ლუწი-კენტი“) არც ერთი გაცვლა არ მომხდარა. ასე რომ, დაალაგეს.

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

მოდით შევხედოთ ბოლო ხელახლა მორთული* ამისთვის Sortuvannya bulbashka** - დახარისხება სავარცხლის მიხედვით***. ეს მეთოდი ორგანიზებულია ძალიან სწრაფად, ო(n 2) მისი ყველაზე დიდი სირთულეა. საშუალოდ დროთა განმავლობაში გვაქვს ო(ნჟურნალი ნ), და ყველაზე კარგი, არც კი დაიჯერებთ, ო(ნ). ეს არის ძალიან ღირსეული კონკურენტი ყველა სახის ” სწრაფი ჯიშები”და ეს, გაითვალისწინეთ, რეკურსიის გამოყენების გარეშე. თუმცა, მე დავპირდი, რომ დღეს ჩვენ არ ჩავუღრმავდებით კრუიზის სიჩქარეს, ამიტომ საუბარს შევწყვეტ და პირდაპირ ალგორითმზე გადავალ.

ეს ყველაფერი კუების ბრალია

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

image: დამნაშავე კუ

სავარცხლის დახარისხება

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

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

ოპტიმალური მნიშვნელობა დადგენილია ექსპერიმენტულად და თეორიულად შემცირების ფაქტორი:

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

ეს არის ის, რაც მინდოდა გითხრათ ბუშტების დახარისხებაზე და მის მსგავსზე.

- შენიშვნები

*შემოკლებული ( უკრაინული) - გაუმჯობესება
** დალაგებულია ნათურის მიხედვით ( უკრაინული) – ბუშტის დალაგება
*** დახარისხება სავარცხლის მიხედვით ( უკრაინული) – სავარცხლის დალაგება

ერთგანზომილებიანი მასივის დახარისხების ალგორითმი „ბუშტის“ მეთოდით. ალგორითმის აღწერა. ბლოკ-სქემა და პროგრამა ტიპების მასივის ზრდის მიხედვით დახარისხებისთვის რეალური7 ელემენტისგან.

ალგორითმის აღწერა

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

როგორც წინა მარტივი შერჩევის მეთოდების შემთხვევაში, ჩვენ განმეორებით გადასვლებს ვაკეთებთ მასივის მეშვეობით, ყოველ ჯერზე ვატარებთ დარჩენილი ნაკრების უმცირეს ელემენტს და მივდივართ მასივის მარცხენა ბოლოში. თუ ცვლილების მიზნით განვიხილავთ მასივს ვერტიკალურად და არა ჰორიზონტალურად და - მცირე წარმოსახვით - წარმოვიდგინოთ ელემენტები, როგორც ბუშტები წყლის ავზში, მათი კლავიშების შესაბამისი "წონით", მაშინ მასივის თითოეული გავლა იწვევს "float" » ბუშტი მისი წონის შესაბამის დონეზე (იხ. ცხრილი 2). ეს მეთოდი საყოველთაოდ ცნობილია, როგორც ბუშტის დალაგება. მისი უმარტივესი ვერსია ნაჩვენებია პროგრამა 1-ში.

1. ბუშტების დალაგების მაგალითი

პროცედურა ბუშტუკები;

ვარ მე, ჯ: ინდექსი; x: ნივთი;

დაიწყოს ამისთვის მე := 2 რომ ნ კეთება

დასაწყისისთვის ჯ := ნ ქვემოთ მე კეთება

თუ ა[ჯ-1].გასაღები > ა[ჯ].გასაღები მაშინ

დაიწყოს x := ა[ჯ-1]; ა[ჯ-1] := ა[ჯ]; ა[ჯ] := x

დასასრული{ბუშტუკები}

1. ბუშტის დალაგება

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

12 18 42 44 55 67 94 06

დალაგდება ბუშტის მეთოდით ერთი პასით და მასივის დახარისხება

94 06 12 18 42 44 55 67

დასჭირდება შვიდი პასი. ეს არაბუნებრივი ასიმეტრია მესამე გაუმჯობესებას გვთავაზობს: თანმიმდევრული გადასასვლელების მიმართულების შეცვლას.

ბუშტების დახარისხების ანალიზი.

მარტივი გაცვლის ალგორითმში შედარებების რაოდენობაა

,

გადარიცხვების მინიმალური, საშუალო და მაქსიმალური რაოდენობა (ელემენტების მინიჭება) ტოლია

,

,

.

1. ბუშტების დახარისხების დიაგრამა.

პროგრამადახარისხება

A: მასივი რეალური;

N, j, k: მთელი რიცხვი;

WriteLn ("შეყვანის მასივი");

ამისთვის j:= 1-დან N-მდე

Write("A", j, "=");

WriteLn ("წყაროების მასივი");

ამისთვის j:= 1-დან N-მდე

ჩაწერეთ (A[j]:8:1);

ამისთვის j:= 2-დან k-მდე

თუ A > A[j] მაშინ

A := A[j];

WriteLn ("დახარისხებული მასივი");

ამისთვის j:= 1-დან N-მდე

ჩაწერეთ (A[j]:8:1);

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

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

მაგრამ არის ერთი "მაგრამ". ძებნის ალგორითმებიმუშაობა ბევრად უფრო სწრაფად უკვე დალაგებულ მონაცემთა ბაზებთან. ამ შემთხვევაში საჭიროა მხოლოდ ხაზოვანი ძებნა.

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

ამ სტატიაში მოცემულია სტანდარტული დახარისხების ალგორითმების განხორციელების მაგალითები.

შერჩევის დალაგება

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

C++ კოდი

void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i მონაცემები[k])( j = k; ) ) tmp = მონაცემები[i]; data[i] = მონაცემები[j]; მონაცემები[j] = tmp; ))

ბუშტის დალაგება

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

C++ კოდი

void SortAlgo::bubbleSort(int მონაცემები, int lenD) ( int tmp = 0; for (int i = 0;i =(i+1);j--)(თუ (მონაცემები[j]

ჩასმის დალაგება

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

ყოველ უღელტეხილზე, მოწესრიგებული რეგიონის ზომა იზრდება 1-ით, ხოლო მოუწესრიგებელი რეგიონის ზომა მცირდება 1-ით.

მთავარი მარყუჟი გადის 1-დან N-1-მდე. j-ე გამეორებისას ელემენტი [i] ჩასმულია სწორ პოზიციაში მოწესრიგებულ რეგიონში. ეს კეთდება მოწესრიგებული რეგიონის ყველა ელემენტის გადაადგილებით, რომლებიც [i]-ზე მეტია ერთ პოზიციაზე მარჯვნივ. [i] ჩასმულია სივრცეში იმ ელემენტებს შორის, რომლებიც [i]-ზე ნაკლები და [i]-ზე მეტია.

C++ კოდი

void SortAlgo::insertionSort(int data, int lenD) ( int key = 0; int i = 0; for (int j = 1;j =0 && data[i]>გასაღები)( მონაცემები = მონაცემები[i]; i = i-1; მონაცემები = გასაღები; ) )

შერწყმა დახარისხება

C++ კოდი

void SortAlgo::mergeSort(int მონაცემები, int lenD) ( if (lenD>1)( int შუა = lenD/2; int rem = lenD-შუა; int * L = ახალი int; int * R = ახალი int; for ( int i=0;i

სწრაფი დალაგება

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

C++ კოდი

void SortAlgo::quickSort(int * მონაცემები, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; თუ (lenD>1) (int * L = new int; int * R = new int; pivot = მონაცემები; for (i=0;i

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

შესავალი

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

დალაგება მანქანის და ადამიანის თვალით

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

კომპიუტერული პროგრამისგან განსხვავებით, დალაგება არ გაგიჭირდებათ, რადგან ხედავთ მთლიან სურათს და მაშინვე შეგიძლიათ გაარკვიოთ რომელი გმირი სად უნდა გადაიტანოთ, რომ სიმაღლის მიხედვით დახარისხება წარმატებით დასრულდეს. თქვენ ალბათ უკვე მიხვდით, რომ ამ მონაცემთა სტრუქტურის აღმავალი თანმიმდევრობით დასალაგებლად, უბრალოდ შეცვალეთ ჰალკისა და რკინის კაცის ადგილები:

Შესრულებულია!

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

• შეადარეთ ორი ელემენტი;
• შეცვალეთ ან დააკოპირეთ ერთი მათგანი;
• გადადით შემდეგ ელემენტზე;

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

ბუშტების დალაგების ალგორითმი

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

• თქვენ გადადიხართ ჩვენი მასივის ნულოვან ელემენტზე (Black Widow);
• შეადარეთ ნულოვანი ელემენტი (Black Widow) პირველთან (Hulk);
• თუ ელემენტი ნულოვან პოზიციაზე უფრო მაღალია, თქვენ შეცვალეთ ისინი;
• წინააღმდეგ შემთხვევაში, თუ ელემენტი ნულოვან პოზიციაზე უფრო მცირეა, თქვენ ტოვებთ მათ თავიანთ ადგილებზე;
• გადადით პოზიციაზე მარჯვნივ და გაიმეორეთ შედარება (შეადარეთ ჰალკი კაპიტანს)

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

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

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

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

ჯავაში ბუშტების დალაგების დანერგვა

იმის საჩვენებლად, თუ როგორ მუშაობს დახარისხება ჯავაში, აქ არის პროგრამის კოდი:

• ქმნის 5 ელემენტისგან შემდგარ მასივს;
• ატვირთავს მასში შურისმაძიებლების აღზევებას;
• აჩვენებს მასივის შიგთავსს;
• ახორციელებს ბუშტების დალაგებას;
• ხელახლა აჩვენებს დახარისხებულ მასივს.

შეგიძლიათ იხილოთ ქვემოთ მოცემული კოდი და გადმოწეროთ ის თქვენს საყვარელ IntelliJ IDE-ში. ის იქნება გაანალიზებული ქვემოთ: კლასი ArrayBubble ( private long a; //ბმული მასივზეპირადი int ელემენტები; //ელემენტების რაოდენობა მასივშისაჯარო ArrayBubble (int max) ( //კლასის კონსტრუქტორი a = ახალი გრძელი[მაქს]; //მაქსიმალური ზომის მასივის შექმნაელემენტები = 0; //შექმნისას მასივი შეიცავს 0 ელემენტს) საჯარო სიცარიელე შევიდა (გრძელი მნიშვნელობა) ( //ელემენტის მასივში ჩასმის მეთოდი a[ elems] = მნიშვნელობა; //მნიშვნელობის ჩასმა მასივში aელემენტები++ ; //მასივის ზომა იზრდება) საჯარო ცარიელი პრინტერი () ( //კონსოლში მასივის გამოტანის მეთოდი for (int i = 0; i< elems; i++ ) { // მასივის თითოეული ელემენტისთვისსისტემა. გარეთ. ბეჭდვა (a[i] + "" ); //გამომავალი კონსოლშისისტემა. გარეთ. println (""); //ახალი ხაზიდან ) სისტემა. გარეთ. println ( "----დასრულდეს მასივის გამომავალი----") ; ) პირადი void toSwap (int პირველი, int მეორე) ( //მეთოდი ცვლის რამდენიმე რიცხვს მასივში long dummy = a[პირველი]; //პირველი ელემენტის ჩასმა დროებით ცვლადში a[ პირველი] = a[ მეორე] ; //პირველის ნაცვლად ვსვამთ მეორე ელემენტს a[second] = მოტყუება; //მეორე ელემენტის ნაცვლად ვწერთ პირველს დროებითი მეხსიერებიდან) საჯარო void bubbleSorter () ( for (int out = elems - 1 ; out >< out; in++ ) { //შიდა მარყუჟი if (a[ in] > a[ in + 1 ] ) to Swap (in, in + 1 ) ; ) ) ) public class Main ( public static void main ( string args ) ( ArrayBubble array = new ArrayBubble ( 5 ) ; //შექმენით მასივი 5 ელემენტითმასივი. შევიდა (163); //შეავსეთ მასივიმასივი. შევიდა (300); მასივი. შევიდა (184); მასივი. შევიდა (191); მასივი. შევიდა (174); მასივი. პრინტერი (); //გამომავალი ელემენტები დახარისხებამდემასივი. bubbleSorter(); //BUBBLE SORT-ის გამოყენებამასივი. პრინტერი (); //გამოიტანეთ დახარისხებული სია ისევ) ) კოდში დეტალური კომენტარების მიუხედავად, ჩვენ მოგაწვდით პროგრამაში წარმოდგენილი ზოგიერთი მეთოდის აღწერას. ძირითადი მეთოდები, რომლებიც ახორციელებენ პროგრამაში მთავარ სამუშაოს, იწერება ArrayBubble კლასში. კლასი შეიცავს კონსტრუქტორს და რამდენიმე მეთოდს:

• into – მასივში ელემენტების ჩასმის მეთოდი;
• პრინტერი – ბეჭდავს მასივის შიგთავსს ხაზ-სტრიქონით;

toSwap – საჭიროების შემთხვევაში ცვლის ელემენტებს. ამისათვის გამოიყენება დროებითი ცვლადი დუმი, რომელშიც იწერება პირველი რიცხვის მნიშვნელობა, ხოლო მეორე ნომრის მნიშვნელობა პირველის ნაცვლად. დროებითი ცვლადის შინაარსი იწერება მეორე რიცხვზე. ეს არის ორი ელემენტის გაცვლის სტანდარტული ტექნიკა;

და ბოლოს მთავარი მეთოდი:

• bubbleSorter – რომელიც ასრულებს ძირითად სამუშაოს და ახარისხებს მასივში შენახულ მონაცემებს, კიდევ ერთხელ წარმოგიდგენთ მას ცალ-ცალკე:

  საჯარო void bubbleSorter() ( //BBUBLE SORT METHOD for (int out = elems - 1 ; out >= 1 ; out-- ) ( //გარე ციკლი for (int in = 0 ; in< out; in++ ) { //შიდა მარყუჟითუ (a[ in] > a[ in + 1 ] ) //თუ ელემენტების რიგი დარღვეულიაგაცვლა (in, in + 1 ); //გამოიძახეთ მეთოდი, რომელიც ცვლის ადგილებს } } }

აქ ყურადღება უნდა მიაქციოთ ორ მრიცხველს: გარე და შიდა. გარე გარე მრიცხველიიწყებს მნიშვნელობების გამეორებას მასივის ბოლოდან და თანდათან მცირდება ერთით ყოველი ახალი გავლისას. out ცვლადი გადაინაცვლებს მარცხნივ ყოველი ახალი გავლისას, ისე რომ არ იმოქმედოს მასივის მარჯვენა მხარეს უკვე დალაგებულ მნიშვნელობებზე. შიდა მრიცხველიმასივის დასაწყისიდან იწყებს მნიშვნელობების გამეორებას და თანდათან იზრდება ერთით ყოველ ახალ გადასასვლელზე. იზრდება მანამ, სანამ არ მიაღწევს (ბოლო ელემენტი, რომელიც უნდა გაანალიზდეს მიმდინარე უღელტეხილში). შიდა მარყუჟი ადარებს ორ მიმდებარე უჯრედს და +1-ში. თუ მაღაზიებში უფრო დიდი რიცხვია, ვიდრე +1-ში, მაშინ გამოიძახება toSwap მეთოდი, რომელიც ცვლის ორი ნომრის ადგილებს.

დასკვნა

ბუშტების დალაგების ალგორითმი ერთ-ერთი ყველაზე ნელია. თუ მასივი შედგება N ელემენტისგან, მაშინ N-1 შედარება განხორციელდება პირველ უღელტეხილზე, N-2 მეორეზე, შემდეგ N-3 და ა.შ. ანუ, უღელტეხილების საერთო რაოდენობა გაკეთდება: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2ამრიგად, დახარისხებისას ალგორითმი ასრულებს დაახლოებით 0.5x(N^2) შედარებებს. N = 5-ისთვის, შედარებების რაოდენობა იქნება დაახლოებით 10, N = 10-ისთვის შედარებების რაოდენობა გაიზრდება 45-მდე. ამრიგად, ელემენტების რაოდენობის მატებასთან ერთად, დახარისხების სირთულე მნიშვნელოვნად იზრდება:

ალგორითმის სიჩქარეზე გავლენას ახდენს არა მხოლოდ გაშვებების რაოდენობა, არამედ იმ პერმუტაციების რაოდენობაც, რომლებიც უნდა გაკეთდეს. შემთხვევითი მონაცემებისთვის, პერმუტაციების რაოდენობა არის საშუალოდ (N^2) / 4, რაც დაახლოებით ნახევარია, ვიდრე გადასვლების რაოდენობა. თუმცა, უარეს შემთხვევაში, პერმუტაციების რაოდენობა ასევე შეიძლება იყოს N^2 / 2 - ეს იმ შემთხვევაში, თუ მონაცემები თავდაპირველად დალაგებულია საპირისპირო თანმიმდევრობით. იმისდა მიუხედავად, რომ ეს საკმაოდ ნელი დახარისხების ალგორითმია, საკმაოდ მნიშვნელოვანია იცოდეთ და გაიგოთ, როგორ მუშაობს იგი და, როგორც უკვე აღვნიშნეთ, ეს არის საფუძველი უფრო რთული ალგორითმებისთვის. ჯგდ!

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

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

image: ბუშტები

დღეს ჩვენ ვისაუბრებთ უმარტივესზე დახარისხების გაცვლა.

თუ ვინმე დაინტერესდება, გეტყვით, რომ არის სხვა კლასები - შერჩევის დალაგება, ჩასმის დალაგება, შერწყმა დახარისხება, განაწილების დახარისხება, ჰიბრიდული სახეობებიდა პარალელური ჯიშები. სხვათა შორის, არსებობს ასევე ეზოთერული დახარისხება. ეს არის სხვადასხვა ყალბი, ფუნდამენტურად არარეალიზებადი, კომიკური და სხვა ფსევდო-ალგორითმები, რომელთა შესახებაც დავწერ რამდენიმე სტატიას "IT Humor" ჰაბში.

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

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

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

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

სულელური ტიპი

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

"ნებისმიერ სულელს შეუძლია ასე დალაგება", - იტყვით და აბსოლუტურად მართალი იქნებით. ამიტომ დახარისხებას უწოდებენ "სულელურს". ამ ლექციაში ჩვენ მუდმივად გავაუმჯობესებთ და შევცვლით ამ მეთოდს. ახლა მას დროებითი სირთულე აქვს ო(n 3), ერთი შესწორების გაკეთების შემდეგ, ჩვენ უკვე მივიყვანთ ო(n 2), შემდეგ კიდევ ცოტას დავაჩქარებთ, შემდეგ ცოტას და ბოლოს მივიღებთ ო(ნჟურნალი ნ) - და ეს საერთოდ არ იქნება "სწრაფი დახარისხება"!

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

ამ შემთხვევაში ჩვენ წინაშე არაფერია ცნობილი...

ბუშტის დალაგება

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

თუ მაქსიმუმებს არა მხოლოდ ბოლომდე მივაღწევთ, არამედ მინიმუმს თავიდანვე მივაღწევთ, მაშინ წარმატებას მივაღწევთ...

შეიკერის დახარისხება

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

შეიკერის დალაგება მუშაობს ოდნავ უფრო სწრაფად, ვიდრე ბუშტების დალაგება, რადგან მაქსიმუმები და მინიმუმები მონაცვლეობით გადადიან მასივის მეშვეობით საჭირო მიმართულებებით. გაუმჯობესება, როგორც ამბობენ, აშკარაა.

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

ლუწი-კენტი დახარისხება

ამჯერად ჩვენ არ დავბრუნდებით მასივის გასწვრივ წინ და უკან, არამედ კვლავ დავუბრუნდებით სისტემატური სიარულის იდეას მარცხნიდან მარჯვნივ, მაგრამ ჩვენ მხოლოდ უფრო ფართო ნაბიჯს გადავდგამთ. პირველ უღელტეხილზე კენტი კლავიშის მქონე ელემენტები შედარებულია ლუწ ადგილებზე დაფუძნებულ მეზობლებთან (1-ლი შედარებულია მე-2-თან, შემდეგ მე-3 მე-4-თან, მე-5-ე მე-6-თან და ა.შ.). შემდეგ, პირიქით, ვადარებთ/ვცვლით „ლუწი“ ელემენტებს „კენტებთან“. შემდეგ ისევ „კენტი-ლუწი“, შემდეგ ისევ „ლუწი-კენტი“. პროცესი ჩერდება, როდესაც მასივის ზედიზედ ორი გავლის შემდეგ („კენტი-ლუწი“ და „ლუწი-კენტი“) არც ერთი გაცვლა არ მომხდარა. ასე რომ, დაალაგეს.

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

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

ეს ყველაფერი კუების ბრალია

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

image: დამნაშავე კუ

სავარცხლის დახარისხება

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

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

ოპტიმალური მნიშვნელობა დადგენილია ექსპერიმენტულად და თეორიულად შემცირების ფაქტორი:

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

ეს არის ის, რაც მინდოდა გითხრათ ბუშტების დახარისხებაზე და მის მსგავსზე.

- შენიშვნები

*შემოკლებული ( უკრაინული) - გაუმჯობესება
** დალაგებულია ნათურის მიხედვით ( უკრაინული) – ბუშტის დალაგება
*** დახარისხება სავარცხლის მიხედვით ( უკრაინული) – სავარცხლის დალაგება