Масивыг эрэмбэлэх асуудлыг шийдэх хэд хэдэн үндсэн алгоритмууд байдаг. Тэдгээрийн дотроос хамгийн алдартай нь оруулах сорт юм. Энэ аргыг ойлгомжтой, энгийн боловч үр ашиг багатай тул програмчлалын сургалтанд голчлон ашигладаг. Энэ нь танд ангилах үндсэн механизмуудыг ойлгох боломжийг олгоно.
Алгоритмын тайлбар
Оруулах эрэмбэлэх алгоритмын мөн чанар нь эхний массив дотор зөв эрэмбэлэгдсэн сегмент үүсэх явдал юм. Элемент бүрийг шалгасан хэсэгтэй нэг нэгээр нь харьцуулж, зөв газарт оруулна. Тиймээс бүх элементүүдийг давтсаны дараа тэдгээр нь зөв дарааллаар жагсана.
Элементүүдийг сонгох дараалал нь дурын байж болно, тэдгээрийг дур мэдэн эсвэл ямар нэг алгоритмын дагуу сонгож болно. Ихэнхдээ дараалсан тооллогыг массивын эхнээс эхлэн дараалсан сегмент үүсгэдэг.
Ангилах эхлэл нь иймэрхүү харагдаж магадгүй:
- Масивины эхний элементийг авна.
- Харьцуулах зүйл байхгүй тул элементийг өөрөө захиалгаар нь аваарайдараалал.
- Хоёр дахь зүйл рүү очно уу.
- Ангилах дүрэмд үндэслэн үүнийг эхнийхтэй харьцуулна уу.
- Хэрэв шаардлагатай бол элементүүдийг өөр газар сольж болно.
- Эхний хоёр элементийг эрэмбэлсэн дараалал болгон авна.
- Гурав дахь зүйл рүү очно уу.
- Хоёрдахьтай нь харьцуулж, шаардлагатай бол солино уу.
- Хэрэв сольсон бол эхнийхтэй нь харьцуулна уу.
- Гурван элементийг эрэмбэлсэн дараалал болгон авна.
Гэхдээ эх массивын төгсгөл хүртэл үргэлжилнэ.
Бодит амьдралаар оруулах эрэмбэ
Тодорхой болгохын тулд энэ ангилах механизмыг өдөр тутмын амьдралд хэрхэн ашигладаг талаар жишээ өгөх нь зүйтэй.
Жишээ нь хэтэвч ав. Мөнгөн тэмдэгтийн тасалгаанд зуу, таван зуу, мянган долларын дэвсгэрт эмх замбараагүй хэвтэж байна. Энэ бол эмх замбараагүй байдал, ийм хонгилд тэр даруй зөв цаас олоход хэцүү байдаг. Мөнгөн тэмдэгтийн массивыг эрэмбэлсэн байх ёстой.
Хамгийн эхнийх нь 1000 рублийн мөнгөн дэвсгэрт бөгөөд түүний дараа шууд 100. Бид зуугаа аваад урд нь тавьдаг. Гурав дахь дараалсан 500 рубль, түүний зохистой газар нь зуугаас мянга хүртэл байна.
Бид хүлээн авсан картуудыг удирдахад хялбар болгох үүднээс "Тэнэг" тоглох үед ижил аргаар ангилдаг.
Операторууд болон туслах функцууд
Оруулах эрэмбэлэх арга нь эрэмбэлэх анхны массив, харьцуулах функц, шаардлагатай бол элементүүдийг тоолох дүрмийг тодорхойлох функцийг оролт болгон авдаг. Оронд нь ихэвчлэн ашигладагердийн давталтын мэдэгдэл.
Эхний элемент нь өөрөө эрэмбэлэгдсэн олонлог тул харьцуулалт хоёр дахь хэсгээс эхэлнэ.
Алгоритм нь ихэвчлэн хоёр утгыг солилцоход туслах функцийг ашигладаг (солих). Энэ нь нэмэлт түр зуурын хувьсагч ашигладаг бөгөөд энэ нь санах ой зарцуулж, кодыг бага зэрэг удаашруулдаг.
Бас нэг хувилбар бол бүлэг элементүүдийг бөөнөөр нь шилжүүлж, дараа нь одоогийн элементийг сул зайд оруулах явдал юм. Энэ тохиолдолд харьцуулалт эерэг үр дүн өгөх үед дараагийн элемент рүү шилжих нь зөв дарааллыг харуулж байна.
Хэрэгжүүлэх жишээ
Тодорхой хэрэгжилт нь ашигласан програмчлалын хэл, түүний синтакс болон бүтцээс ихээхэн шалтгаална.
Утга солилцохын тулд түр зуурын хувьсагчийг ашиглан Сонгодог С хэрэгжүүлэлт:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) завсарлага; массив[j + 1]=массив[j]; массив[j]=температур; } }
PHP-ийн хэрэгжилт:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Энд эхлээд эрэмбэлэх нөхцөлтэй таарахгүй байгаа бүх элементүүдийг баруун тийш шилжүүлж, дараа нь одоогийн элементийг чөлөөт зайд оруулна.
while давталт ашигладаг Java код:
нийтийн статик хүчингүй оруулахSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Кодны ерөнхий утга өөрчлөгдөөгүй: массивын элемент бүрийг өмнөхтэй нь дараалан харьцуулж, шаардлагатай бол тэдгээртэй сольдог.
Тооцоолсон ажиллах хугацаа
Мэдээжийн хэрэг, хамгийн сайн тохиолдолд алгоритмын оролт нь аль хэдийн зөв байдлаар эрэмблэгдсэн массив байх болно. Энэ тохиолдолд алгоритм нь солилцоо хийхгүйгээр элемент бүрийг зөв газарт нь байгаа эсэхийг шалгахад л хангалттай. Тиймээс ажиллах хугацаа нь O(n) массивын уртаас шууд хамаарна.
Хамгийн муу оролт нь урвуу дарааллаар эрэмблэгдсэн массив юм. Үүнд олон тооны сэлгэлт шаардлагатай бөгөөд ажиллах үеийн функц нь элементийн квадратын тооноос хамаарна.
Бүрэн эмх цэгцгүй массивын яг солих тоог дараах томъёогоор тооцоолж болно:
n(n-1)/2
энд n нь эх массивын урт юм. Тиймээс 100 элементийг зөв дарааллаар нь байрлуулахын тулд 4950 солих шаардлагатай болно.
Оруулах арга нь жижиг эсвэл хэсэгчлэн эрэмбэлсэн массивуудыг эрэмбэлэхэд маш үр дүнтэй байдаг. Гэсэн хэдий ч тооцоолол маш нарийн тул үүнийг хаа сайгүй хэрэглэхийг зөвлөдөггүй.
Алгоритмыг бусад олон нарийн төвөгтэй ангилах аргуудад туслах болгон ашигладаг.
Тэнцүү утгыг эрэмбэлэх
Оруулах алгоритм нь тогтвортой гэж нэрлэгддэг төрөлд хамаарна. Энэ нь,Энэ нь ижил элементүүдийг солихгүй, харин анхны дарааллыг нь хадгалдаг. Тогтвортой байдлын индекс нь олон тохиолдолд зөв захиалга хийхэд чухал байдаг.
Дээрх нь бүжгийн төрөлд оруулах гайхалтай жишээ юм.
