Დახარისხება ტექნიკის პროგრამირება: დახარისხება "ბუშტი"

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

სად ასეთი უჩვეულო სახელი?

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

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

bubble sort ხორციელდება შემდეგნაირად:

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

კიდევ უფრო მოკლეა ალგორითმი პროგრამა შეიძლება ჩაიწეროს როგორც:

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

Pseudocode საფუძველზე ალგორითმი აღწერილი

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

Sortirovka_Puzirkom წესით;

იწყება

ციკლი j ეხლა nachalnii_index to konechii_index;

ციკლი i ეხლა nachalnii_index to konechii_index-1;

თუ massiv [i]> მასივი [i + 1] (პირველ ელემენტს უფრო მეტია, ვიდრე მეორე), მაშინ:

(შეცვლა ადგილებში ღირებულებების);

ბოლოს

რა თქმა უნდა, ამ სიმარტივის მხოლოდ ამძიმებს სიტუაციას: მარტივი ალგორითმი, მით უფრო, რომ აისახება ყველა ხარვეზები. საინვესტიციო თანაფარდობა დროს არის ძალიან დიდი თუნდაც მცირე array (აქ მოდის ფარდობითობის: დროის არაპროფესიონალისთვისაც ჩანდეს პატარა, მაგრამ სინამდვილეში პროგრამისტი ყოველ მეორე ან თუნდაც millisecond ითვლის).

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

Sortirovka_Puzirkom წესით;

იწყება

sortirovka = true;

ციკლი სანამ sortirovka = true;

sortirovka = false;

ციკლი i ეხლა nachalnii_index to konechii_index-1;

თუ massiv [i]> მასივი [i + 1] (პირველ ელემენტს უფრო მეტია, ვიდრე მეორე), მაშინ:

(შეცვლა ელემენტები ადგილები);

sortirovka = true; (განსაზღვრული, რომ გაცვლა გაკეთდა).

End.

შეზღუდვები

მთავარი მინუსი - ხანგრძლივობა პროცესში. რამდენი დრო ხორციელდება დახარისხება ალგორითმი bubble?

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

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

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

ღირსება

bubble sort არის ძალიან ადვილი გასაგებია. პროგრამაში ტექნიკური უნივერსიტეტების შესწავლა შეკვეთით ელემენტები თავისი მასივი გაივლის პირველი ადგილი. მეთოდი არის მარტივი განხორციელება ორივე Delphi პროგრამირების ენა (L (Delphi) და C / C ++ (C / C plus plus), წარმოუდგენლად მარტივი ღირებულებების ადგილმდებარეობა ალგორითმი სწორი მიზნით და Pascal (პასკალ). Bubble დალაგების იდეალურია დამწყებთათვის.

იმის გამო, რომ ნაკლი ალგორითმი არ გამოიყენება კლასგარეშე მიზნებისათვის.

Visual დახარისხება პრინციპი

საწყის ხედი მასივი 8 22 4 74 44 37 1 7

ნაბიჯი 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

ნაბიჯი 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

ნაბიჯი 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

ნაბიჯი 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

ნაბიჯი 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

ნაბიჯი 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Step 7 1 4 7 8 22 37 44 74

bubble sort მაგალითად Pascal

მაგალითად:

const kol_mas = 10;

var massiv: array [1..kol_mas] საქართველოს მთელი რიცხვი;

a, b, k: მთელი რიცხვი;

დაიწყოს

writeln ( "input", kol_mas, ელემენტების მასივი ");

ამისთვის: = 1 kol_mas ამის readln (massiv [a ]);

ამისთვის: = 1 kol_mas 1 გააკეთებს დაიწყოს

ბ: = a + 1 kol_mas არ დაიწყოს

თუ massiv [a]> massiv [ b] შემდეგ დაიწყება

k = massiv [a]; massiv [a] = massiv [ b]; massiv [b]: = k;

დასრულდება;

დასრულდება;

დასრულდება;

writeln ( "მას შემდეგ, რაც ერთგვარი");

ამისთვის: = 1 kol_mas ამის writeln (massiv [a ]);

ბოლომდე.

მაგალითი bubble დახარისხება C ენის (C)

მაგალითად:

# include

# include

int ძირითადი (int argc, char * argv [])

{

int მასივი [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

for (;;) {

ff = 0;

(i = 7 i> 0; i -) {

თუ (massiv [i] [i- 1]) {

swap (massiv [i], massiv [i- 1]);

ff ++;

}

}

თუ (ff == 0) მოხსნა;

}

getch (); // ჩვენება დაგვიანებით

დაბრუნდეს 0;

}.