Лк12

Модонд нэвтрэлт хийх аргууд

Байгаль дээр үндэс, мөчир, навч бүхий ургамлыг мод гэдэг. Компьютерын ухаанд модтой бүтцийн хувьд төстэй өгөгдлийн бүтцийг мөн мод гэдэг. Гэхдээ компьютерын ухаанд модыг уруу харуулж зурдаг. Мод гэдэг бүтцийн хувьд үндэс бол хамгийн чухал элемент бөгөөд нэг модонд цорын ганц үндэс байна. Үндсээс мөчир, мөчрөөс навч гардаг. Салаалж ургасан модны хэсгийг дэд мод гэнэ. Нэг зангилаанаас хэдэн элемент – мөчир/навч салаалсан гэдгээс нь хамааруулж хоёртын, N –тын мод гэж ялгаж болдог. Тэдэн дотор хоёрын мод онцгой байр эзэлдэг бөгөөд хоёртын модонд суурилсан олон хэрэглээ байдаг. Модны тухай ярихад өвөг эцэг, эцэг, хүүхэд, ахан дүүс гэсэн ухагдахуунуудыг бас хэрэглэдэг.

Мод нь ямар нэг нөхцөлийг хангах тодорхой дүрмээр зохион байгуулагдсан зангилаанууд болон тэдгээрийг холбосон холбоосуудыг агуулдаг. Зангилаа нь мэдээлэлийг хадгалах ердийн нэг объект ба холбоос нь хоёр зангилааны хоорондын харилцааг тодорхойлдог. Холбоосоор холбогдсон модны дараалсан зангилаануудын жагсаалтыг зам гэнэ.

Модыг ингэж сурах нь байгаль дээрхтэй адилтгаж ойлгоход хэрэгтэй ч компьютерын ухаанд дараах байдлаар зурдаг. Амьдрал дээр мод бүтцээр илэрхийлж болох, илүү тохиромжтой олон тооны өгөгдлийг нэрлэж болно. Жишээ нь хүмүүсийн ургийн бичиг, байгуулгын зохион байгуулалтын бүтэц, Байгаль, техникийн нийлмэл системийн бүтэц г.м. Өгөгдлийн мод бүтэц дээр боловсруулалт хийнэ гэдэг үнэн чанартаа модны үндсээс навч хүртэл дээшээ, доошоо салаа мөчрөөр дамжин нэвтрэлт хийнэ гэсэн үг. Хоёртын модонд нэвтрэлт нь сонгосон алгоритмаасаа хамаарч Preorder, Inorder, Postorder, Levelorder гэсэн 4 төрөлд хуваагддаг.

Preorder нэвтрэлт:

public static void preOrder(BinaryTreeNode t)

{

   if (t != null)

  {

      visit(t);

      preOrder(t.leftChild);

      preOrder(t.rightChild);

   }

}

inOrder нэвтрэлт:

public static void inOrder(BinaryTreeNode t)

{

  if (t != null)

  {

     inOrder(t.leftChild);

     visit(t);

     inOrder(t.rightChild);

  }

}

PostOrder нэвтрэлт:

public static void postOrder(BinaryTreeNode t)

{

   if (t != null)

   {

      postOrder(t.leftChild);

      postOrder(t.rightChild);

      visit(t);

   }

}

LevelOrder нэвтрэлт:

public static void LevelOrder(BinaryTreeNode t)

{

   while (t != null)

  {

      t –д зочлоод хүүхдүүдийг нь FIFO дараалалд хийнэ;

      зангилааг FIFO дарааллаас устгаж, дуудна t;

     // дараалал хоосон бол устгал null –г буцаана

   }

}

9-11

Лк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-р зургаар үзүүллээ.

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-р зургаар үзүүллээ.

6

Графын онол

Графын онол нь орой болон тал （мөчир）-уудын олонлогоос тогтох Граф гэх зүйлийн мөн чанарыг судалдаг математикийн нэг салбар ухаан юм.

Компьютерийн Өгөгдлийн бүтэц болон алгоритм зэрэгт өргөнөөр хэрэглэгддэг.

Граф

Галт тэрэг ашиглан нэг өртөөнөөс нөгөөд очиход уг 2 өртөө （орой） нь төмөр зам (тал) -аар холбогдсон эсэхийг мэдэх хэрэгтэй болохоос төмөр замын сүлжээ нь ямар хэлбэр дүрс үүсгэж байгаа нь чухал биш байх нь олонтаа.

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

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

6 орой, 7 талаас тогтох графын жишээ

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

Графын математик тодорхойлолтууд[

Чиглэлт граф

 нь оройнуудын олонлог,  нь талуудын олонлог байг. Талуудыг оройнуудын хост харгалзуулдаг  функц тодорхойлогдсон гэж үзье.

.

Тэгвэл чиглэлт граф  нь

гэж тодорхойлогдоно.

Чиглэлгүй граф

 нь  -ийн бүх дэд олонлогуудын олонлог байг. Талд хэд хэдэн оройг харгалзуулдаг g функц оршин байг.

Энд дурын  талын хувьд g(e) = (v₁, v₂) хэлбэрээр 2 оaрой харгалздаг гэж үзье. Тэгвэл чиглэлгүй граф G нь

гэж тодорхойлогдоно. g нь 3-аас олон оройг талд харгалзуулдаг функц байвал уг графыг хайпэр граф гэдэг.

E-г анхнаасаа ямар нэг олонлогийн дэд олонлог гэж үзвэл дээрх тодорхойлолтоос функцийг нь хасч болно. Үүний тулд чиглэлт графт E-г V×V-ийн дэд олонлог, чиглэлгүй графт E-г P(V)-ийн дэд олонлог гэж ойлгоход болно.

Үндсэн ойлголтууд[

Граф нь тодорхойлолтоосоо хамааран талууд нь жин（өртөг）-тэй байж болно. Ийм графыг Жинтэй граф гэж нэрлэнэ. G графын оройнуудын олонлогийг V(G)、талуудын олонлогийг E(G) гэж тэмдэглэх нь элбэг.

e талын холбож буй оройнуудыг төгсгөлүүд гэх бөгөөд тэдгээр нь e-гээр хөрш гэж хэлнэ Мөн нэг оройгоос гарсан 2 талыг зэргэлдээ талууд гэнэ. Хэрэв талын 2 төгсгөл нь давхцаж байвал уг талыг гогцоогэдэг. Бас 2 оройг холбосон тал хэд хэд байвал тэдгээр талыг давхар замууд гэнэ. Гогцоо болон давхар замгүй графыг энгийн граф гэдэг.

G ба G' графуудын хувьд G' -ийн оройнуудын болон талуудын олонлог нь харгалзан G-ийн оройнуудын болон талуудын олонлогийн дэд олонлог байвал G' -г G-ийн дэд граф гэж нэрлэдэг. Эсрэгээрээ, Gнь G' -ийн өргөтгөсөн граф гэдэг. Тухайлбал уг 2 графын оройнуудын олонлог нь давхцаж байвал нэг нь нөгөөгийнхөө үржигдэхүүн граф гэнэ.

Графын ямар нэг v орой төгсгөл нь болдог талуудын тоог уг оройн эрэмбэ гээд d(v) гэж тэмдэглэнэ. Түүнчлэн чиглэлт графын хувьд v оройгоос гарсан талуудын тоог v-ийн гарсан эрэмбэ, хүрч ирсэн талуудын тоог v-ийн орсон эрэмбэ гэнэ. Дурын v оройн хувьд d(v) = k гэсэн нөхцөл биелж байвал k-зөв граф гэнэ. k-ийн хувьд k-зөв графыг товчоор зөв граф гэдэг. G графын хамгийн бага эрэмбэ бүхий оройн тоог δ(G), хамгийн их эрэмбэ бүхий оройн тоог Δ(G)-ээр тэмдэглэх нь элбэг. Мөн эрэмбэ нь 0 байх оройг Саланги цэг гэдэг.

Хөрш оройнуудаар дамжсан v₁, e₁, v₂, e₂, ..., e_n-1, v_n дарааллыг зам, нэг ч тал давхардаж ороогүй бол энгийн зам гэдэг. Мөн эхлэл, төгсгөл нь давхцах замыг битүү зам（цикл） гэнэ.

Дурын 2 орой нь талаар шууд холбогдсон байвал бүтэн граф гэх бөгөөд n оройтой бүтэн графыг K_n-ээр тэмдэглэдэг.