Insertion Sort

Qo'shish orqali saralash (Insertion Sort) — bu har bir iteratsiyada saralanmagan bitta elementni olib, uni massivning allaqachon saralangan qismidagi o'ziga mos to'g'ri o'rniga joylashtirib boruvchi saralash algoritmidir.

Qo'shish orqali saralash qo'lda karta (karta o'yini) o'ynayotganda kartalarni tartiblash bilan bir xil ishlaydi: Biz birinchi kartani allaqachon saralangan deb hisoblaymiz, so'ngra navbatdagi saralanmagan kartani olamiz. Agar yangi olingan karta qo'limizdagi kartadan katta bo'lsa, uni o'ng tomonga, kichik bo'lsa chap tomonga joylashtiramiz. Shu tariqa, barcha kartalar ketma-ket olinib, o'z joyiga kiritiladi.

Xuddi shu yondashuv Insertion Sort algoritmi tomonidan qo'llaniladi.

Qo'shish orqali saralash qanday ishlaydi?

Faraz qilaylik, bizga quyidagi massiv berilgan:

Dastlabki massiv (Initial array)

1. Massivdagi birinchi element allaqachon saralangan deb hisoblanadi. Ikkinchi elementni olamiz va uni alohida key o'zgaruvchisida saqlaymiz.

   key elementni birinchi element bilan taqqoslaymiz. Agar birinchi element key dan katta bo'lsa, key birinchi elementning oldiga joylashtiriladi.

Agar birinchi element key dan katta bo'lsa, key birinchi elementning oldiga kiritiladi

2. Endi dastlabki ikkita element saralandi. Uchinchi elementni olamiz va uni chap tomondagi barcha elementlar bilan taqqoslaymiz. Uni o'zidan kichik bo'lgan elementning orqasiga qo'yamiz. Agar o'zidan kichik element bo'lmasa, massivning eng boshiga joylashtiramiz.

1-elementni massivning boshiga kiritish

3. Xuddi shu tarzda, har bir saralanmagan element o'zining to'g'ri joyiga siljitiladi:

4 ni 1 ning orqasiga joylashtirish

3 ni 1 ning orqasiga joylashtirish va massiv to'liq saralandi

Qo'shish orqali saralash algoritmi

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

Dasturiy namunalar

// Go tilida Insertion Sort algoritmi
package main

import "fmt"

func insertionSort(arr []int) {
	for step := 1; step < len(arr); step++ {
		key := arr[step]
		j := step - 1

		// key dan katta bo'lgan barcha elementlarni bir pozitsiya o'ngga suramiz
		for j >= 0 && key < arr[j] {
			arr[j+1] = arr[j]
			j--
		}
		// key ni topilgan joyga joylashtiramiz
		arr[j+1] = key
	}
}

func main() {
	data := []int{9, 5, 1, 4, 3}
	fmt.Println("Dastlabki massiv:", data)

	insertionSort(data)

	fmt.Println("O'sish tartibida saralangan massiv:")
	fmt.Println(data)
}

Qo'shish orqali saralashning murakkabligi

Vaqt murakkabligi

• Eng yomon holat (Worst Case Complexity): O(n^2) — agar massiv teskari (kamayish) tartibida berilgan bo'lsa, har bir element barcha chapdagi elementlar bilan taqqoslanadi.
• Eng yaxshi holat (Best Case Complexity): O(n) — agar massiv allaqachon saralangan bo'lsa, ichki while sikli har bir qadamda atigi 1 marta taqqoslash bilan darhol to'xtaydi.
• O'rtacha holat (Average Case Complexity): O(n^2) — massiv elementlari tasodifiy aralash tartibda bo'lganda.

Xotira murakkabligi

• Xotira murakkabligi O(1) ga teng, chunki faqat key va j kabi bir nechta qo'shimcha o'zgaruvchilar talab qilinadi.
• Insertion Sort barqaror (stable) algoritm hisoblanadi.

Qo'shish orqali saralashning qo'llanilishi

Insertion sort quyidagi vaziyatlarda keng qo'llaniladi:

• Massivda elementlar soni oz bo'lganda.
• Massivning aksariyat qismi allaqachon saralangan bo'lib, faqat bir nechta elementlar o'z o'rnida bo'lmaganda (deyarli saralangan ma'lumotlar uchun eng tezkor algoritmlardan biri).