АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Insertion sort бол массивыг эрэмбэлэх энгийн аргуудын нэг гэдгийг бид мэднэ.

Тэгвэл массивыг эрэмбэлэхэд  элементийн байрыг солих үйлдэл нийт хэдэн удаа хийгдэхийг тооцоолно уу?

Массивын i-дугаар элементийн байрыг солих үйлдэл хэдэн удаа хийгдэх тоог k[i] гэвэл нийт элементийн

байрыг солих үйлдлийн тоо k[1] + k[2] + k[3] + … + k[n] байна.

Тухайлбал

arr=[4, 3, 2, 1] массивыг авч үзье.

[4,3,2,1]  

[3,4,2,1]   1 удаа

[2,3,4,1]   2 удаа

[1,2,3,4]   3 удаа

Нийт шилжилт (байр сэлгэлт) = 1 + 2 + 3 = 6

Оролтын хэлбэр:

Эхний мөрөнд нийт асуулгын тоо болох t тоо өгөгдөнө. Асуулга бүрийн бүтэц дараах хэлбэртэй байна.

Хязгаарлалт:

Гаралтын хэлбэр:

t ширхэг мөрөнд тухайн асуулга бүрийн хариуг хэвлэнэ.

Жишээ оролт 0

 2 

 5 

 1 1 1 2 2 

 5 

 2 1 3 1 2

Жишээ гаралт 0

 0 

4  

Тайлбар

Эхний асуулга бол эрэмбэлэгдсэн массив учраас элементийн байр солих үйлдэл хийгдэхгүй.

Хоёр дахь асуулгын хувьд дараах байдлаар шилжилт буюу байр сэлгэх үйлдэл хийгдэх тоо нь:

Массив:        2 1 3 1 2 -> 1 2 3 1 2 -> 1 1 2 3 2 -> 1 1 2 2 3

Шилжилт:      -1                      -2                   -1            = 4

Орчуулсан : Хөвсгөл аймгийн Ирээдүй сургуулийн багш Д.Батмөнх