Бөмбөлөг ялгах. Програмчлалд эрэмбэлэх аргууд: хөөсөөр эрэмбэлэх. Ийм ер бусын нэр хаанаас ирсэн бэ?
Төвлөрсөн компьютеруудын цагийн дөрөвний нэгийг нь мэдээлэл ангилахад зарцуулдаг гэсэн тооцоо бий. Учир нь урьдчилан эрэмбэлсэн массив дахь утгыг олох нь илүү хялбар байдаг. Тэгэхгүй бол эрэл хайгуул гэдэг чинь өвсөн дотроос зүү хайсантай адил.
Бүх ажлын цагаа эрэмбэлэх алгоритмыг судалж, хэрэгжүүлэхэд зарцуулдаг програмистууд байдаг. Учир нь бизнесийн програм хангамжийн дийлэнх нь мэдээллийн баазын менежменттэй холбоотой байдаг. Хүмүүс мэдээллийн сангаас байнга мэдээлэл хайж байдаг. Энэ нь хайлтын алгоритмууд эрэлт ихтэй байна гэсэн үг юм.
Гэхдээ нэг "гэхдээ" байдаг. Хайлтын алгоритмууд нь аль хэдийн эрэмблэгдсэн мэдээллийн сантай илүү хурдан ажилладаг. Энэ тохиолдолд зөвхөн шугаман хайлт шаардлагатай.
Зарим үед компьютерууд хэрэглэгчгүй байх үед эрэмбэлэх алгоритмууд мэдээллийн сан дээр ажилласаар байна. Хайлуулагчид дахин ирдэг бөгөөд мэдээллийн баазыг аль хэдийн хайлтын зорилгод үндэслэн эрэмбэлсэн байна.
Энэ нийтлэлд стандарт эрэмбэлэх алгоритмын хэрэгжилтийн жишээг өгсөн болно.
Сонголтын төрөл
Массивыг өсөх дарааллаар эрэмбэлэхийн тулд давталт бүрт хамгийн их утгатай элементийг олох ёстой. Үүний тусламжтайгаар та сүүлчийн элементийг солих хэрэгтэй. Хамгийн өндөр утгатай дараагийн элементийг хоёроос сүүлчийн байранд байрлуулна. Энэ нь массивын эхний байранд байгаа элементүүд зохих дараалалд орох хүртэл явагдах ёстой.
C++ код
хүчингүй SortAlgo::selectionSort(int өгөгдөл, int lenD) ( int j = 0; int tmp = 0; хувьд (int i=0; i)
Бөмбөлөг ангилах
Бөмбөлөг эрэмбэлэх нь зэргэлдээх элементүүдийг харьцуулж, дараагийн элемент нь өмнөхөөсөө бага байвал газруудыг солино. Өгөгдлийг олон удаа дамжих шаардлагатай. Эхний дамжуулалтын үед массивын эхний хоёр элементийг харьцуулна. Хэрэв тэдгээр нь дараалалгүй байвал тэдгээрийг сольж, дараа нь дараагийн хосын элементүүдийг харьцуулна. Үүнтэй ижил нөхцөлд тэд бас байраа сольдог. Иймээс массивын төгсгөлд хүрэх хүртэл мөчлөг бүрт эрэмбэлэх ажил явагдана.
C++ код
хүчингүй SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i) Оруулах эрэмбэ нь массивыг эрэмбэлэгдсэн ба дараалалгүй гэсэн хоёр мужид хуваадаг. Эхэндээ массив бүхэлдээ эрэмбэлэгдээгүй муж юм. Эхний дамжуулалт дээр эрэмблэгдээгүй бүсээс эхний элементийг арилгаж, дараалсан бүсэд зөв байрлалд байрлуулна. Дамжуулах бүрт эрэмбэлэгдсэн бүсийн хэмжээ 1-ээр нэмэгдэж, эмх замбараагүй бүсийн хэмжээ 1-ээр буурдаг. Үндсэн гогцоо нь 1-ээс N-1 хүртэл үргэлжилнэ. j-р давталт дээр [i] элементийг дараалсан бүсэд зөв байрлалд оруулна. Үүнийг [i] нэг байрлалаас их эрэмбэлэгдсэн бүсийн бүх элементүүдийг баруун тийш шилжүүлэх замаар хийдэг. [i]-г [i]-ээс бага ба [i]-ээс их элементүүдийн хоорондох зайд оруулна. C++ код
хүчингүй SortAlgo::insertionSort(int өгөгдөл, int lenD) ( int түлхүүр = 0; int i = 0; хувьд (int j = 1;j) C++ код
хүчингүй SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int; int * R = new int; for () int i=0;i Quicksort нь хуваах ба ялах алгоритмыг ашигладаг. Энэ нь анхны массивыг хоёр бүс болгон хуваахаас эхэлдэг. Эдгээр хэсгүүд нь тулгуур гэж нэрлэгддэг тэмдэглэсэн элементийн зүүн ба баруун талд байрладаг. Процессын төгсгөлд нэг хэсэг нь лавлагааны хэмжээнээс бага, нөгөө хэсэг нь лавлагааны хэмжээнээс том элементүүдийг агуулна. C++ код
хүчингүй 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 = шинэ int ; int * R = шинэ int ; пивот = өгөгдөл; хувьд (i=0;i) Эдгээр аргуудын практик ашиг тус нь тийм ч их биш бөгөөд олон хабра хэрэглэгчид нэгдүгээр ангидаа энэ бүхнийг даван туулсан. Тиймээс энэ нийтлэлийг алгоритмын онолыг сонирхож эхэлсэн бөгөөд энэ чиглэлээр анхны алхамаа хийж байгаа хүмүүст зориулав. зураг: бөмбөлөгүүд Өнөөдөр бид хамгийн энгийн зүйлийн талаар ярих болно солилцооны ангилал. Хэрэв хэн нэгэн сонирхож байвал өөр ангиуд байгаа гэж хэлье - сонголтын төрөл, оруулах төрөл, нэгтгэх төрөл, түгээлтийн ангилах, эрлийз төрлүүдТэгээд зэрэгцээ төрөл. Дашрамд хэлэхэд бас байдаг эзотерик ангилах. Эдгээр нь янз бүрийн хуурамч, үндсэндээ хэрэгжих боломжгүй, хошин болон бусад псевдо алгоритмууд бөгөөд би "IT Humor" төвд хэд хэдэн нийтлэл бичих болно. Гэхдээ энэ нь өнөөдрийн лекцтэй ямар ч холбоогүй бөгөөд бид одоо зөвхөн энгийн солилцооны эрэмбийг л сонирхож байна. Өөрсдөө олон тооны солилцооны ангилал байдаг (би арав гаруй зүйлийг мэднэ), тиймээс бид гэж нэрлэгддэг зүйлийг авч үзэх болно. хөөс ангилахболон бусад зарим нь үүнтэй нягт холбоотой. Дээр дурдсан бараг бүх аргууд нь маш удаан бөгөөд тэдгээрийн цаг хугацааны нарийн төвөгтэй байдлын талаар гүнзгий дүн шинжилгээ хийхгүй гэдгийг би урьдчилан анхааруулах болно. Зарим нь илүү хурдан, зарим нь удаан байдаг, гэхдээ бид үүнийг дунджаар хэлж чадна О(n 2). Түүнчлэн, нийтлэлийг ямар ч програмчлалын хэл дээрх хэрэгжүүлэлтээр эмх замбараагүй болгох ямар ч шалтгаан олж харахгүй байна. Сонирхсон хүмүүс кодын жишээг Rosetta, Wikipedia эсвэл өөр газраас хялбархан олох боломжтой. Гэхдээ эрэмбэлэх солилцоо руу буцаж орцгооё. Захиалга нь массивыг олон удаа дараалан хайх, хос элементүүдийг бие биетэйгээ харьцуулах үр дүнд үүсдэг. Хэрэв харьцуулж буй элементүүд бие биенээсээ ангилагдаагүй бол бид тэдгээрийг солино. Цорын ганц асуулт бол массивыг яг яаж тойрч гарах, харьцуулахдаа ямар үндэслэлээр хос сонгох вэ гэдэг асуудал юм. Стандарт хөөс ангилахаас биш, харин... гэж нэрлэгддэг алгоритмаас эхэлцгээе. "Ямар ч тэнэг хүн ингэж ангилж чадна" гэж чи хэлэх болно, та үнэхээр зөв байх болно. Ийм учраас эрэмбэлэхийг "тэнэг" гэж нэрлэдэг. Энэ лекцээр бид энэ аргыг байнга сайжруулж, өөрчлөх болно. Одоо тэр түр зуурын бэрхшээлтэй байна О(n 3), нэг засвар хийсний дараа бид үүнийг аль хэдийн авчрах болно О(n 2), дараа нь бид үүнийг бага зэрэг хурдасгах болно, дараа нь арай илүү, эцэст нь бид авах болно О(nбүртгэл n) - мөн энэ нь "Түргэн эрэмбэлэх" биш байх болно! Тэнэг эрэмбэлэхдээ ганцхан сайжруулалт хийцгээе. Шилжилтийн явцад хоёр зэргэлдээ эрэмбэлэгдээгүй элементийг олж, тэдгээрийг сольсны дараа бид массивын эхэнд буцаж очихгүй, харин эцэс хүртэл тайван замаар явах болно. Энэ тохиолдолд бидний өмнө бидний сайн мэдэх... Хэрэв бид дээд хязгаарыг эцэс хүртэл шахаад зогсохгүй, хамгийн багадаа хүртэл түлхэж чадвал амжилтанд хүрнэ... Шейкерээр эрэмбэлэх нь хөөс ялгахаас арай хурдан ажилладаг, учир нь максимум ба доод хэмжээ хоёулаа массиваар шаардлагатай чиглэлд ээлжлэн шилждэг. Сайжруулалт нь тэдний хэлснээр илт харагдаж байна. Таны харж байгаагаар, хэрэв та тоолох үйл явцад бүтээлчээр хандвал массивын төгсгөлд хүнд (хөнгөн) элементүүдийг шахах нь илүү хурдан болдог. Тиймээс гар урчууд жагсаалтаас гарахын тулд өөр нэг стандарт бус “замын зураг” санал болгов. Тогтмол "хөөс" -ээр дамжуулалт бүрт бид одоогийн дээд хэмжээг массивын төгсгөл хүртэл системтэйгээр шахдаг. Хэрэв та тэгш, сондгой индексүүдийн дагуу үсрэх юм бол массивын бүх том эсвэл бага элементүүдийг нэг гүйлтээр нэгэн зэрэг баруун нэг байрлал руу түлхэнэ. Энэ арга нь илүү хурдан ажилладаг. Сүүлийнхийг харцгаая дахин тохижуулсан* Учир нь Сортування булбашка** - Самаар эрэмбэлэх***. Энэ арга нь маш хурдан зохион байгуулдаг, О(n 2) нь түүний хамгийн хэцүү бэрхшээл юм. Дунджаар бид цаг хугацааны хувьд О(nбүртгэл n), хамгийн шилдэг нь, та үүнд итгэхгүй байх болно, О(n). Энэ нь бүх төрлийн "хурдан төрлийн" маш зохистой өрсөлдөгч бөгөөд үүнийг рекурс ашиглахгүйгээр санаж байна уу. Гэсэн хэдий ч би өнөөдөр бид аялалын хурдыг судлахгүй гэж амласан тул би ярихаа больж, алгоритм руу шууд орох болно. зураг: гэм буруутай яст мэлхий Харьцуулсан элементүүдийн хоорондох анхны цоорхойг ямар ч биш, харин тусгай утгыг харгалзан үзэх нь дээр бууруулах хүчин зүйл, хамгийн оновчтой утга нь ойролцоогоор 1.247 байна. Нэгдүгээрт, элементүүдийн хоорондох зай нь массивын хэмжээтэй тэнцүү байна бууруулах хүчин зүйл(үр дүн нь мэдээжийн хэрэг хамгийн ойрын бүхэл тоо хүртэл дугуйрсан). Дараа нь массивыг энэ алхамаар дамжсаны дараа бид дахин алхамыг хуваана бууруулах хүчин зүйлмөн жагсаалтыг дахин харна уу. Энэ нь индексийн зөрүү нэг хүрэх хүртэл үргэлжилнэ. Энэ тохиолдолд массивыг ердийн бөмбөлөгөөр эрэмбэлдэг. Оновчтой утгыг туршилтын болон онолын хувьд тогтоосон бууруулах хүчин зүйл: Энэ аргыг зохион бүтээхэд 70-80-аад оны зааг дээр цөөхөн хүн үүнийг анхаарч үзсэн. Арваад жилийн дараа, програмчлал нь IBM-ийн эрдэмтэн, инженерүүдийн салбар байхаа больж, аль хэдийн маш хурдацтай нэр хүндтэй болж байх үед энэ аргыг 1991 онд Стивен Лэйси, Ричард Бокс нар дахин нээж, судалж, дэлгэрүүлжээ. Энэ бол хөөс ялгах болон үүнтэй төстэй бусад зүйлсийн талаар танд хэлэхийг хүссэн зүйл юм. - Тэмдэглэл * богиносгосон ( украин) - сайжруулах Сайн уу! Өнөөдөр бид хөөс ялгах аргыг авч үзэх болно. Энэ алгоритмыг ихэвчлэн сургууль, их дээд сургуулиудад заадаг тул бид Паскал хэлийг ашиглах болно. Тэгэхээр ангилах гэж юу вэ? Эрэмбэлэх гэдэг нь элементүүдийг хамгийн багаас том руу (өсөх эрэмбээр) эсвэл хамгийн том элементээс жижиг рүү (буурах эрэмб) эрэмблэх явдал юм. Массивуудыг ихэвчлэн эрэмбэлдэг. Янз бүрийн эрэмбэлэх алгоритмууд байдаг. Зарим нь олон тооны элементүүдийг ангилахдаа сайн байдаг бол зарим нь маш цөөн тооны элементүүдтэй илүү үр дүнтэй байдаг. Манай хөөсний арга нь дараахь шинж чанартай байдаг. Алгоритм:
Бид массивын нэг элементийг авч, дараагийнхтай нь харьцуулж, хэрэв бидний элемент дараагийн элементээс их байвал бид тэдгээрийг солино. Массивыг бүхэлд нь үзсэний дараа бид хамгийн дээд элемент нь "тухагдах" бөгөөд хамгийн сүүлчийнх нь байх болно гэдэгт итгэлтэй байж болно. Тиймээс нэг элемент аль хэдийн яг байрандаа байна. Учир нь Бид бүгдийг нь байранд нь тавих хэрэгтэй, тиймээс бид массивын элементүүдээс 1-ийг хассан бол энэ үйлдлийг хэдэн ч удаа давтах ёстой. Хэрэв үлдсэн хэсэг нь байрандаа байвал сүүлчийн элемент автоматаар зогсох болно.
Массив руугаа буцъя: 3 1 4 2 Одоо энэ алгоритмыг Паскаль хэл дээр програмчлах л үлдлээ. const n = 4; (Бид тогтмолыг тохируулсан, энэ нь массивын урт байх болно) var i, j, k:integer; (Үүрлэсэн гогцоонд зориулсан хоёр хувьсагч, нэг нь элементүүдийг солих) m:бүхэл тоон массив; (Бид массив үүсгэнэ) эхэлнэ (Бид гарнаас массивыг хүсэх болно:) Writeln("Массив оруулна уу:"); for i:=1 to n do begin Writeln(i, " element:"); Readln(m[i]); Төгсгөл; (Гадаад давталт нь массивын элементүүдийг хасах 1 байх тусам дотоод гогцоог олон удаа давтах үүрэгтэй.) for i:=1 to n-1 do begin (Дотоод гогцоо аль хэдийн элементүүдийг давтаж, харьцуулдаг. хоорондоо.) for j :=1 to n-i do begin (Хэрэв элемент нь дараагийнхаас их бол байруудыг солино.) if m[j]>m then begin k:=m[j]; m[j]:=m; m:=k; Төгсгөл; Төгсгөл; Төгсгөл; (Үр дүнг хэвлэх:) for i:=1 to n do Write(m[i], " "); Төгсгөл. Шошго: Бөмбөлөг эрэмбэлэх C, Бөмбөлөг эрэмбэлэх, Хоёр хэмжээст массивын хөөс зэрэг Мөн алгоритмын санаа нь маш энгийн. Бид тоонуудын массиваар орж дарааллыг шалгана (дараагийн тоо нь өмнөхөөсөө их, тэнцүү байх ёстой), дарааллыг зөрчсөн тохиолдолд бид элементүүдийг нэн даруй сольж, төгсгөлд хүрдэг. массив, дараа нь дахин эхэлнэ. Массивыг эрэмбэлэх (1, 5, 2, 7, 6, 3) 1, 2, 5, 3, 6, 7 Энэ нь бөмбөлөг гэх мэт "хөнгөн" элементүүдийн "дээш хөвөх"тэй төстэй гэж тэд хэлдэг тул алгоритм ийм нэртэй болсон. хүчингүй хөөс эрэмбэлэх(int *a, хэмжээ_t хэмжээ) ( size_t i, j; int tmp; хувьд (i = 1; i)< size; i++) {
for (j = 1; j < size; j++) {
if (a[j] >a) ( tmp = a[j]; a[j] = a; a = tmp; ) ) ) ) Энэ алгоритм нь оролтын өгөгдлөөс үл хамааран үргэлж (n-1) 2 алхам хийх болно. Массив эрэмбэлэгдсэн байсан ч (n-1) 2 удаа дамжих болно. Түүнээс гадна аль хэдийн эрэмбэлсэн өгөгдлийг дахин шалгах болно. 1, 2, 4, 3 гэсэн массивыг эрэмбэлэх хэрэгтэй гэж бодъё 1 2 4 3 a болон a элементүүдийг сольсны дараа массивын энэ хэсгийг туулах шаардлагагүй болно. Үүнийг анхаарч алгоритмаа дахин боловсруулъя Хүчингүй bubbleSort2(int *a, size_t хэмжээ) ( size_t i, j; int tmp; for (i = 1; i)< size; i++) {
for (j = i; j >0; j--) (хэрэв (a[j])< a) {
tmp = a[j];
a[j] = a;
a = tmp;
}
}
}
}
Өөр нэг хэрэгжилт Хүчингүй bubbleSort2b(int *a, size_t хэмжээ) ( size_t i, j; int tmp; for (i = 1; i)< size; i++) {
for (j = 1; j <= size-i; j++) {
if (a[j] < a) {
tmp = a[j];
a[j] = a;
a = tmp;
}
}
}
}
Энэ тохиолдолд хоёр дахин олон алхам байх болно, гэхдээ аль хэдийн эрэмбэлсэн массивыг эрэмбэлэх асуудал хэвээр байна: та функц нь эрэмбэлэгдсэн массивыг нэг удаа харж байгаа эсэхийг шалгах хэрэгтэй. Үүнийг хийхийн тулд бид туг хувьсагчийг танилцуулж байна: хэрэв массив эрэмблэгдсэн бол үүнийг орхигдуулах болно (туг = 0). Бид дарааллын зөрчилтэй тулгармагц туг өргөх болно (туг = 1) бид ердийнхөөрөө массивыг эрэмбэлж эхэлнэ. Void bubbleSort3(int *a, size_t хэмжээ) ( size_t i; int tmp; char туг; хийх ( туг = 0; хувьд (i = 1; i)< size; i++) {
if (a[i] < a) {
tmp = a[i];
a[i] = a;
a = tmp;
flag = 1;
}
}
} while (flag);
}
Энэ тохиолдолд нарийн төвөгтэй байдал нь мөн n 2 дараалалтай байх боловч эрэмбэлэгдсэн массивын хувьд зөвхөн нэг дамжуулалт байх болно. Одоо алгоритмаа сайжруулцгаая. Хоосон төрлийн массивыг эрэмбэлэх ерөнхий функц бичье. Хувьсагчийн төрөл тодорхойгүй тул та массивын нэг элементийн хэмжээ болон харьцуулах функцийг нэмж оруулах шаардлагатай болно. Int intSort(const void *a, const void *b) ( буцах *((int*)a) > *((int*)b); ) void bubbleSort3g(хүчингүй *a, size_t зүйл, size_t хэмжээ, int (* cmp)(const void*, const void*)) ( size_t i; хүчингүй *tmp = NULL; char туг; tmp = malloc(зүйл); do ( туг = 0; хувьд (i = 1; i)< size; i++) {
if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) {
memcpy(tmp, ((char*)a + i*item), item);
memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item);
memcpy(((char*)a + (i-1)*item), tmp, item);
flag = 1;
}
}
} while (flag);
free(tmp);
}
Функц нь муухай харагдаж байна - одоогийн болон өмнөх элементийн хаягийг ихэвчлэн тооцдог. Үүний тулд тусдаа хувьсагчдыг тодруулцгаая. Void bubbleSort3gi(void *a, size_t зүйл, size_t size, int (*cmp)(const void*, const void*)) ( size_t i; void *tmp = NULL; void *prev, *cur; char flag; tmp = malloc(зүйл); do ( туг = 0; i = 1; өмнөх = (char*)a; cur = (char*) өмнөх + зүйл; while (i)< size) {
if (cmp(cur, prev)) {
memcpy(tmp, prev, item);
memcpy(prev, cur, item);
memcpy(cur, tmp, item);
flag = 1;
}
i++;
prev = (char*)prev + item;
cur = (char*)cur + item;
}
} while (flag);
free(tmp);
}
Одоо эдгээр функцийг ашигласнаар та ямар ч төрлийн массивыг эрэмбэлэх боломжтой Void main() ( int a = (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); int i; bubbleSort3gi(a, sizeof(int), 10, intSort); for (i) = 0;i< 10; i++) {
printf("%d ", a[i]);
}
_getch();
}
Статик олон хэмжээст массивыг эрэмбэлэх нь нэг хэмжээст массивыг эрэмбэлэхээс үндсэндээ ялгаатай биш юм. Та статик нэг хэмжээст болон олон хэмжээст массивууд санах ойд ижил дүрстэй байдгийг ашиглаж болно. Void main() ( int a = (1, 9, 2, 8, 3, 7, 4, 6, 5); int i, j; bubbleSort3gi(a, sizeof(int), 9, intSort); for (i) = 0;i< 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
}
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
#include Хоёрдугаарт, та эхлээд массивыг нэг хэмжээст рүү шилжүүлж, нэг хэмжээст массивыг эрэмбэлээд дараа нь хоёр хэмжээст рүү шилжүүлж болно. Void bubbleSort3gi2d(void **a, size_t зүйл, size_t m, size_t n, int (*cmp)(const void*, const void*)) ( size_t size = m*n, дэд_хэмжээ = n*зүйл; size_t i, j , k; void *arr = malloc(хэмжээ * зүйл); char *p1d = (char*)arr; char *p2d = (char*)a; //Хоёр хэмжээст хоосон төрлийн массивыг нэг хэмжээст рүү хуулна. хувьд (i = 0; i< m; i++) {
memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size);
}
bubbleSort3gi(arr, item, size, cmp);
//Копируем одномерный массив обратно в двумерный
for (i = 0; i < m; i++) {
memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size);
}
}
Хэрэв та энэ функцэд андуурч байгаа бол бичсэн функцийг ашиглана уу. Өмнөх жишээнээс залгах Энэ нь зөвхөн хамгийн хурдан арга гэж тооцогддоггүй төдийгүй хамгийн удаан захиалга өгөх аргуудын жагсаалтыг хаадаг. Гэсэн хэдий ч энэ нь бас давуу талтай. Тиймээс, хэрэв та элементүүдийг тодорхой дарааллаар байрлуулах шаардлагатай бол хөөс ялгах нь асуудлыг шийдэх хамгийн логик бөгөөд байгалийн шийдэл юм. Жишээлбэл, жирийн хүн үүнийг гараар ашиглах болно - зүгээр л зөн совингоор. Уг аргын нэрийг усан дахь агаарын бөмбөлөгтэй зүйрлэснээр зохион бүтээжээ. Энэ бол зүйрлэл юм. Жижиг агаарын бөмбөлгүүд дээшээ гарч ирдэгтэй адил тэдгээрийн нягт нь аливаа шингэнийхээс (энэ тохиолдолд ус) их байдаг тул массивын элемент бүр бага байх тусам түүний үнэ цэнэ аажмаар нэмэгддэг. тоонуудын жагсаалтын эхэнд хүрэх зам. Бөмбөлөг ангилах нь дараах байдлаар ажилладаг. Илүү товчхондоо ирээдүйн программын алгоритмыг дараах байдлаар бичиж болно. Хамгийн энгийн хэрэгжилт нь дараах байдалтай байна. Процедур Сортировка_Пузирком;
Эхлэх
-д зориулсан гогцоо j-аас анхны_индексөмнө konechii_index;
-д зориулсан гогцоо би-аас анхны_индексөмнө konechii_index-1;
Хэрэв массив[i]>массив (утгуудыг солих); Төгсгөл
Мэдээжийн хэрэг, энгийн байдал нь нөхцөл байдлыг улам хүндрүүлдэг: алгоритм нь энгийн байх тусам бүх дутагдал гарч ирдэг. Цагийн зарцуулалт нь жижиг массивын хувьд ч хэтэрхий их байдаг (харьцангуйн онол энд чухал үүрэг гүйцэтгэдэг: энгийн хүний хувьд цаг хугацаа бага мэт санагдаж болох ч програмистын бизнест секунд бүр, бүр миллисекунд бүр чухал байдаг). Илүү сайн хэрэгжүүлэх шаардлагатай байсан. Жишээлбэл, массив дахь утгуудыг солихыг харгалзан үзвэл: Процедур Сортировка_Пузирком;
Эхлэх
сортировка
= үнэн; өнөөг хүртэл мөчлөг сортировка
= үнэн;
сортировка
= худал;
-д зориулсан гогцоо би-аас анхны_индексөмнө konechii_index-1;
Хэрэв массив[i]>массив(эхний элемент нь хоёр дахь элементээс их), дараа нь: (элементүүдийг солих); сортировка
= үнэн; (солилцоо хийгдсэнийг харуулсан).
Төгсгөл.
Гол сул тал бол үйл явцын үргэлжлэх хугацаа юм. Бөмбөлөг хийхэд хэр хугацаа шаардагдах вэ? Гүйцэтгэх хугацааг массив дахь тоонуудын квадратаас тооцдог - эцсийн үр дүн нь үүнтэй пропорциональ байна. Хамгийн муу тохиолдолд массив нь нэг утгыг хассан элемент байгаатай ижил тооны удаа дамжих болно. Энэ нь эцэст нь харьцуулах зүйлгүй ганц л элемент үлдэж, массиваар дамжин өнгөрөх сүүлийн дамжуулалт нь ашиггүй үйлдэл болж хувирдаг. Нэмж дурдахад энгийн солилцооны эрэмбэлэх арга нь зөвхөн жижиг массивуудад үр дүнтэй байдаг. Түүний тусламжтайгаар их хэмжээний өгөгдлийг боловсруулах боломжгүй болно: үр дүн нь алдаа эсвэл програмын бүтэлгүйтэл байх болно. Бөмбөлөг ангилах нь ойлгоход маш энгийн. Техникийн их, дээд сургуулийн сургалтын хөтөлбөрт массивын элементүүдийн дарааллыг судлахдаа эхлээд тусгагдсан байдаг. Энэ аргыг Delphi програмчлалын хэл (D) болон C/C++ (C/C plus plus) аль алинд нь хялбархан хэрэгжүүлдэг бөгөөд утгуудыг зөв дарааллаар нь байрлуулах гайхалтай энгийн алгоритм бөгөөд Bubble Sort нь эхлэгчдэд тохиромжтой. Түүний дутагдалтай байдлаас шалтгаалан алгоритмыг хичээлээс гадуурх зорилгоор ашигладаггүй. Массивын анхны харагдац 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 Алхам 7 1 4 7 8 22 37 44 74 Жишээ: const kol_mas=10; var массив:бүхэл тоон массив; a, b, k: бүхэл тоо; writeln("оролт", kol_mas, "массивын элементүүд"); for a:=1 to kol_mas хийх readln(массив[a]); a:=1-ээс kol_mas-1 хүртэл эхэлнэ for b:=a+1 to kol_mas эхлэх хэрэв massiv[a]>massiv[b] бол эхэлнэ k:=массив[a]; массив[a]:=массив[b]; массив[b]:=k; Төгсгөл; writeln("эрэмбэлэсний дараа"); for a:=1 to kol_mas do writeln(massiv[a]); #оруулна #оруулна int main(int argc, char* argv) int massiv = (36, 697, 73, 82, 68, 12, 183, 88), i, ff; төлөө (; ;)( ff = 0; хувьд (i = 7; i>0; i--)( хэрэв (массив[i]< massiv) {
солих (массив[i], массив); хэрэв (ff == 0) тасарвал; getch(); // дэлгэцийн сааталОруулах төрөл
Нэгтгэх төрөл
Түргэн ангилах
Валютын төрлөөс хамгийн хурдан арга гэж нэрлэгддэг аргыг хүн бүр сайн мэддэг хурдан ангилах. Энэ тухай диссертаци бичиж, Хабрегийн тухай олон өгүүлэлд зориулж, түүн дээр үндэслэн нарийн төвөгтэй эрлийз алгоритмуудыг зохион бүтээжээ. Гэхдээ өнөөдөр бид энэ талаар ярихгүй хурдан ангилах, мөн өөр нэг солилцооны аргын тухай - сайн хуучин хөөс ангилахболон түүний сайжруулалт, өөрчлөлт, мутаци, өөрчлөлтүүд. Тэнэг төрөл
Ангилах нь үнэхээр тэнэг юм. Бид массивыг зүүнээс баруун тийш харж, зам дагуух хөршүүдийг харьцуулна. Хэрэв бид хоорондоо ялгагдаагүй хос элементүүдтэй тулгарвал бид тэдгээрийг сольж, нэг дөрвөлжин рүү буцна, өөрөөр хэлбэл хамгийн эхэнд. Бид массивыг дахин шалгаад, хэрэв бид "буруу" хөрш зэргэлдээ элементүүдтэй дахин таарвал бид газруудыг сольж, бүгдийг дахин эхлүүлнэ. Массивыг бага багаар эрэмбэлэх хүртэл бид үргэлжлүүлнэ. Бөмбөлөг ангилах
Эсвэл энгийн солилцоогоор ангилах. Үхэшгүй мөнхийн сонгодог төрөл. Үйл ажиллагааны зарчим нь энгийн: бид массивыг эхнээс нь дуустал гүйлгэж, ангилаагүй хөрш элементүүдийг нэгэн зэрэг сольдог. Эхний дамжуулалтын үр дүнд хамгийн дээд элемент нь сүүлчийн газар хүртэл "хөвөх" болно. Одоо бид массивын эрэмблэгдээгүй хэсгийг (эхний элементээс эцсийн өмнөх элемент хүртэл) дахин давж, замдаа эрэмбэлэгдээгүй хөршүүдийг өөрчилнө. Хоёр дахь том элемент нь хоёроос сүүлчийн байранд байх болно. Бид ижил сүнсээр үргэлжлүүлэн массивын байнга буурч буй эрэмблэгдээгүй хэсгийг туулж, олсон максимумыг эцэс хүртэл түлхэх болно. Сэгсрэгчээр ангилах
Тэр адилхан холих төрөл, тэр адилхан коктейль ангилах. Процесс нь "хөөс" шиг эхэлдэг: бид хамгийн их хэмжээгээр ар тал руу нь шахдаг. Үүний дараа бид 180 0-ийг эргүүлж, эсрэг чиглэлд явж, хамгийн ихдээ биш, харин хамгийн багадаа буцаж очно. Массив дахь эхний болон сүүлчийн элементүүдийг эрэмбэлсний дараа бид дахин эргэлт хийнэ. Хэд хэдэн удаа нааш цааш явсны эцэст бид үйл явцыг дуусгаж, жагсаалтын голд ордог. Тэгш сондгой ангилах
Энэ удаад бид массиваар нааш цааш гүйхгүй, харин зүүнээс баруун тийш системтэй алхах санаа руу буцаж очих болно, гэхдээ бид зөвхөн илүү өргөн алхам хийх болно. Эхний дамжуулалт дээр сондгой түлхүүртэй элементүүдийг тэгш газар үндэслэн хөршүүдтэйгээ харьцуулна (1-ийг 2-р, дараа нь 3-ыг 4, 5-ыг 6 гэх мэт). Дараа нь бид эсрэгээрээ "тэгш" элементүүдийг "сондгой" элементүүдтэй харьцуулдаг/өөрчилдөг. Дараа нь дахин "сондгой-тэгш", дараа нь дахин "тэгш-сондгой". Массивыг хоёр дараалан дамжуулсны дараа ("сондгой-тэгш" ба "тэгш сондгой") нэг ч солилцоо хийгдээгүй үед процесс зогсдог. Тиймээс тэд үүнийг ангилсан. 
Энэ бүгд яст мэлхийн буруу
Бага зэрэг дэвсгэр. 1980 онд Влодзимиерз Добосевич яагаад хөөс ялгах болон түүний деривативууд маш удаан ажилладагийг тайлбарласан. Энэ бүхэн яст мэлхийнээс болсон. "Яст мэлхий" нь жагсаалтын төгсгөлд байрладаг жижиг элементүүд юм. Жагсаалтын эхэнд байгаа том үнэ цэнэтэй элементүүд болох "туулай" (Бабушкины "туулай"-тай андуурч болохгүй) хөөс зэрэгт анхаарлаа хандуулсан гэдгийг та анзаарсан байх. Тэд барианы шугам руу маш хурдан хөдөлдөг. Гэвч удаан мөлхөгчид эхэндээ дурамжхан мөлхдөг. Та тортиллагаа ашиглан тохируулж болно самнууд. Самнаж ангилах
"Хөөс", "сэгсрэгч", "сондгой-тэгш" хэлбэрээр массиваар давтагдах үед хөрш зэргэлдээх элементүүдийг харьцуулна. "Сам" -ын гол санаа нь эхлээд харьцуулж буй элементүүдийн хооронд хангалттай том зайг авч, массивын дарааллаар энэ зайг хамгийн бага хэмжээнд хүртэл нарийсгах явдал юм. Ийм байдлаар бид массивыг самнаж, аажмаар жигдрүүлж, улам цэвэрхэн утас болгон жигдрүүлдэг. 
** чийдэнгээр эрэмбэлсэн ( украин) – Хөөс ялгах
*** Самаар эрэмбэлэх ( украин) – Самнаж ангилах
Давуу тал:
Сул талууд:
Тодорхой массивтай болцгооё: 3 1 4 2
Бид эхний "3" элементийг аваад дараагийн "1"-тэй харьцуулна. Учир нь "3" > "1", дараа нь газруудыг солино уу:
1 3 4 2
Одоо бид "3" ба "4"-ийг харьцуулж, гурав нь дөрвөөс ихгүй байгаа нь бид юу ч хийхгүй гэсэн үг юм. Дараа нь "4" ба "2"-ыг харьцуулна уу. Дөрөв нь хоёроос их тул бид байраа сольдог: 1 3 2 4. Цикл дууслаа. Энэ нь хамгийн том элемент аль хэдийн байрандаа байх ёстой гэсэн үг юм!! Энд ийм зүйл болсныг бид харж байна. "4" (бидний хамгийн том элемент) хаана ч байсан, давталт бүх массивыг дайран өнгөрсний дараа энэ нь сүүлчийнх хэвээр байх болно. Нэг зүйрлэл - агаарын бөмбөлөг усанд хөвдөгтэй адил бидний элемент массив дээр хөвдөг. Ийм учраас алгоритмыг "Bubble Sort" гэж нэрлэдэг. Дараагийн элементийг байрлуулахын тулд мөчлөгийг дахин эхлүүлэх шаардлагатай боловч сүүлчийн элемент нь байрандаа байгаа тул цаашид авч үзэх боломжгүй юм.
Бид "1" ба "3"-ыг харьцуулдаг - бид юу ч өөрчлөхгүй.
Бид "3" ба "2"-ыг харьцуулж байна - Гурав нь хоёроос их, энэ нь бид байраа сольж байна гэсэн үг. Үүнээс харахад: 1 2 3 4 . Хоёр дахь мөчлөг дууссан. Бид хоёр мөчлөгийг аль хэдийн дуусгасан бөгөөд энэ нь бидний сүүлийн хоёр элементийг аль хэдийн ангилсан гэж итгэлтэйгээр хэлж чадна гэсэн үг юм. Бидний хийх ёстой зүйл бол гурав дахь элементийг эрэмбэлэх бөгөөд дөрөв дэх нь автоматаар зөв газартаа унах болно. Дахин нэг удаа бид эхний болон хоёр дахь элементийг харьцуулж үзвэл бид бүх зүйл байрандаа байгаа гэдгийг бид харж байгаа бөгөөд энэ нь массивыг элементүүдийн өсөх дарааллаар эрэмбэлсэн гэж үзэж болно гэсэн үг юм.
Үр дүн нь энд байна: 
Энд видео заавар байна
Бөмбөлөг ангилах
Бид массиваар явж, эхний дугаар, хоёр дахь дугаарыг шалгана, тэдгээр нь өсөх дарааллаар байна. Дараа нь дэг журам зөрчигдөж, бид эдгээр элементүүдийг сольж байна
1, 2, 5, 7, 6, 3
Бид массиваар үргэлжлүүлэн 7 нь 5-аас их, харин 6 нь бага тул бид тэдгээрийг сольж байна.
1, 2, 5, 6, 7, 3
3 нь дарааллыг зөрчиж, 7-оор байраа солино
1, 2, 5, 6, 3, 7
Бид массивын эхэнд буцаж очоод ижил зүйлийг хийнэ
1, 2, 3, 5, 6, 7
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4Олон хэмжээст массивыг эрэмбэлэх
Ийм ер бусын нэр хаанаас ирсэн бэ?
Алгоритмын тайлбар
Тайлбарласан алгоритм дээр суурилсан псевдокод
Аргын сул тал
Давуу тал
Харааны эрэмбэлэх зарчим
Паскаль хэл дээрх хөөс ялгах жишээ
Си хэл дээрх хөөс ялгах жишээ