Bubble Sort ("pufakcha saralash") — eng sodda, eng tushunarli saralash algoritmi: siz ro'yxat bo'ylab ketma-ket yurasiz, har safar qo'shni ikkita elementni solishtirasiz, va agar ular noto'g'ri tartibda bo'lsa, joylarini almashtirasiz. Buni ko'p marta takrorlaysiz, toki hech qanday almashtirish kerak bo'lmay qolguncha.

Nomi nimadan kelib chiqqan? Har bir aylanishda eng katta (yoki eng kichik) qiymat asta-sekin ro'yxat oxiriga "suzib boradi" — xuddi suvdagi pufakcha yuzaga ko'tarilgandek.

package main

import "fmt"

func bubbleSort(nums []int) {
	n := len(nums)
	for i := 0; i < n; i++ {
		for j := 0; j < n-i-1; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}

func main() {
	nums := []int{5, 2, 8, 1, 9}
	bubbleSort(nums)
	fmt.Println(nums)
}

Ichki sikl (j) qo'shni juftlarni solishtirib, kerak bo'lsa almashtiradi — bu bitta "o'tish" (pass), va u eng katta qiymatni to'g'ri joyiga (oxiriga) "suzib olib boradi". Tashqi sikl (i) buni n marta takrorlaydi, chunki har bir o'tishda faqat bitta element o'z joyiga tushishi kafolatlanadi. n-i-1 chegarasi — allaqachon to'g'ri joyiga tushgan (oxirgi i ta) elementlarni qayta solishtirmaslik uchun kichik optimallashtirish.

Bubble Sort'ning eng katta kamchiligi — sekinligi: n ta element uchun taxminan n * n marta solishtirish kerak bo'ladi (buni "Big O Notation" darsida aniqroq ko'ramiz). Shuning uchun u haqiqiy loyihalarda deyarli hech qachon ishlatilmaydi — lekin algoritmik fikrlashni o'rganish uchun eng yaxshi boshlang'ich nuqta.