Bubble სახის მასივი. ბუშტის დალაგება. ჯავაში ბუშტების დალაგების დანერგვა

04.03.2019

დავალაგოთ მასივი ზემოდან ქვევით, ნულოვანი ელემენტიდან ბოლომდე.

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

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

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

შაბლონი void bubbleSort(T a, გრძელი ზომა) (გრძელი i, j; T x; for(i=0; i< size; i++) { // ი - უღელტეხილის ნომერი for(j = ზომა-1; j > i; j--) ( // შიდა მარყუჟის მარყუჟითუ (a > a[j]) ( x=a; a=a[j]; a[j]=x; ) ) )

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

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

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

ასე რომ, ალგორითმის პირველი გაუმჯობესება არის იმის დამახსოვრება, მოხდა თუ არა რაიმე გაცვლა მოცემულ პასზე. თუ არა, ალგორითმი მთავრდება.

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

ალგორითმის თვისობრივად განსხვავებული გაუმჯობესება შეიძლება მივიღოთ შემდეგი დაკვირვებით. მიუხედავად იმისა, რომ ქვემოდან მსუბუქი ბუშტი ზევით აწევს ერთი გავლისას, მძიმე ბუშტები ჩაიძირება მინიმალური სიჩქარით: ერთი ნაბიჯით ყოველ გამეორებაზე. ასე რომ, მასივი 2 3 4 5 6 1 დალაგდება 1 უღელტეხილზე, მაგრამ 6 1 2 3 4 5 თანმიმდევრობის დახარისხებას დასჭირდება 5 გავლა.

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

შაბლონი void shakerSort(T a, გრძელი ზომა) (გრძელი j, k = ზომა-1; გრძელი lb=1, ub = ზომა-1; // მასივის დაუხარისხებელი ნაწილის საზღვრები Tx; კეთება ( //გადავლა ქვემოდან ზევით for(j=ub; j>0; j--) (თუ (a > a[j]) (x=a; a=a[j]; a[j]=x; k=j; ) ) lb = k+1; // გაიარეთ ზემოდან ქვევითამისთვის (j=1; j<=ub; j++) { if (a >a[j]) ( x=a; a=a[j]; a[j]=x; k=j; ) ) ub = k-1; ) ხოლო (lb< ub); }

რამდენად იმოქმედა აღწერილმა ცვლილებებმა მეთოდის ეფექტურობაზე? შედარებების საშუალო რაოდენობა, თუმცა შემცირდა, რჩება O(n 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 წელს სტივენ ლეისისა და რიჩარდ ბოქსის მიერ.

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

- შენიშვნები

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

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

image: ბუშტები

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- შენიშვნები

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

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

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

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

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

პროცედურა ბუშტების დალაგება;

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

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

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

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

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

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

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

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

12 18 42 44 55 67 94 06

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

94 06 12 18 42 44 55 67

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

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

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

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

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

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

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);

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

ბუშტების დალაგების ალგორითმი სრულდება დახარისხებული მასივის ელემენტებში გავლების გამეორებამდე. მასივის ელემენტების მეშვეობით გამეორება ახორციელებს შიდა მარყუჟს. თითოეული გავლისთვის შედარებულია ორი მეზობელი ელემენტებიდა თუ შეკვეთა არასწორია, ელემენტები იცვლება. გარე მარყუჟი იმუშავებს მასივის დახარისხებამდე. ამრიგად, გარე მარყუჟი აკონტროლებს შიდა მარყუჟის შესრულების რაოდენობას, როდესაც მასივის ელემენტების შემდეგი გავლისას არც ერთი ცვლილება არ მოხდება, მასივი ჩაითვლება დალაგებული. ალგორითმის კარგად გასაგებად, მოდით დავახარისხოთ, მაგალითად, 7 რიცხვის მასივი ბუშტის მეთოდის გამოყენებით (იხ. ცხრილი 1).
ორიგინალური მასივი: 3 3 7 1 2 5 0

ცხრილი 1 - ბუშტის დალაგება

გამეორების ნომერი	მასივის ელემენტები							გადაწყობები
ref. მასივი	3	3	7	1	2	5	0
0	3	3						ყალბი
1		3	7					ყალბი
2			1	7				7>1, მართალია
3				2	7			7>2, მართალია
4					5	7		7>5, მართალია
5						0	7	7>0, მართალია
მიმდინარე მასივი	3	3	1	2	5	0	7
0	3	3						ყალბი
1		1	3					3>1, მართალია
2			2	3				3>2, მართალია
3				0	3			3>0, მართალია
4					3	5		ყალბი
5						5	7	ყალბი
მიმდინარე მასივი	3	1	2	0	3	5	7
0	1	3						3>1, მართალია
1		2	3					3>2, მართალია
2			0	3				3>0, მართალია
3				3	3			ყალბი
4					3	5		ყალბი
5						5	7	ყალბი
მიმდინარე მასივი	1	2	0	3	3	5	7
	1	2						ყალბი
		0	2					2>0, მართალია
			2	3				ყალბი
				3	3			ყალბი
					3	5		ყალბი
						5	7	ყალბი
მიმდინარე მასივი	1	0	2	3	3	5	7
	0	1						1>0, მართალია
		1	2					ყალბი
			2	3				ყალბი
				3	3			ყალბი
					3	5		ყალბი
						5	7	ყალბი
საბოლოო მასივი	0	1	2	3	3	5	7
დახარისხების დასასრული

მასივის დასალაგებლად საკმარისი იყო შიდა მარყუჟის ხუთი გაშვება, for ,. დაწყების შემდეგ, for loop იმუშავა 6-ჯერ, რადგან მასივში არის 7 ელემენტი, შემდეგ გამეორებები (გამეორება) მარყუჟისთვისერთი ნაკლები უნდა იყოს. ყოველი გამეორებისას, მასივის ორი მიმდებარე ელემენტი შედარებულია. თუ მასივის მიმდინარე ელემენტი უფრო დიდია, ვიდრე მომდევნო, მაშინ ჩვენ ვცვლით მათ. ამრიგად, სანამ მასივი დალაგდება, შიდა მარყუჟი იმუშავებს და შედარების ოპერაცია შესრულდება. გაითვალისწინეთ, რომ for loop-ის ყოველი სრული შესრულებისთვის მასივის ერთი ელემენტი მაინც პოულობს ადგილს. უარეს შემთხვევაში, დასჭირდება შიდა მარყუჟის n-2 გაშვება, სადაც n არის მასივის ელემენტების რაოდენობა. ეს იმაზე მეტყველებს, რომ ბუშტების დალაგება უკიდურესად არაეფექტურია დიდი მასივებისთვის.

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

// bu_sort.cpp: განსაზღვრავს შესვლის წერტილს კონსოლის აპლიკაციისთვის. #include "stdafx.h" #include #შეიცავს #შეიცავს სახელთა სივრცის გამოყენებით std; void bubbleSort(int *, int); // ბუშტების დალაგების ფუნქციის პროტოტიპი int main(int argc, char* argv) ( srand(time(NULL)); setlocale(LC_ALL, "rus"); cout<< "Введите размер массива: "; int size_array; // длинна массива cin >> ზომა_მასივი; int *sorted_array = new int ; // ერთგანზომილებიანი დინამიური მასივი for (int მრიცხველი = 0; მრიცხველი< size_array; counter++) { sorted_array = rand() % 100; // заполняем массив случайными числами cout << setw(2) << sorted_array << " "; // вывод массива на экран } cout << "\n\n"; bubbleSort(sorted_array, size_array); // вызов функции сортировки пузырьком for (int counter = 0; counter < size_array; counter++) { cout << setw(2) << sorted_array << " "; // печать отсортированного массива } cout << "\n"; system("pause"); return 0; } void bubbleSort(int* arrayPtr, int length_array) // сортировка пузырьком { int temp = 0; // временная переменная для хранения элемента массива bool exit = false; // болевая переменная для выхода из цикла, если массив отсортирован while (!exit) // пока массив не отсортирован { exit = true; for (int int_counter = 0; int_counter < (length_array - 1); int_counter++) // внутренний цикл //сортировка пузырьком по возрастанию - знак >//დალაგება ბუშტის მიხედვით კლებადობით - ნიშანი< if (arrayPtr >arrayPtr) // შეადარეთ ორი მიმდებარე ელემენტი ( // შეასრულეთ მასივის ელემენტების გადაწყობა temp = arrayPtr; arrayPtr = arrayPtr; arrayPtr = temp; გასვლა = მცდარი; // ელემენტები გადააკეთეს შემდეგ გამეორებაზე) )

პროგრამის შედეგი ნაჩვენებია სურათზე 1.

სურათი 1 - ბუშტის დალაგება

Bubble სახის მასივი. ბუშტის დალაგება. ჯავაში ბუშტების დალაგების დანერგვა

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

შეატყობინეთ შეცდომას

ტექსტი, რომელიც გაეგზავნება ჩვენს რედაქტორებს:

თქვენი კომენტარი (სურვილისამებრ):