Selection Sort

Tanlash orqali saralash (Selection Sort) — bu har bir iteratsiyada massivning saralanmagan qismidan eng kichik (yoki eng katta) elementni tanlab olib, uni saralanmagan qismning boshiga joylashtirib boruvchi saralash algoritmidir.

Tanlash orqali saralash qanday ishlaydi?

Keling, elementlarni o'sish tartibida saralash jarayonini bosqichma-bosqich ko'rib chiqamiz:

1-bosqich: Birinchi elementni minimum deb olish

1. Saralanmagan massivning birinchi elementini minimum deb belgilaymiz.

Birinchi elementni minimum deb belgilash (Select first element as minimum)

2-bosqich: Minimum elementni qolgan elementlar bilan taqqoslash

2. minimum elementni ikkinchi element bilan taqqoslaymiz. Agar ikkinchi element minimum dan kichik bo'lsa, ikkinchi elementni yangi minimum sifatida belgilaymiz.

   So'ngra yangilangan minimum ni uchinchi element bilan taqqoslaymiz. Agar uchinchi element ham kichikroq bo'lsa, uni yangi minimum qilamiz, aks holda o'zgarishsiz qoldiramiz. Bu jarayon massivning oxirigacha davom etadi.

Minimum elementni qolgan elementlar bilan taqqoslash

3-bosqich: Minimal element bilan saralanmagan qismning birinchi elementini almashtirish

3. Barcha elementlar ko'rib chiqilgach, topilgan haqiqiy minimum element saralanmagan qismning boshidagi element bilan almashtiriladi (swap).

Boshidagi elementni topilgan minimum bilan almashtirish

4-bosqich: Keyingi iteratsiyalar

4. Har bir keyingi iteratsiyada indekslash navbatdagi saralanmagan elementdan boshlanadi. 1-dan 3-gacha bo'lgan qadamlar barcha elementlar o'zlarining to'g'ri o'rniga joylashgunga qadar takrorlanadi.

Birinchi iteratsiya yakuni (1-element to'liq o'rniga tushdi)

Ikkinchi iteratsiya (saralanmagan qismdan navbatdagi kichik element tanlandi)

Uchinchi iteratsiya

To'rtinchi iteratsiya yakuni (massiv to'liq saralandi)

Tanlash orqali saralash algoritmi

selectionSort(array, size)
  repeat (size - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
end selectionSort

Dasturiy namunalar

// Go tilida Selection Sort algoritmi
package main

import "fmt"

func selectionSort(arr []int) {
	size := len(arr)
	for step := 0; step < size-1; step++ {
		minIdx := step
		for i := step + 1; i < size; i++ {
			// Kamayish tartibida saralash uchun < ni > ga o'zgartiring
			if arr[i] < arr[minIdx] {
				minIdx = i
			}
		}
		// Minimal elementni boshiga qo'yish
		arr[step], arr[minIdx] = arr[minIdx], arr[step]
	}
}

func main() {
	data := []int{20, 12, 10, 15, 2}
	fmt.Println("Dastlabki massiv:", data)

	selectionSort(data)

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

Tanlash orqali saralashning murakkabligi

Taqqoslashlar soni:

(n - 1) + (n - 2) + (n - 3) + ... + 1 = n * (n - 1) / 2

Bu esa taxminan n^2 ga teng. Shuningdek, kodda ikkita ichma-ich sikl (nested loop) mavjud bo'lgani sababli, murakkablik har qanday holatda ham n^2 bo'ladi.

Vaqt murakkabligi

• Eng yomon holat (Worst Case Complexity): O(n^2) — agar massiv teskari tartibda berilgan bo'lsa.
• Eng yaxshi holat (Best Case Complexity): O(n^2) — hatto massiv allaqachon to'liq saralangan bo'lsa ham, minimum elementni qidirish uchun barcha elementlar taqqoslab chiqiladi.
• O'rtacha holat (Average Case Complexity): O(n^2) — elementlar massivda aralash tartibda bo'lganda.

Xotira murakkabligi

• Xotira murakkabligi O(1) ga teng, chunki minimal element indeksini saqlash uchun faqat bitta qo'shimcha min_idx o'zgaruvchisi ishlatiladi.

Tanlash orqali saralashning qo'llanilishi

Selection sort quyidagi holatlarda ishlatiladi:

• Kichik hajmdagi massivlarni saralash kerak bo'lganda.
• Xotiraga qayta yozish (swap) operatsiyalarining narxi juda yuqori bo'lganda (chunki Selection sort har bir qadamda faqat bir martagina almashtirish — jami ko'pi bilan O(n) marta swap amalini bajaradi).