7-8

Лк7

Өгөгдлийн урсгалын диаграмийг өргөтгөх CASE хэрэгсэлүүд

     Case Tools

Ямарч системийг сайжруулах, хөгжүүлэх олон хэрэгсэл байдаг. Харин мэдээллийн системийг хөгжүүлэхэд case tools хэмээн нэрлэгддэг автоматжуулалтын техник хэрэгслүүдийг өргөн хэрэлэж байна. (Computer Aided Software Engineering). Case tools нь системийн шинжээчийн ажлыг хөнгөвчлөн үр бүтээмжийг дээшлүүлэх, системийн хөгжүүлэлтийн эхэн үеэс төгсгөл хүртэлх бүхий л хугацааны туршид ажлуудыг нэгтгэн зохион байгуулах улмаар хэрэглэгчтэй үр ашигтай харилцах боломжоор хангадаг. Case tools нь :

·         Системийн шинжээчийн ажлын үр бүтээмжийг дээшлүүлэх

·         Шинжээч болон хэрэглэгчийн хоорондын харилцааг сайжруулах

·         Хөгжүүлэлтийг хийх ажлуудыг нэгтгэж, тодорхой дараалалд оруулах

·         Сайжруулалтыг оновчтой болгох зэрэг давуу талуудтай.

Лк8

Эрэмблэлтийн энгийн аргууд

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

Эрэмбэлэлтийн алгоритмуудыг судлах эхний хэсэгт бид эрэмбэлэлтийн энгийн аргуудтай танилцах юм.Эрэмбэлэлт нь хийхэд энгийн аргуудыг сонгох зарим хэрэглээ ба шаардлага байдаг.Ер нь эрэмбэлэх үйлдэл нь программын ажлын явцад зөвхөн ганц удаа (эсвэл цөөхөн) хийгддэг.Хэрэв эрэмбэлэх өгөгдлийн тоо нь асар олон биш бол энгийн эрэмбэлэлтийн аргууд нь илүү үр ашигтай байхаас гадна нэвтрүүлэлт болон шалгалт хийихэд хялбар байдаг.Энгийн аргууд цөөхөн өгөгдлийн хувьд ямагт тохиромжтой байдаг.Өгөгдлийн өөр нэг өгөгдөх хэлбэр бол өгөгдлүүд нь бараг эрэмбэлэгдсэн (аль эсвэл аль хэдийн эрэмбэлэгдсэн) эсвэл маш олон тооны тэнцүү өгөгдлүүд (түлхүүр талбарын өгөгдөл) агуулсан байж болно. Ийм бүтэцтэй өгөгдлүүдэд эрэмбэлэлтийн энгийн аргууд харьцангуй илүү үр ашигтай гүйцэтгэгддэг. Эрэмбэлэлтийн аргуудыг судлахын өмнө эрэмбэлэлтийн зарчим ойлголт болон нэр томьёололтой танилцья.Эрэмбэлэгдэх өгөгдөл нь хэд хэдэн талбаруудаас тогтох бичлэгүүд байж болох ба энэ тохиолдолд эрэмбэлэлтийг аль нэг талбарын утгаар хийдэг.Энэ талбарыг түлхүүр гэж нэрлэдэг.Энэ номд эрэмбэлэлтийн алгоритмуудын программыг ойлгомжтой,хялбархан болгох зорилгоор бүхэл тоо, тэмдэгт зэрэг энгийн өгөгдлийн төрөлтэй массивийн хувьд эрэмбэлэлтийг гүйцэтгэхээр тодорхойлж өгсөн. Хэрэв эрэмбэлэгдэх нийт өгөгдөл нь санах ойд хүрэлцэхүйц бага хэмжээтэй бол дотоод эрэмбэлэлт гэнэ.Хэрэв өгөгдлийн хэмжээ нь дотоод эрэмбэлэлтээр хийгдэхээргүй их хэмжээтэй бол гадаад эрэмбэлэлт гэнэ.Өөрөөр хэлбэл гадаад эрэмбэлэлтийг диск эсвэл соронзон туузан дээр гүйцэтгэдэг.Энэ номонд авч үзэх аргууд нь үндсэндээ дотоод эрэмбэлэлтийн аргуудад хамаарна. Эрэмбэлэлтын аргуудыг харьцуулах гол хэмжүүр бол тэдгээрийн ажиллах хугацаа юм.Эрэмбэлэлтийн алгоритмын түлхүүр үйлдэл нь харьцуулах ба утга солилцох гэсэн үндсэн үйлдлээр тодорохойлогддог.Гэвьч эрэмбэлэлтийн алгоритмын хувьд харьцуулалтын тоог илүү сонирхдог.Алгоритмын ажиллах хугацааг хамгийн муу ба дундаж гэсэн хоёр тохиолдлын хувьд хэлэлцдэг.Бид N өгөгдлийн хувьд ажиллах хугацаа нь N² шаардах алгоритмаас эхлээд N шаардах алгоритмуудыг үзэх болно. Эрэмбэлэлтийн алгоритмын өөр нэг хэмжүүр бол шаардагдах нэмэлт санах ойн хэмжээ юм.Зарим алгоритм (шаардагдах маш бага зайг үл тооцвол) нэмэлт зай ашигладаггүй байхад зарим нь N өгөгдлийг давхар хадгалах нэмэлт зайг шаардаж байдаг. Эрэмбэлэлт хийгдэх өгөгдөл нь массивт эсвэл жагсаалтад хадгалагдаж болно. N өгөгдлийн жагсаалтадхадгалагдах үед N заагчийн нэмэлт үай шаарддаг.Эрэмбэлэлтийн алгоритмуудыг ашиглан жагсаалтыг эрэмбэлэх хоёр хэлбэр байдаг.Зангилааны өгөгдлийн хэмжээ бага тохиолдолд зангилааны зөвхөн өгөгдлийг солилцох нь тохиромжтой байдаг бол зангилааны өгөгдлийн хэмжээ асар том (тухайлбал олон талбараас тогтох бичлэг) тохиолдолд зангилааны заагчуудыг ашиглан бүхэл зангилааг солилцох нь илүү тохиромжтой.Өөрөөр хэлбэл бичлэгийн талбар бүрийн утгыг солилцохын оронд зөвхөн хоёр зангилаанд хамаарах заагчуудын утгыг өөрчилнө.Жагсаалт эрэмбэлэх жишээг энэ бүлгийн төгсгөлд сонгон эрэмбэлэх аргыг ашиглан нэвтрүүлэх болно. 

Сонгон эрэмбэлэх арга

selectionSort ( ) функц нь нэгэнт загвар функцээр тодорхойлогдсон болохоор бид ямарч өгөгдлийн төрөл бүхий массивийг энэн функцэд дамжуулан эрэмбэлж чадна.Жишээлбэл int ба char төрөлтэй массивуудыг дээрх функцэд хэрхэн дамжуулахыг харцгаая

int a [ 8 ] = { 77, 33, 44, 11, 88, 22, 66, 55 } ;

char s [ 15 ] = {‘a’ , ‘b’, ‘o’ ,  ‘r’,  ‘t’, ‘n’ ,

‘g’, ‘e’, ‘x’,  ‘a’, ‘m’, ‘p’, ‘l’, ‘e’} ;

selectionSort ( a, 8) ;

selectionSort ( s, 15) ;

эрэмбэлэлтийн энэн энгийн арга нь маш цөөхөн өгөгдөлтэй массивийн хувьд сайн ажилладаг.Сонгон эрэмбэлэх алгоритм нь өгөгдлийн анх өгөгдөх дарааллаас үл хамааран ойролцоогоор n² харьцуулалт, n солилцох үйлдэл хийдэг.Дээрх алгоритмаас ажиглавал i гадаад давталтын алхам бүрт нэг солоилт ба n-1 харьцуулалт хийж байна. Иймээс нийт харьцуулалтын тообуюу алгоритмын ажиллах хугацааг илэрхийлэх £ ( n ) функцийн утга нь £ ( n ) = (n-1) + (n-2) +….+ 2 + 1 = n(n-1)/2 = O (n²) гэж тодорхойлогдоно. Сонгон эрэмбэлэгдэх алгоритм нь бага түлхүүртэй том бичлэг бүхий өгөгдлийн хувьд шугаман ажилладаг.Жишээлбэл түлхүүр нь 1 үг байхад бичлэг М үгээс тогтож болно.Энэ тохиолдолд 1 нэгж хугацаа зарцуулж байхрд солилцох үйлдэлд М нэгж хугацаа зарцуулна. Иймд NM хэмжээтэй нийт өгөгдлийн эрэмбэлэгдэхэд N²харьцуулалт ба NM солилцох үйлдэл хийнэ.Хэрэв N=O(M) бол эрэмбэлэлтийн бүхэл өгөгдлийн хувьд шугаман гэж хэлж болох юм.

Оруулан эрэмбэлэх арга

Оруулан эрэмбэлэх алгоритм нь сонгон эрэмбэлэлтийн алгоритмуудын нэг бөгөөд магадгүй илүү уян хатан , үр ашигтай байж болно.Энэ аргын үндсэн элемент нь эрэмбэлэгдсэн массивт эрэмбэлэлтийг алдагдуулахгүйгээр шинээр элемент охуулах үйлдлээр тодорхойлогддог.Өөрөөр хэлбэл эрэмбэлэгдсэн элементүүдийн шинэ элементээс их элементүүдын нэг байрлал баруунтийм шилжүүлэх байдлаар орвол зохих байрлалыг чөлөллж өгдөг.Оруулан эрэмбэлэх алгоритмыг дараах InsertionSort ( ) функцээр үзүүллээ. Шинээр оруулах элементийг гадаад давталт I –гээр массивийн хоёр дахь элементээс эхлэн авна.Эхний алхамд хамгийн эхний элементтэй харьцуулан байрлалыг нь олсноор хоёх элементтэй эрэмбэлэгдсэн массив гарган авна.Удаах алхамд, үүсгэсэн хоёр элемелнт бүхий эрэмбэлэгдсэн массвтаа массивийн гурав дахь эрлементийг оруулах байдлаар масвинй төгсгөл хүртэл бүх элементийн хувьд давтан гүйцэтгэнэ. Дээрх алгоритмын while дотоод давталтаар шинэ элементийг эрэмбэлэгдсэн гэх түүний өмнөх элементүүдээс тогтох массивийн хэсэгт оруулж өгөх үйлдэл хийгдэнэ.Энэ давталт нь шинэ элементээс бага элемент тааралдтал хийгдэх ба харин ир элементүүд нь хойшоо (баруун тийш) нэг шилсэн шинэ элементэд зай гаргах болно.Хэнрэв шинэ элемент өмнөх бүх элементүүдээс бага байх тохиолдолд j индекс багассаар массивийн хэмжээнээс (тэгээд бага болох ) өнгөрч болох юм.Энэ алдааг зохицуулах зорилгоор while давталтанд j>=0 гэсэн нөхцөлийг давхар оруулж өгсөн.Гэвч энэ нөхцөл нь j –ийн утга тэгээс бага болоогүй тохиолдолд бүрт илүүдэл шалгалтыг гүйцэтгэж байна.ЭНэ илүүдэл шалгалтаас зайлсхийих нэг арга бол масствийн эхний элементэд хязгааргүй бага (массивийн элементүүдээс харьцангуй бага) утга олнон ашигладаг.Эхний энэ элементийг харуул элемент гэж нэрлэдэг.Ингэснээр массивийн эхний элементийг массивийн үндсэн элементээр авахгүй  бөгөөд дотоод давталтыг while ( element <a[ j ] ) гэж гүйцэтгэнэ.Гэвч ихэнх тохиолдолд массивийн элементүүдийн утгын доод хязгаарыг урьдчилан тодорхойлох боломжгүй байдгаас харуул элементийн утгыг тогтооход хүндрэлтэй байдаг.Энэ алгоритмыг найман бүхэл тоон массивт хэрхэн ажиллахыг

Бөмбөлгөн эрэмбэлэлтийн арга

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

Template<class Type>void bubbleSort (Type a [ ] , int n)   {

for ( int i=n-1; i>0 ; I – -)

for ( int i=0; i<i ; j ++)

if (a[ j ] > a [ j+1 ] ) swap (a, j , j+1) ;

}

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

Индексээр эрэмбэлэх арга

Зарим тохиолдолд өгөгдөлүүд маш том бичлэгээс тогтох үед түүнийг эрэмбэлэхэд зарцуулах хугацааны дийлэнх хэсэг солих үйлдэлд хамаардаг.Энэ тохиолдолд индексийн массив үүсгэж, өгөдөлд өөрчлөлт хийлгүйгээр элементүүдийн индексийг уг өгөгдөл эрэмбэлэгдсэн байдлаар индексийн массив хийдэг.Эрэмбэлэлтийн энэ аргын үед өгөгдөл хадгалах a [ ] массиваас гадна индекс хадгалах нэмэлт p [ ]  индексийн массивыг авч явдаг. Индексийн массив нь өгөгдлийн массив дахь өгөгдлүүдийн индексийг хадгалах ба индексийн массивт  байрлах дарааллаар өгөдлийн массивт хандвал эрэмбэлэгдсэн өгөгдлүүд гарна.Өөрөөр хэлбэл p [1] нь массивийн хамгийн бага элементийн индексийг p [2] нь a [ ] нь массивийн удаах бага элементийн индексийг гэх байдлаар хадгална.Эрэмбэлэлт нь маш том бичлэгүүдийг шилжүүлэн солихийн оронд зөвхөн индексүүийн хооронд солих үйлдэл хийдэг. 10.3 зургаар индексийн аргаар эрэмбэлэхийн өмнөх ба эрэмбэлсний дараах a [ ] ба p [ ] массивуудыг харьцуулан үзүүллээ. Индексийн массив үүсгэхдээ оруулан эрэмбэлэх аргыг ашигласан функцийн кодыг доор үзүүллээ.

Shell-ийн арга

Энэ (анх D . L . Shell боловсруулсан) алгоритм нь оруулан эрэмбэлэх аргыг элементийн эцсийн байрлалдаа орох шилжилтийг хурдасгатан сайжруулсан. Оруулан эрэмбэлэх арна нь харьцуулалтыг өмнөх элементүүдтэй дэс дараалан хйиж, шилжилтийг зөвхөн зэргэлдээ байрлалын хувьд хийдэг учраас удаан байдаг. Жишээлбэл хамгийн бага элемент массивын төгсгөлд байвал N Шилжилт хийсний дараа байрлалаа олох боломжтой болно. Тэгвэл shell-ийн арга нь оруулан эрэмбэлэх арын зайтайгаар хол хол хийдэг. Тухайн алхмын зайг h гэвэл массивын h алхам дахь элемент бүрийн хувьд эрэмбэлэлтийг хийх ба массивт биенээсээ үл хамаарах h ширхэг эрэмбэлэгдсэн дэд хэсэг үүснэ. Өөрөөр хэлбэл эхний эрэмбэлэгдсэн хэсэгт массивын o , h, 2h _ индекстэй элементүүд, удаах эрэмбэлэгдсэн хэсэгт 1, h+1, 2h+1 _ индекстэй элементүүд хамаарах байдлаар i=0,1,…, h-1 хувьд i, (i+h), (i+2h),… индекстэй элементүүдээс тогтох h ширхэг эрэмбэлэгдсэн дэд хэсэг үүснэ. Энэ үйлдлийн h- ийн утга нь 1-ээр эхлэх дурын тоонуудын дараалал байж болно. Алгоритмын эрэмбэлэлт нь алхмын зай h – ийн авах утгуудын дарааллаас маш их хамаардаг. Туршилт болон судалгаагаар эрэмбэлэлтийг үр ашигтай болгох h- ийн авах утгуудын дарааллаас маш их хамаардаг. Туршилт болон судалгаагар эрэмбэлэлтийг үр ашигтай болгох h-ийн нэг дарааллыг сонирхцгооё. h1=1 гэвэл hs+1=3hs +1гэж тодорхойлогдох ба дараалал h1+2 ≥N байх h, утгаар төгсгөнө. Эндээс 1, 4, 13, 40, 121, 364, 1093,… гэсэн дараалал үүснэ.

Тархалтыг тоолох

Аливаа бодлогод эрэмбэлэлтийн аргуудаас шууд авч ашиглахын өмнө уг бодлогынхоо онцлог шинж , нөхцөл байдалд тохируулан сонгох, цаашилбал алгоритмыг өөрчлөх болон шинэ арга сэтгэх хэрэгтэй.Тухайлбал, 1-ээс N ялгаатай ( давтагдахгүй ) утгатай түлхүүр талбар бүхий N өгөгдлийг эрэмбэлэх алгоритмыг тодорхойлъё.Энэ бодлогыг нэмэлт b массивын тусламжтайгаар

For ( i=0 ; i<N ; i++ ) b[ a [ I ] ] = a [ i ] ;

Гэж хялбархан шийдэж болно.( Хэрэв туслах массив ашиглахгүй шэвэл sort ( ) функцэд өмнө нь  ашиглаж байсан арай төвөгтэй аргаар шийдэж болно.Өөрөөр хэлбэл бид бүх элементийн эрэмбэлэгдвэл зохих байрлалыг мэдэж байгаа.  Өөх нэгэн бодлогын нөхцөлийг авч үзье.Энэ бодлого нь 0-ээс м-1 түлхүүр утгатай N (N>M) өгөгдлийг эрэмбэлэх юм.Тархалтыг тоолох алгоритмаар энэ бодлогыг шийдэж болно.Энэ алгоритмын санаа нь ялгаатай түлхүүр утгуудын давталтыг ( масстивт хичнээн орсоныг ) тоолон, дараа н давталтын тоог ашиглан элементүүдын байрлалыг тодорхойлох юм.Энэ аргыг дараах кодын хэсгээр үзүүллээ.

For ( i=0 ; i<M ; i++ ) count [ I ] = 0 ;

For ( i=0 ; i<M ; i++ ) count [ a [ i ] ++ ;

For ( i=0 ; i<M ; i++ ) count [ I ] += count [ i-1 ] ;

For ( i=N-1 ; i>=0 ; I — ) b [ –count [ a [ I ] ] ] = a [ I ] ;

For ( i=0 ; i<N ; i++ ) a [ I ] = b [ I ] ;

Дээрх кодыг хэрхэн ажиллахыг 10.5-р зургийн эхний мөрөн дэхь тэмдэгтүүдээс

тогтох массиваар тайлбарлая.Эхний давталтаар count массивийн элементүүдэд 0 утга олгоно.Удаах давталтаар түлхүүр утгууд хичнээн давтагдсаныг тоолж, үр дүнг count массивийн харгалзах индекстэй элементэд хийнэ.Жишээлбэл: а массивт 0 түлхүүр 2 удаа давтагдсан учир count [ 0 ] = 2 , 1 утгатай түлхүүр 3 удаа учир count [ 1 ] = 3 гэх мэтээр count [ 2 ] = 3 , count [ 3 ] = 2 гэсэн утгуудыг авна.Гурав дахь давталтаар count [ 0 ] = 2 , count [ 1 ] = 5 , count [ 2 ] = 8 , count [ 3 ] = 10 гэсэн утгуудыг авна.Энэ нь 0 утгатай түлхүүр ь массивийн 2 дахь элементийг хүртэл, 1 утгатай түлхүүр ь массивийн 5 дахь элементийг хүртэл, 2 утгатай түлхүүр ь массивийн 8 дахь элементийг хүртэл, 3 утгатай түлхүүр ь массивийн 9 дахь элемент хүртэл тус тус байрлахыг тодорхойлж байна.

Жагсаалт эрэмбэлэх

Сонгон эрэмбэлэх алгоритм ашиглан жагсаалтыг зөвхөн зангилааны өгөгдлийн утгуудыг солилцох аргаар эрэмбэлье. 6-р бүлэгт тодорхоблсон нэг холбоост жагсаалыг шууд ашиглан swap_value ( ) ба sort ( ) гишүүн функцуудийг нэмж тодорхойльё. Харин жагсаалтийг эрэмбэлэхдээ заагчийн утгаар буюу бүхэл зангилаагаар нь солилцох аргаар программ бичих даалгаврыг уншигч танд үлдээе.Энэ тохиолдолд оруулан эрэмбэлэх аргыг ашиглах нь илүү тохиромжтой.Учир нь жагсаалтын дунд элемент оруулахдаа түүнээс хойш орших элеиентүүдийг шилжүүлэх шаардлаггүй ба оруулан эрэмбэлэх арга нь харьцуулалтын тоог багасгадаг.Жагсаалтыг зангилааны хувьд эрэмбэлэх үед тухайн зангилааны өмнөх ыа хойдхи зангилаануудыг мэдэж байх шаардлагатай.Тиймээс нэмэлт заалтууд ашиглах эсвэл хоёр холбоост жагсаалтыг ашиглавал кодчлолыг хялбархнаар шийдэж болно.

Хурдан эрэмбэлэлтийн арга

Хурдан эрэмбэлэлтийн (quick sort)алгоритм нь хэсэглэн-нэгтгэх аргыг ашиглан эрэмбэлэлт хийдэг.ЭНэ алгоритм нийт өгөдлийг хоёр хэсэгт хуваан , хэсэг бүрт уг аргыг рекуст йшиглан эрэбэлэдэг.

quickSort ( ) функц нь partition ( ) функцээр хуваагдах зшшн ба баруун дэд хэсэг бүрийн хувьд өөрийгөө рекурсээр дууддаг. partition ( ) функц нь массивийн дараах нөхцөлийг хангах гурван хэсэгт худаагддаг.Үүнд:

(1)   Эцсийн байрлалдаа орсон i индексбүхий a [ i ] элемент

(2)   a [ i ]-ээс бага элементүүдийг агуулах a [ l ] … a [ i-1 ] зүүн дэд хэсэгт

(3)   a [ i ]-ээс их элементүүдийг агуулах a [ i+1] … a [ r ]баруун дэд хэсэгт

гэсэн гурван хэсгүүд багтана.Энэ хуваалтыг дараах аргаар хялбархан нэвтрүүлж болно.Үүний тулд эхлээд эцсийн байрлалдаа орох элементийг Тухайлбал a [ r ] сонгоно.Дараа нь a [ r ] элементээс их элемент тааралдттал массивийн зүүн талаас, a [ r ]элементээс бага элемент тааралдтал массивийн баруун талаас хайлт хийнэ.Хайлтаар олдсон хоёр элементийг хооронд нь солж хайлтийг дахин цааш үргэлжилүүлнэ.Хайлт нь массиввийн хоёр талаас хумигдсаар тодорхой нэг байрлалд зөрөх тэр мөчид зогсоно.Энэ байрлал нь a [ r ] элементийн орох байрлал бөгөөд a [ r ]-ээс бага элементүүд зүүн талд, их элементүүд баруун гар талд байрласан байх болно.Энэ үйлдлийг бидний жишээ өгөгдөл хувьд хэрхэн гүйцэтгэхийг 11,1-р зургаар үзүүллээ.