Хөтөлбөрийн арга барил ялгах: "хөөс" ялгах

хөөс төрөл нь зөвхөн хамгийн хурдан арга гэж үзэж үүнээс гадна, энэ нь зохион байгуулах хамгийн удаан арга замуудын жагсаалтыг хаадаг байна. Гэсэн хэдий ч, энэ нь түүний давуу талтай. Тиймээс, хөөс ялгах арга - Хамгийн гэдгийг ч та тодорхой дарааллаар зүйлсийг зохион байгуулах гэж байгаа бол, асуудал нь байгалийн болон логик шийдэл юм. зүгээр л зөн совингоо гэхэд - Энгийн хүн гараар, жишээ нь, энэ нь тэднийг ашиглаж болно.

Ийм ер бусын нэрийг хаана байсан бэ?

Арга нэр ус агаарын бөмбөлөг адилтган ашиглан гарч ирсэн. Энэ бол зүйрлэл юм. Зүгээр л хамгийн бага агаарын бөмбөлөг дээшээ өсөх - тэдний нягтрал нь шингэн (энэ тохиолдолд - ус) илүү байдаг учраас, мөн массив элемент тус бүр бага нь үнэ цэнэ, жагсаалт тоо дээд илүү аажмаар арга зам юм.

алгоритмийн тодорхойлолт

дараах байдлаар хөөс төрөл гүйцэтгэсэн байна:

• Эхний нэвтрүүлэх: массив нь тооны элемент нь хоёр хос авсан, мөн харьцуулна. Хоёр хүн багийн эхний утга зарим элементүүд нь хоёр дахь ээс их бол, хөтөлбөр тэдэнд солилцох газар хийх;
• Үүний үр дүнд хамгийн их тоо хүртвэл массивын төгсгөл. бусад бүх элементүүд нь эмх замбараагүй байдлаар тэд байсан хэвээр, ялгах, ангилах илүү шаарддаг боловч,
• Тиймээс хоёр дахь нэвтрүүлэх шаардлагатай: Энэ нь төсөөтэй хийсэн өмнөх (аль хэдийн тодорхойлсон) ба харьцуулалт нь хэд хэдэн - хасах нэг,
• аялал тоо гурван харьцуулалт, секундэд нэгээс доошгүй, хоёр, нэгдүгээр илүү байна. Тэгээд дээр;
• аялал бүрийн гэж (бүх массив дахь утга, ялангуяа тоо) хасах (аялал тоо) харьцуулалт дүгнэх.

Хөтөлбөрийн ч богино алгоритм гэж бичиж болно:

• тоо нь массив нь тэдний хоёр дахь анхны илүү байх үүрэг бол ямар ч хоёр тоо байдаг зэрэг урт шалгаж байна;
• буруу массив нь програм хангамжийн своп бүрт өөр элементүүдийн талаар байр сууриа.

Псевдокод тайлбарласан алгоритм дээр суурилсан

хялбар хэрэгжүүлэх дараах байдлаар хийж болно:

Sortirovka_Puzirkom журам;

эхлэл

konechii_index нь nachalnii_index-аас J хувьд мөчлөг;

konechii_index-1 нь nachalnii_index-аас Учир нь мөчлөг;

Хэрэв massiv [би]> massiv [Би + 1] (эхний хоёр дахь илүү элемент), дараа нь:

(Өөрчлөлт утгыг байрлуулдаг);

эцсийн

Мэдээж хэрэг, энэ нь энгийн л нөхцөл байдлыг бий болгож байна: хялбар алгоритм нь илүү энэ нь бүх алдаа гарсныг илэрдэг. Цаг хугацааны хөрөнгө оруулалтын харьцаа дэндүү их бага ч гэсэн массив нь (а программист хоёр дахь, тэр ч байтугай millisecond тоо бүр энгийн хүнийхээс цаг хэмжээ бага мэт санагдаж болох ч үнэн хэрэгтээ харьцангуйн ирдэг энд) юм.

Энэ нь илүү сайн хэрэгжүүлэх болсон. Жишээ нь, массив газар утгын солилцох харгалзан:

Sortirovka_Puzirkom журам;

эхлэл

sortirovka = үнэн,

мөчлөг sortirovka үнэн = хүртэл;

sortirovka = хуурамч;

konechii_index-1 нь nachalnii_index-аас Учир нь мөчлөг;

Хэрэв massiv [би]> massiv [Би + 1] (эхний хоёр дахь илүү элемент), дараа нь:

(Элементүүд нь солигдож);

sortirovka = үнэн, (Солилцоо хийсэн байна гэж тодорхойлсон).

Төгсгөл.

хязгаарлалт

Гол сул тал - үйл явцын үргэлжлэх хугацаа. Хэр их цаг хугацаа гүйцэтгэсэн алгоритм нь ялгах хөөс?

Хар тугалга цаг массив дахь квадрат тоо тоо тооцоолсон юм - энэ нь эцсийн үр дүн нь пропорциональ байна.

массив нь хэдэн ч удаа баталсан юм хамгийн муу тохиолдол бол энэ нь нэг утга хасах элемент байдаг юм. Энэ нь юу эцэст нь, зөвхөн нэг элемент байдаг, учир нь харьцуулах юу ч байхгүй бөгөөд энэ нь массивын дамжуулан хамгийн сүүлийн нэвтрүүлэх ямар ч хэрэггүй үйлдэл болж байна.

Үүнээс гадна, энэ нь зөвхөн жижиг хэмжээтэй массивын хувьд гэж нэрлэдэг шиг, энгийн солилцох ялгах үр дүнтэй арга. үйл явцын тусламжтайгаар их хэмжээний өгөгдөл ажиллахгүй байж болно: үр дүн алдаа, хөтөлбөрийн дутагдал байж болно.

нэр төр

хөөс төрөл ойлгоход маш хялбар байдаг. нь массивын дараалал элементийн судалгааны техникийн их, дээд сургуулийн сургалтын хөтөлбөр нь эхний ээлжинд нэвтрүүлэх. арга нь Delphi программчлалын хэлийг аль аль нь (L (Delphi), болон C / C ++ (C / C нэмэх нь нэмэх нь), зөв дарааллаар, наад байршил алгоритм нь маш энгийн утгыг хэрэгжүүлэхэд хялбар байдаг Pascal (Pascal). Bubble Sort эхлэн хамгийн тохиромжтой юм.

Улмаас алгоритмийн сул талуудтай нь гадуурх зорилгоор ашиглаж байна.

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

Алхам 1 2 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

Алхам 7 1 4 7 8 22 37 44 74

Паскалийн хөөс төрлийн жишээ

жишээ нь:

Const kol_mas = 10;

VAR massiv: массив нь [1..kol_mas] бүхэл тоо;

A, B, K: бүхэл тоо;

эхлэх

writeln ( 'оруулах', kol_mas, "массивын элементүүд ');

нь: kol_mas хүртэл = 1 readln хийх (massiv [A ]);

нэг нь: = 1 kol_mas-1 эхлэх вэ

Б: = A + 1 kol_mas нь эхлэх вэ

massiv [A]> massiv [бол B] дараа нь эхлэх

K: = massiv [A]; massiv [A]: = massiv [ B]; massiv [B]: = к;

эцсийн;

эцсийн;

эцсийн;

writeln ( 'төрлийн дараа');

а: kol_mas хүртэл = 1 writeln хийх (massiv [A ]);

төгсгөл.

ЖИШЭЭ хөөс C хэл дээр ялгах (C)

жишээ нь:

#include

#include

INT гол (INT argc, Хорхой * argv [])

{

INT massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, би FF;

нь (;;) {

FF = 0;

нь (I = 7; Би> 0; I -) {

бол (massiv [би] [i- 1]) {

Солилцох (massiv [би], massiv [i- 1]);

FF ++;

}

}

бол (FF == 0) эвдэж,

}

getch (); // дэлгэцийн саатал

0 буцаах;

}.