Insertion sort. Insertion sort — (Joylab saralash) ham tartibsiz massiv elementlarini saralash uchun moʻljallangan. Uning ishlash algoritmi xuddi qoʻldagi kartani saralashga oʻxshab ketadi. Tartibsiz turgan kartalar ichidan birini olasiz va uni oʻzi turishi kerak boʻlgan joyga joylashtirib qoʻyasiz. Insertion sort ham shu koʻrinishda ishlaydi. Algoritm oldin massiv boshidagi ikkita elementni saralab olib, massivning qolgan elementlarini shunga qarab oʻz oʻrniga joylashtirib chiqadi. Joylab saralashning xususiyatlari. Bu algoritm oddiy amalga oshirilgani uchun eng oddiy algoritmlardan biridir. Insertion sort kichik maʼlumotlarni saralash uchun samarali. Joylab saralash tabiatan moslashuvchan, yaʼni qisman saralangan maʼlumotlar toʻplamlari uchun mos keladi. Insertion sort ham Selection sort va Bubble sort kabi O(n2) vaqt murakkabligi bilan ishlasa ham, lekin ulardan koʻra samaraliroq algoritm hisoblanadi. Aynan, massiv elementlari deyarli saralangan holatda Insertion sort algoritmi Merge sort yoki Quick sort algoritmidan ham koʻra tezroq ishlaydi. Joylab saralash algoritmining ishlashi. 12 11 13 5 6 Dastlab, massivning dastlabki ikkita elementi joylash tartibida taqqoslanadi. 12 11 13 5 6 Bu yerda 12 11 dan katta, ular oʻsish tartibida emas va 12 oʻzining toʻgʻri joyida emas. Shunday qilib, 11 va 12 ning oʻrnini almashtiring. Shunday qilib, hozircha 11 tartiblangan pastki qatorda saqlanadi. 11 12 13 5 6 Endi keyingi ikkita elementga oʻting va ularni solishtiring 11 12 13 5 6 Bu yerda 13 12 dan katta, shuning uchun ikkala element ham oʻsish tartibida turibdi, almashtirish sodir boʻlmaydi. 12, shuningdek, 11 bilan birga tartiblangan pastki qatorda saqlanadi Endi tartiblangan kichik massivda ikkita element mavjud, ular 11 va 12 Keyingi ikkita elementga oʻtish: 13 va 5 11 12 13 5 6 5 va 13 ikkalasi ham oʻz joyida emas, shuning uchun ularni almashtiring 11 12 5 13 6 Almashtirilgandan soʻng, 12 va 5 elementlar tartiblanmadi, shuning uchun yana almashtiriladi 11 5 12 13 6 Bu yerda yana 11 va 5 tartiblanmadi, shuning uchun yana almashtiring 5 11 12 13 6 bu yerda u oʻzining toʻgʻri holatida Endi tartiblangan kichik massivda mavjud boʻlgan elementlar 5, 11 va 12 Keyingi ikkita elementga oʻtish: 13 va 6 5 11 12 13 6 Shubhasiz, ular tartiblanmagan, shuning uchun ikkalasini almashtirishni amalga oshiring 5 11 12 6 13 Endi 6 12 dan kichik, shuning uchun yana almashtiring 5 11 6 12 13 Almashtirish 11 va 6 ni tartiblamaydi, shuning uchun yana almashtiring 5 6 11 12 13 Nihoyat, massiv toʻliq tartiblangan.