Bubble Sort

Pufaksimon saralash (Bubble Sort) — bu massivning ikkita qo'shni elementini taqqoslab, agar ular noto'g'ri tartibda turgan bo'lsa, o'rinlarini almashtirish orqali elementlarni kerakli tartibga keltiruvchi oddiy saralash algoritmidir.

Suvdagi havo pufakchalari asta-sekin yuzaga qalqib chiqqani kabi, har bir iteratsiyada massivdagi eng katta (yoki eng kichik) element massivning oxiriga "qalqib" boradi. Shu sababli bu algoritm pufaksimon saralash (bubble sort) deb ataladi.

Pufaksimon saralash qanday ishlaydi?

Faraz qilaylik, biz massiv elementlarini o'sish tartibida saralamoqchimiz.

1. Birinchi iteratsiya: Taqqoslash va almashtirish

1. Birinchi indeksdan boshlab, birinchi va ikkinchi elementlarni o'zaro taqqoslaymiz.
2. Agar birinchi element ikkinchisidan katta bo'lsa, ularning o'rni almashtiriladi (swap).
3. Endi ikkinchi va uchinchi elementlarni taqqoslaymiz. Agar ular noto'g'ri tartibda bo'lsa, almashtiramiz.
4. Bu jarayon massivning oxirgi elementiga qadar davom etadi.

Qo'shni elementlarni taqqoslash (Compare the Adjacent Elements)

2. Qolgan iteratsiyalar

Xuddi shu jarayon keyingi iteratsiyalarda ham takrorlanadi.

Har bir iteratsiya yakunida saralanmagan qismdagi eng katta element o'zining to'g'ri o'rniga — oxirgi indeksga borib joylashadi.

Har bir iteratsiyada eng katta element oxirga joylashadi

Keyingi iteratsiyada oxirgi joylashgan element hisobga olinmaydi va taqqoslash faqat qolgan saralanmagan qism ustida bajariladi.

Ikkinchi va uchinchi iteratsiyalar

Barcha elementlar o'z o'rniga joylashguncha jarayon davom ettiriladi:

Barcha elementlar to'liq saralandi

Pufaksimon saralash algoritmi

bubbleSort(array)
  for i <- 1 to indexOfLastElement - 1
    for j <- 0 to indexOfLastElement - i
      if array[j] > array[j + 1]
        swap(array[j], array[j + 1])

Pufaksimon saralash dasturiy kodi

Quyida standart pufaksimon saralash algoritmining turli dasturlash tillaridagi namunasi keltirilgan:

// Go tilida Bubble Sort algoritmi
package main

import "fmt"

func bubbleSort(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				// O'rinlarini almashtirish
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

func main() {
	data := []int{-2, 45, 0, 11, -9}
	fmt.Println("Dastlabki massiv:", data)

	bubbleSort(data)

	fmt.Println("Saralangan massiv:", data)
}

Optimallashtirilgan pufaksimon saralash

Yuqoridagi standart algoritmda, hatto massiv allaqachon to'liq saralangan bo'lsa ham, barcha taqqoslashlar oxirigacha bajarilaveradi. Bu esa ortiqcha vaqt sarflanishiga olib keladi.

Buni oldini olish uchun biz qo'shimcha swapped (almashtirildi) bayrog'ini kiritamiz. Agar biror qadamda (iteratsiyada) hech qanday almashtirish sodir bo'lmasa, demak elementlar allaqachon to'liq tartiblangan va siklni darhol to'xtatish (break) mumkin.

Optimallashtirilgan algoritm:

bubbleSort(array)
  for i <- 1 to indexOfLastElement - 1
    swapped <- false
    for j <- 0 to indexOfLastElement - i
      if array[j] > array[j + 1]
        swap(array[j], array[j + 1])
        swapped <- true
    if swapped == false
      break

Optimallashtirilgan saralash kodi

// Go tilida optimallashtirilgan Bubble Sort
package main

import "fmt"

func bubbleSortOptimized(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		swapped := false
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				swapped = true
			}
		}
		// Agar birorta ham almashtirish bo'lmasa, massiv saralangan
		if !swapped {
			break
		}
	}
}

func main() {
	data := []int{-2, 45, 0, 11, -9}
	fmt.Println("Dastlabki massiv:", data)

	bubbleSortOptimized(data)

	fmt.Println("Saralangan massiv:", data)
}

Pufaksimon saralashning murakkabligi

Murakkablikning batafsil tahlili

Bubble Sort har doim qo'shni elementlarni taqqoslaydi. Shuning uchun bajariladigan taqqoslashlar soni:

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

Bu esa taxminan n^2 ga teng. Shunday qilib, Umumiy murakkablik: O(n^2)

1. Vaqt murakkabligi

• Eng yomon holat murakkabligi (Worst Case Complexity): O(n^2) — agar biz o'sish tartibida saralamoqchi bo'lsak-u, massiv kamayish tartibida berilgan bo'lsa.
• Eng yaxshi holat murakkabligi (Best Case Complexity): O(n) — agar massiv allaqachon saralangan bo'lsa (optimallashtirilgan Bubble Sort yordamida).
• O'rtacha holat murakkabligi (Average Case Complexity): O(n^2) — elementlar massivda aralash tartibda joylashgan bo'lsa.

2. Xotira murakkabligi

• Xotira murakkabligi O(1) ga teng, chunki almashtirish uchun faqat bitta qo'shimcha temp o'zgaruvchisi ishlatiladi.
• Shuningdek, u barqaror (stable) saralash algoritmidir, ya'ni bir xil qiymatga ega elementlarning dastlabki o'zaro tartibi buzilmaydi.

Pufaksimon saralashning qo'llanilishi

Bubble sort quyidagi holatlarda ishlatiladi:

• Murakkablik katta ahamiyatga ega bo'lmaganda (kichik hajmdagi massivlar uchun).
• Qisqa va tushunishga oson kod afzal ko'rilganda.