Шууд оруулах аргаар массивыг эрэмбэлэх. Шууд ангилах. Дамжуулах алгоритмын үр ашиг

Шаардлагатай тодорхойлолт, ангиллын ангилал.

Эрэмбэлэх. Шаардлагатай тодорхойлолт, ангиллын ангилал. Шууд оруулах, сонгох ангилах. Тэдний үр нөлөө

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

Хэрэв эрэмбэлэгдсэн бичлэгүүд их хэмжээний санах ой эзэлдэг бол тэдгээрийг зөөх нь үнэтэй байдаг. Тэдгээрийг багасгахын тулд ашиглах хэрэгтэй хаягийн хүснэгтийг эрэмбэлэх арга. Энэ аргыг ашиглаж байна гол хаягийн хүснэгт. Заагчуудыг дахин цэгцэлсэн, i.e. Массив өөрөө зөөгддөггүй. Эрэмбэлэх үед ижил товчлуурууд гарч ирж болно. Энэ тохиолдолд эх файл дахь ижил дарааллаар эрэмбэлсэний дараа ижил түлхүүрүүдийг байрлуулахыг зөвлөж байна. Энэ зарчмыг ашигладаг тогтвортой ангилах.

Эрэмбэлэх үр ашгийг хэд хэдэн шалгуураар авч үзэж болно:

1) ангилахад зарцуулсан цаг хугацаа;

2) ангилахад шаардагдах RAM-ийн хэмжээ;

3) Программист програм бичихэд зарцуулсан цаг.

Ангилахад зарцуулсан хугацаа нь эрэмбэлэх явцад гүйцэтгэсэн харьцуулалт болон элементүүдийг зөөх тоотой пропорциональ байна.

Ангилахдаа харьцуулах дугаарын дараалал нь хооронд хэлбэлзэж болно гэж үздэг o(nlogn)өмнө o(n 2), Хаана o(n)- хамгийн тохиромжтой, боломжгүй тохиолдол.

Эрэмбэлэх аргуудыг ойролцоогоор дараах байдлаар ангилж болно.

1) хатуу (шууд) аргууд(тэдгээрийн үр нөлөө нь ойролцоогоор ижил):

· шууд холболт;

· шууд сонголт;

· шууд солилцоо;

2) сайжруулсан аргууд.

Амьдралд ийм эрэмбэлэх зарчим нь ганцаарчилсан тоглоом тоглох, орон сууц цэвэрлэх, олон тооны холимог зүйлийг зохих дарааллаар байрлуулах шаардлагатай үед байдаг. Мэдээллийг эрэмбэлэхдээ маш байгалийн ангилах аргыг ашигласан.

Элементүүд нь оюун санааны хувьд бэлэн дараалалд хуваагддаг a 1 ,...,a i-1болон анхны дараалал. Дууссан дарааллаар элементүүдийг өгөгдсөн дарааллаар (буурах эсвэл өсөх) байрлуулна. Мөн эхний дараалалд эрэмбэлэх шаардлагатай элементүүд байдаг. Алхам бүрт анхны дарааллын элементүүд нэгээр буурч, дууссан дараалал нэгээр нэмэгддэг. Энэ нь анхны дарааллыг гаргаж авсан тул тохиолддог би- th элемент бөгөөд дууссан дараалал руу шилжиж, дууссан дарааллын элементүүдийн дунд хүссэн газарт нь оруулна.

10, 3, 11, 8, 2, 15, 44, 9 гэсэн элементүүдийн дарааллаар шууд оруулах аргыг ашиглан эрэмбэлэх жишээг авч үзье (Хүснэгт 11.1). Үүнийг өсөх дарааллаар эрэмбэлэх шаардлагатай.

Эхлээд дууссан дараалалд ямар ч элемент байхгүй. Эхний алхамд анхны дарааллын эхний элемент болох 10 нь дууссан дарааллын эхний элемент болно. Дараагийн алхам бол хоёр дахь алхам юм: анхны дарааллын 3-р элементийг дууссан хэсэгт байрлуулна. Энэ нь ингэж явдаг. Хэрэв элемент 10-аас их бол байрандаа үлдэнэ, бага бол 10-ыг нэг нэгж баруун тийш шилжүүлж, элементийг байранд нь байрлуулна. 3 оноос хойш<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, дараа нь 11 байрандаа үлдэнэ. Анхны дараалал нь одоо: 8, 2, 15, 44, 9. Дараагийн алхмуудыг ижил аргаар гүйцэтгэнэ.

Хүснэгт 11.1

Шууд ангилах нь хэрхэн ажилладаг

Энэхүү эрэмбэлэх үе шатуудын тоо (Хүснэгт 11.1) нь эрэмбэлж буй дарааллын элементүүдийн тоотой тэнцүү байна, өөрөөр хэлбэл. 8 алхам = 8 элемент.

Энэ аргыг хэрэгжүүлэх хоёр арга байдаг - саадгүй (Зураг 11.1) болон саадтай (Зураг 11.2).

Арга: Эдгээр бодисын диэлектрик тогтмол нь чийгийн агууламжаас хамаарах хамааралд үндэслэн бодисын чийгийн хэмжээг шууд бусаар хэмжих арга. Эх сурвалж: RMG 75 2004: Улсын хүнсний хангамжийн тогтолцоо ...

ЦУС- ЦУС нь биеийн артери, судас, хялгасан судсыг дүүргэдэг, тунгалаг, цайвар шаргал өнгөтэй шингэн юм. цусны сийвэнгийн өнгө ба түүнд агуулагдах үүссэн элементүүд: цусны улаан эс эсвэл эритроцит, цагаан эсвэл лейкоцит, цусны товруу, эсвэл ... Анагаах ухааны агуу нэвтэрхий толь бичиг

Үл хөдлөх хөрөнгө- (Үл хөдлөх хөрөнгө) Үл хөдлөх хөрөнгийн тодорхойлолт, үл хөдлөх хөрөнгийн төрлүүд, үл хөдлөх хөрөнгийн түрээс, худалдах үл хөдлөх хөрөнгийн тухай ойлголт, үл хөдлөх хөрөнгийн төрөл, үл хөдлөх хөрөнгийн түрээс, худалдах, татвар, даатгалын тухай мэдээлэл Агуулга - энэ нь төрөл юм. эд хөрөнгө, ...... Хөрөнгө оруулагчдын нэвтэрхий толь бичиг

Энэ нэр томъёо нь өөр утгатай, C-г үзнэ үү. Мөн үзнэ үү: C (програмчлалын хэл) C++ Утга зүй: олон парадигм: объект хандалтат, ерөнхий, процедур, метапрограмчлал Гүйцэтгэх төрөл: эмхэтгэсэн ... Wikipedia-д гарсан.

БИЕТ БУС ХӨРӨНГИЙН ҮНЭЛГЭЭНИЙ ҮНЭЛГЭЭ- (англ. биет бус хөрөнгийн үнэлгээ) - тухайн аж ахуйн нэгжийн материаллаг агуулгагүй, аж ахуйн нэгжид орлого бүрдүүлдэг тодорхой бүлэг объектын эрхийн хэмжээг үндэсний... тогтоосон хугацаанд тодорхойлох. .. Санхүү, зээлийн нэвтэрхий толь бичиг

СУРГУУЛИЙН ерөнхий боловсрол- уч. сургах болно байгууллага, үндсэн элемент үүссэн. системүүд. Энэ чиглэлээр Ш. хичээлүүд: сурган хүмүүжүүлэх ухаан, түүх, хүн ам зүй, социологи гэх мэт Зөвхөн сурган хүмүүжүүлэх ухаанд шинжлэх ухааны асуудал бүрэн бие даасан байр суурийг эзэлдэг. газар. Мэдлэг...... Оросын сурган хүмүүжүүлэх нэвтэрхий толь бичиг

цаг хугацаа- 3.3.4 цаг tE (цаг хугацаа tE): ротор эсвэл статорын ороомгийн анхны эхлэх ээлжийн гүйдлийн IA-аар нэрлэсэн ажлын горимд хүрсэн температураас орчны хамгийн их температурт зөвшөөрөгдөх температур хүртэл халаах хугацаа. Эх сурвалж… Норматив, техникийн баримт бичгийн нэр томъёоны толь бичиг-лавлах ном

ГОСТ R IEC 60204-1-2007: Машины аюулгүй байдал. Машин механизмын цахилгаан тоног төхөөрөмж. 1-р хэсэг. Ерөнхий шаардлага- Нэр томьёо ГОСТ R IEC 60204 1 2007: Машины аюулгүй байдал. Машин механизмын цахилгаан тоног төхөөрөмж. 1-р хэсэг. Ерөнхий шаардлага анхны баримт бичиг: TN тэжээлийн систем 18.2.2-т заасны дагуу 1-р аргын дагуу туршилтыг хэлхээ тус бүрээр хийж болно... ... Норматив, техникийн баримт бичгийн нэр томъёоны толь бичиг-лавлах ном

авто- 3.3.1 Автомат дээж авах төхөөрөмж: Дамжуулах хоолойгоор урсаж буй шингэний төлөөллийн дээжийг авахад ашигладаг төхөөрөмж. Тайлбар Автомат дээж авагч нь ихэвчлэн датчик, олборлогч ... ... Норматив, техникийн баримт бичгийн нэр томъёоны толь бичиг-лавлах ном

хүчдэл- 3.10 стресс: Суналтын хүчийг холбоосын хөндлөн огтлолын нэрлэсэн хэмжээстэй харьцуулсан харьцаа.

Урагшаа эрэмбэлэх нь эрэмбэлэгдээгүй эерэг бүхэл тоонуудын жагсаалт (ихэвчлэн түлхүүр гэж нэрлэдэг) дээр ажилладаг бөгөөд тэдгээрийг өсөх дарааллаар эрэмбэлдэг. Энэ нь ихэнх тоглогчид тарааж буй картуудаа зохион байгуулж, нэг нэгээр нь карт авдагтай ижил аргаар хийгддэг. Дараах эрэмблэгдээгүй найман бүхэл тоон жагсаалтыг ашиглан ерөнхий процедурын үйлдлийг жишээ болгон үзүүлье.

27 412 71 81 59 14 273 87.

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

Давталт 0

27 ангилсан

Давталт 1Ангилалгүй 412 71 81 59 14 273 87

Эрэмбэлэгдсэн 27,412

Давталт 2Ангилалгүй 71 81 59 14 273 87

Эрэмбэлэгдсэн 27 71 412

Давталт 3Ангилалгүй 81 59 14 273 87

Эрэмбэлэгдсэн 27 71 81 412

Давталт 4Ангилалгүй 59 14 273 87

Эрэмбэлэгдсэн 27 59 71 81 412

Давталт 5Ангилалгүй 14,273 87

Эрэмбэлэгдсэн 14 27 59 71 81 412

Давталт 6Эрэмбэлэгдээгүй 273 87

Ангилсан 14 27 59 71 81 273 412

Давталт 7Ангилалгүй 87

Эрэмбэлэгдсэн 14 27 59 71 81 87 273 412

Дараах алгоритмд зөвхөн нэг жагсаалт үүсгэгдэх бөгөөд тоонуудын дахин зохион байгуулалтыг хуучин жагсаалтад хийнэ.

SIS алгоритм(Шууд оруулах ангилах). I(1), I(2), бүхэл тоонуудын дарааллыг эрэмбэлэх. . . ,I (N) өсөх дарааллаар.

1-р алхам.[Үндсэн давталт]

J←-ийн хувьд 2 рууН дамжуулан хийхалхам 4 од ;болонЗОГС.

Алхам 2.[Дараагийн бүхэл тоог сонгох] Тохируулах K←I(J); болон L←J−1.

Алхам 3.[Эрэмбэлэгдсэн бүхэл тоотой харьцуулах] байхадК

БА L≥1 тохируулна ууБи (L+1) ← I(L); болон L←L−1 од.

Алхам 4.[ Оруулсан ] Тохируулах I(L+1)←K.

QUICKSORT:Дундаж ажиллах хугацаа O(N ln N) бүхий эрэмбэлэх алгоритм

SIS алгоритмын үйл ажиллагаа удаашралтай байгаагийн гол шалтгаан нь товчлууруудын хооронд бүх харьцуулалт, солилцоо нь дарааллаар хийгддэг. a 1, a 2, . . . , мөн Нхөрш зэргэлдээх элементүүдийн хосуудад тохиолддог. Энэ арга нь харьцангуй том хэмжээтэй байхыг шаарддаг

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

38-р мөр 08 16 06 79 76 57 24 56 02 58 48 04 70 45 47 Үйлдэл

1 38 47 буурах j

5 04 38 солилцоо

6 08 38 өсөлт i

10 38 79 солилцоо

14 02 38 солилцоо

15 76 38 нэмэгдүүлэх i,>

16 38 76 солилцоо

17 38 56 буурах j

19 24 38 солилцоо

20 57 38 нэмэгдүүлэх i,>

21 38 57 солилцох, буурах

22 04 08 16 06 02 24 38 57 56 76 58 48 79 70 45 47

(1 2 3 4 5 6) 7 (8 9 10 11 12 13 14 15 16)

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

К.Хоор энэ санааг (QUICKSORT алгоритм) зохион бүтээж, маш үр дүнтэй хэрэгжүүлж, SIS алгоритмын ажиллах дундаж хугацааг O(N 2) дарааллаас O(N ln N) хүртэл багасгасан. Энэ алгоритмыг дараах жишээгээр тайлбарлая.

Зураг дээрх эхний эгнээний тоонуудын дарааллыг эрэмбэлэхийг хүсч байна гэж бодъё. 15. гэсэн таамаглалаар эхэлцгээе эхлээдЭнэ дарааллын (38) түлхүүр нь эцэст нь эрэмбэлэгдсэн дарааллын дунд гарч ирэх түлхүүрийг сайн ойртуулах үүрэг гүйцэтгэдэг. Бид энэ утгыг түлхүүрүүдийг сольж болох тэргүүлэх элемент болгон ашиглаж, дараах байдлаар үргэлжлүүлнэ. Бид I ба J гэсэн хоёр заагчийг суулгаж, би зүүн талаас нь тоолж эхэлдэг (I=1), J нь зүүн талаас (J=N) дарааллаар эхэлдэг. Харьцуулж байна а биТэгээд болон Ж. Хэрэв мөн би ≤a Ж, J←J−1 гэж тохируулаад дараах харьцуулалтыг хийнэ. Үргэлжлүүлье багасгахБид хүрэх хүртэл J a I >a J .Тэгээд газраа солицгооё a I ↔a J(Зураг 15, мөр 5, түлхүүр солилцох 38 ба 04), I←I+1 тохируулаад үргэлжлүүлнэ үү нэмэгдүүлэхБид хүрэх хүртэл би a I >a J .Дараагийн солилцооны дараа (мөр 10, 79↔38) бид J-ийг дахин бууруулж, J-г багасгах ба I-г нэмэгдүүлэх замаар энэ үйл явцыг дарааллын хоёр төгсгөлөөс "дунд" хүртэл I=J авах хүртэл үргэлжлүүлнэ.

Одоо хоёр баримт байна. Нэгдүгээрт, эхний байрлалд байсан түлхүүр(38) одоо эрэмбэлэгдсэн дарааллаар зохих байрандаа байна. Нэгдүгээрт, энэ элементийн зүүн талд байгаа бүх товчлуурууд бага байх ба баруун талд байгаа бүх товчлуурууд нь том байх болно.

Бүх дарааллыг эцэст нь эрэмбэлэхийн тулд зүүн ба баруун дэд дарааллаар ижил процедурыг хэрэглэж болно. 15-р зургийн сүүлчийн мөрөнд (22 дугаартай) I=J гарвал I=7 байна. Дараа нь (1,6) ба (8,16) дараалалд процедурыг дахин хэрэглэнэ.

Алгоритмын рекурсив шинж чанар нь эрэмблэгдээгүй хоёр дэд дарааллын хамгийн том (8,16)-ийн хамгийн гадна талын элементүүдийн индексийг стек дээр байрлуулж, дараа нь жижиг дэд дарааллыг (1,6) эрэмбэлэхийг үргэлжлүүлэх ёстойг харуулж байна.

15-р зургийн 4-р мөрөнд 04-ийн тоо 2-р байрлал руу шилжсэн бөгөөд (1,1) ба (3,6) дэд дарааллыг эрэмбэлэх шаардлагатай. (1,1) аль хэдийн эрэмбэлэгдсэн (02 дугаар) тул бид (3,6) эрэмбэлэх бөгөөд энэ нь эргээд (3,4) ба (6,6) гэсэн 6-р мөрөнд хүргэдэг. 7-р мөрөнд дэд дарааллыг (1,6) эрэмбэлсэн. Одоо бид стекээс (8,16) гарч ирээд энэ дэд дарааллыг эрэмбэлж эхэлнэ. 13-р мөрөнд эрэмбэлэх шаардлагатай (8,11) ба (13,16) дарааллыг агуулна. Бид (13,16) стек дээр тавьж, ангилах (8,11) гэх мэт. 20-р мөрөнд бүх дарааллыг эрэмбэлсэн.

QUICKSORT алгоритмыг албан ёсоор тайлбарлахын өмнө бид яг хэрхэн ажилладагийг харуулах хэрэгтэй. Бид [ LEFT (K), RIGHT (K) ] стекийг ашиглан эрэмблэгдээгүй байгаа дэд дарааллын хамгийн зүүн ба баруун талын элементүүдийн индексийг санах болно. Богино дэд дарааллыг ердийн алгоритмаар илүү хурдан эрэмбэлдэг тул QUICKSORT алгоритм нь ердийн аргаар эрэмбэлэхийн тулд ямар богино байх ёстойг тодорхойлдог оролтын параметртэй байдаг.

Хайх

Одоо өгөгдлийн бүтцээс мэдээлэл олж авахтай холбоотой зарим үндсэн асуудлуудын шалгалт руу орцгооё. Эрэмбэлэх өмнөх хэсгийн нэгэн адил бид бүх мэдээллийг гол утгуудаар тодорхойлж болох бүртгэлд хадгалсан гэж үзэх болно, i.e. рекорд R i нь K i-ээр тэмдэглэгдсэн гол утгатай тохирч байна.

Шугаман массив хэлбэрээр файлд санамсаргүй байдлаар байрлуулсан N бичлэг байна гэж үзье. Өгөгдсөн оруулгыг олох тодорхой арга бол товчлууруудыг дараалан хайх явдал юм. Шаардлагатай түлхүүр олдвол хайлт амжилттай дуусна; эс бөгөөс бүх түлхүүрүүдийг хайж олох ба хайлт амжилтгүй болно. Хэрэв боломжит бүх түлхүүрийн захиалга адил магадлалтай бол ийм алгоритм нь хамгийн муу болон дундаж тохиолдолд O(N) үндсэн үйлдлүүдийг шаарддаг. Хэрэв та файлыг түлхүүрээр урьдчилан захиалбал хайлтын хугацаа мэдэгдэхүйц багасах болно. Хэрэв файл хангалттай том, байнга ханддаг бол энэхүү урьдчилсан ажил нь утга учиртай болно.

Бид файлын голд очоод K i түлхүүрийг олсон гэж бодъё. K болон K i-г харьцуулж үзье. K=K i бол шаардлагатай бичлэг олдоно. Хэрэв К<К i ,то ключ К должен находиться в части файла, предшествующей К i (если запись с ключом К вообще существует) . Аналогично, если К i <К, то дальнейший поиск следует вести в части файла, следующей за К i . Если повторять эту процедуру проверки ключа К i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К i будет исключать из рассмотрения приблизительно половину непросмотренной части.

Энэ процедурын урсгал диаграммыг хоёртын хайлт, 16-р зурагт үзүүлэв

Алгоритм BSEARCH (Хоёртын хайлт) нь N≥2 бичлэг бүхий файлаас K товчлууртай бичлэгийг хайдаг бөгөөд түлхүүрүүд нь K 1 өсөх дарааллаар эрэмблэгдсэн байдаг.<К 2 …<К N .

Алхам 0.[Эхлэх] Тохируулах FIRST←1 ; LAST← N. (FIRST болон LAST нь файлын хараахан үзэж амжаагүй хэсгийн эхний болон сүүлчийн товчлууруудын заагч юм.)

1-р алхам.[Үндсэн гогцоо] байхад LAST≥FIRST дамжуулан хийхалхам 4 од.

Алхам 2.[Төв түлхүүрийг авах] Тохируулах I←|_(ЭХНИЙ + СҮҮЛИЙН)/2_| .(K i нь файлын хараахан үзэж амжаагүй хэсгийн дунд эсвэл зүүн талд байрлах түлхүүр юм.)

Алхам 3.[Амжилттай эсэхийг шалгана уу] Хэрэв K = K I тэгээд PRINT "Амжилттай дууссан, K I-тэй тэнцүү түлхүүр"; болонЗОГС fi.

Алхам 4.[Харьцуулалт] ХэрэвК < KI дараа нь тохируулна уу LAST←I-1 өөр тохируулсанЭХНИЙ←I+1 fi.

Алхам 5.[Хайлт амжилтгүй болсон] PRINT "амжилтгүй"; болонЗОГС.

BSEARCH алгоритмыг 17-р зурагт K=42 олоход ашигладаг.

Хоёртын хайлтын аргыг эрэмбэлэгдсэн файлыг хоёртын мод болгон төлөөлөхөд ашиглаж болно. 2-р алхамын эхний гүйцэтгэлд олдсон гол утга (K(8)=53) нь модны үндэс юм. Энэ утгын зүүн (1,7) ба баруун талын (9,16) гол интервалууд нь стек рүү түлхэгдэнэ. Дээд талын интервалыг стекээс гаргаж аваад 2-р алхамыг ашиглан дунд элементийг (эсвэл дундын зүүн талд байгаа элемент) олно. Энэ түлхүүр (K(4)=33) нь язгуурын утгаас бага бол язгуурын зүүн талын, эсрэгээр баруун талын дараагийн элемент болно. Шинээр нэмэгдсэн товчлуурын баруун болон зүүн талд байгаа энэ интервалын дэд интервалууд [(1,3) , (5,7)] нь стек дээр байрлана. 18-р зурагт 17-р зурагт заасан 16 захиалгат товчлуурт зориулж бүтээх хоёртын модыг үзүүлэв.

Хоёртын хайлтыг одоо энэ модыг үндсээр нь хайсан бичлэг рүү гатлах гэж тайлбарлаж болно. Хэрэв эцсийн оройд хүрч, заасан түлхүүр олдохгүй бол хайсан оруулга өгөгдсөн файлд байхгүй болно. Үндэсээс өгөгдсөн K түлхүүр хүртэлх нэг зам дээрх оройн тоо нь K-г олох гэж оролдох үед BSEARCH алгоритмаар хийсэн харьцуулалтын тоотой тэнцүү болохыг анхаарна уу.

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

Өгөгдлийг боловсруулахдаа өгөгдлийн мэдээллийн талбар болон түүний машин дахь байршлыг мэдэх нь чухал юм.

Дотоод болон гадаад ангилал байдаг:

Дотоод эрэмбэлэх - RAM-д эрэмбэлэх;

Гадаад эрэмбэлэх - гадаад санах ойд эрэмбэлэх.

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

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

Бид зөвхөн нэмэлт RAM ашигладаггүй төрлүүдийг авч үзэх болно. Ийм төрлүүд гэж нэрлэдэг "нэг газар".

Ангилах үр нөлөөг хэд хэдэн шалгуурын дагуу авч үзэж болно.

Ангилахад зарцуулсан хугацаа;

Ангилахад шаардагдах RAM-ийн хэмжээ;

Программист програм бичихэд зарцуулсан хугацаа.

Эхний шалгуурыг онцолж үзье. Ангилахад зарцуулсан цагтай тэнцэх хугацааг авч үзэж болно харьцуулалтын тооТэгээд хөдөлгөөний тооангилах үед.

Ангилах үеийн харьцуулалт, хөдөлгөөний тооны дараалал нь дотор байдаг

O (n log n) -ээс O (n 2) хүртэл;

O(n) бол хамгийн тохиромжтой, боломжгүй тохиолдол юм.

Дараахь ангилах аргуудыг ялгаж үздэг.

Хатуу (шууд) аргууд;

Сайжруулсан аргууд.

Хатуу аргууд:

Шууд оруулах арга;

Шууд сонгох арга;

Шууд солилцооны арга.

Хатуу аргуудын үр нөлөө нь ойролцоогоор ижил байдаг.

Шууд ангилах

Элементүүд нь оюун санааны хувьд бэлэн дараалал a 1 ,...,a i-1 болон анхны дараалалд хуваагддаг.

Алхам болгонд i = 2-оос эхлэн i-г нэгээр нэмэгдүүлэх үед i-р элементийг анхны дарааллаас хасаж, дууссан дараалал руу шилжүүлж, хүссэн газартаа оруулна.

Алгоритмын мөн чанар нь дараах байдалтай байна.

i = 2-оос n-ийн хувьд

X = a(i)

Бид a(1)...a(i) дундаас x-г оруулах байрыг олно

дараагийн i

Урагшаа эрэмбэлэх хоёр алгоритм байдаг. Эхнийх нь ямар ч саадгүй

Саад бэрхшээлгүй шууд оруулах ангилах алгоритм

i = 2-оос n-ийн хувьд

X = a(i)

j = i - 1-ээс 1 хүртэл

Хэрэв x< a(j)

Дараа нь a(j + 1) = a(j)

Үгүй бол Л руу яв

Эндиф

Дараагийн ж

L: a(j + 1) = x

дараагийн i

буцах

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

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

i = 2-оос n-ийн хувьд

X = a(i)

A(0) = x (a(0) - саад)

J = i - 1

байхад x< a(j) do

A(j +1) = a(j)

J = j - 1

Төгсгөлд нь

A(j +1) = x

дараагийн i

буцах

Дамжуулах алгоритмын үр ашиг

i-р шигших явцад Ci гол харьцуулалтын тоо хамгийн ихдээ i-1, хамгийн багадаа 1; Хэрэв бид N товчлуурын бүх сэлгэлт ижил магадлалтай гэж үзвэл харьцуулалтын дундаж тоо = i/2. Шилжилтийн тоо Mi=Ci+3 (саадыг оруулаад). Элементүүдийн аль хэдийн эрэмблэгдсэн эхний дарааллын үед хамгийн бага тооцооллыг хийдэг бол хамгийн муу тооцоо нь урвуу дарааллаар тавигдсан тохиолдолд гардаг. Зарим талаараа оруулах ангилах нь үнэхээр байгалийн зан үйлийг харуулдаг. Дээрх алгоритм нь тогтвортой эрэмбэлэх үйл явцыг тодорхойлсон нь тодорхой байна: тэнцүү товчлуур бүхий элементүүдийн дараалал өөрчлөгдөөгүй хэвээр байна.

Массивыг эсрэгээр нь эрэмбэлэх үед хамгийн муу тохиолдолд харьцуулах тоо, C max = n(n - 1)/2, өөрөөр хэлбэл - O (n 2). Сэлгээний тоо M max = C max + 3(n-1), i.e. - O (n 2). Хэрэв массив аль хэдийн эрэмблэгдсэн бол харьцуулах болон солих тоо хамгийн бага байна: C min = n-1; М мин = =3(n-1).

Шууд солилцоо ашиглан эрэмбэлэх (хөөс ялгах)

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

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

C min = n - 1, дараалал O(n),

мөн ямар ч хөдөлгөөн байхгүй

Шууд ангилах аргуудын харьцуулсан дүн шинжилгээ нь сонгодог хэлбэрээрээ солилцооны "эрэмбэлэх" нь орцыг ашиглан ангилах, сонгох хоёрын хоорондох хөндлөн огтлол юм. Хэрэв дээрх сайжруулалтыг үүн дээр нэвтрүүлсэн бол хангалттай эрэмбэлэгдсэн массивуудын хувьд хөөс ялгах нь давуу талтай.

Энэ аргыг ихэвчлэн хөөс ялгах гэж нэрлэдэг.

Шууд солилцооны аргын алгоритм

j = n-ээс i хүртэлх алхам -1

хэрэв a(j)< a(j - 1) then

Манай тохиолдолд нэг хоосон дамжуулалтаар дуусгасан. Элементүүдийг дахин нэг удаа харахгүйн тулд харьцуулалт хийх, үүнд цаг зарцуулахын тулд та шалгах нүдийг оруулж болно. fl, энэ нь үнэ цэнэтэй хэвээр байна худлаа, хэрэв дараагийн дамжуулалтын үеэр солилцоо хийгдээгүй бол. Доорх алгоритмд нэмэлтүүдийг тодоор тэмдэглэсэн болно.

fl = үнэн

хэрэв fl = худал бол буцаана

fl = худал

j = n-ээс i хүртэлх алхам -1

хэрэв a(j)< a(j - 1) then

fl = үнэн

Бөмбөлөгний аргын сайжруулалт бол сэгсрэгчээр ангилах бөгөөд дамжуулалт бүрийн дараа дотоод гогцооны чиглэл өөрчлөгддөг.

Шууд солилцооны эрэмбэлэх алгоритмын үр ашиг

Харьцуулалтын тоо C max = n(n-1)/2, дараалал O(n 2).

Хөдөлгөөний тоо M max =3C max =3n(n-1)/2, дараалал O(n 2).

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

Энэ аргыг хөзөр тоглоход өргөн ашигладаг. Элементүүд (картууд) нь оюун санааны хувьд аль хэдийн "бэлэн" дараалалд хуваагддаг A 1 , A 2 ,…, A i -1 , мөн "үлдсэн" (ангилаагүй) хэсэгт: A i , A i +1 ,…, A N. .

Аргын мөн чанар нь i-р алхам бүрт (i = 2-оос эхлэн) i-р элементийг ангилаагүй хэсгээс салгаж, "бэлэн" хэсэгт байрлуулж, зөв ​​газарт нь оруулдаг.

Аргын текстийн алгоритм:

1. Эхлэл.

2. i-д 2-оос N хүртэлх утгууд гарах хүртэл давталт хийнэ.
алхам = 1:

a) i-р элементийг (A(i)) A(0) нүдэнд байрлуулна;

б) j = -1 гэж оноож, өөрөөр хэлбэл j нь субьектийн зүүн талд (i-th) байрлах элементийн тоотой тэнцүү бөгөөд ингэснээр "бэлэн" дараалалд зогсож байна;

в) хэрэв A(0) ≥ A(j) бол A(0) элементийг A(j+1) нүдэнд байрлуулна, үгүй ​​бол A(j) элементийг A(j+1) нүдэнд байрлуулна, утгыг бууруулна. j-г нэг нэгээр нь хийгээд c алхамыг дахин хийнэ.

Зураг дээр. Зураг 1-д шууд оруулах аргыг ашиглан ангилах блок диаграммыг үзүүлэв.

Энэ арга нь дараах байдлаар ажиллана: i-р алхам дээр (i = 2-оос эхлэн) i-р элементийг чөлөөт нүдэнд байрлуулна (жишээлбэл, A(0)). Энэ элементийг зүүн талд байгаа "дууссан" хэсэгт байгаа элементтэй харьцуулна. Хэрэв A(0) элемент бага байвал харьцуулсан (j-р элемент) баруун тийш нэг байрлалаар шилжиж, дараа нь дараагийн элементийг харьцуулах зорилгоор авна. Хэрэв харьцуулах явцад A(0) элемент бага биш байвал тухайн элементийг харьцуулсан даруйд нь байрлуулна.

Цагаан будаа. 1. Шууд оруулах аргыг ашиглан ангилах схем

Зураг дээр. Зураг 2-т шууд оруулах аргыг ашиглан ангилах ажлыг гүйцэтгэх жишээг үзүүлэв.

Анхны дараалал
	A (0)
I = 2
I = 3
I = 4
I = 5
I = 6
I = 7
I = 8
Үр дүн

Цагаан будаа. 2. Шууд оруулах ангиллын жишээ

Шууд эрэмбэлэх нь эрэмбэлэгдсэн өгөгдөл дараалсан (нэг нэгээр нь) ирэх тохиолдолд илүү тохиромжтой.

Шууд сонголтын эрэмбэ

Аргын мөн чанар нь дараах байдалтай байна. "Үлдсэн" (ангилаагүй) хэсгийн хамгийн жижиг элементийг сонгож, эхний элементтэй (ижил ангилаагүй хэсэгт) сольсон. Үүний дараа эрэмбэлэгдээгүй хэсгийн уртыг нэг элементээр (эхний нэг) багасгаж, бүх процесс нь (n – 1) элементээр, дараа нь (n – 2) элемент гэх мэтээр зөвхөн нэг элементтэй болтол үргэлжилнэ. хамгийн том элемент.

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

Аргын текстийн алгоритм:

1. Эхлэл.

2. i-д 1-ээс N – 1 хүртэлх утгууд гарах хүртэл давталт хийнэ.
алхам = 1:

a) одоогийн (i-р) элементийг санах ойн зарим нүдэнд (X) байрлуулж, одоогийн элементийн серийн дугаарыг (i) санах (х хувьсагч K);

б) j нь i + 1 (өөрөөр хэлбэл i-ийн хажууд байгаа элементээс) N хүртэлх утгууд байх үед давталтыг гүйцэтгэнэ, алхам = +1:

гогцооны бие: хэрэв X > A(j) бол A(j) элементийг X нүдэнд байрлуулж, K нүдэнд түүний тоог санах;

в) A(K) = A(i) ба A(i) = X онооно.

Зураг дээр. Шууд сонгох аргыг ашиглан ангилах ажлыг гүйцэтгэх жишээг Зураг 3-т үзүүлэв.

Анхны дараалал	44						06
I = 1		55	12
I = 2			55			18
I = 3				42		55
I = 4					94		44
I = 5						55	94
I = 6							94	67
I = 7

Цагаан будаа. 3. Шууд сонголтоор ангилах жишээ