Katta imtihon daftarlarini ballga qarab tartiblashingiz kerak deylik. Bitta yo'l — barchasini bitta "o'rtacha" ball bilan solishtirib, ikkita uyumga bo'lish: "bundan kam" va "bundan ko'p". Keyin har bir kichik uyumni yana xuddi shu tarzda ikkiga bo'lasiz — toki har bir uyumda bitta qog'oz qolguncha. Quick Sort aynan shu g'oyaga asoslangan.

Bu — "bo'l va hukmronlik qil" (divide and conquer) strategiyasining klassik namunasi: katta muammoni kichik, o'xshash muammolarga bo'lasiz, ularni (odatda rekursiya orqali) alohida hal qilasiz, so'ng natijalarni birlashtirasiz.

package main

import "fmt"

func quickSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums // 0 yoki 1 elementli ro'yxat allaqachon "saralangan"
	}

	pivot := nums[len(nums)/2] // "o'rtacha" sifatida tanlangan qiymat
	var less, equal, greater []int

	for _, n := range nums {
		switch {
		case n < pivot:
			less = append(less, n)
		case n == pivot:
			equal = append(equal, n)
		default:
			greater = append(greater, n)
		}
	}

	result := append(quickSort(less), equal...)
	result = append(result, quickSort(greater)...)
	return result
}

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

pivot — "nazorat nuqtasi" sifatida tanlangan bitta qiymat. Ro'yxat uchta guruhga bo'linadi: pivotdan kichiklar, unga teng bo'lganlar, va undan kattalar. Eng qiziq qismi — less va greater guruhlari xuddi shu `quickSort` funksiyasining o'ziga qayta beriladi (rekursiya, "Loop Variations" va rekursiv daraxt darslarida ko'rgan g'oya) — ular yana kichikroq guruhlarga bo'linadi, toki har bir guruh 0 yoki 1 elementga (allaqachon saralangan holatga) yetguncha.

Bubble Sort bilan solishtirganda, Quick Sort odatda ancha tezroq ishlaydi (o'rtacha holatda), chunki har bir qadamda muammoni taxminan yarmiga kamaytiradi, birma-bir emas. Lekin agar pivot doim eng yomon tanlansa (masalan har doim eng kichik qiymat), Quick Sort ham Bubble Sort kabi sekinlashishi mumkin — bu "Why Balanced Trees?" darsida ko'rgan "noto'g'ri tartib muammoni yomonlashtiradi" g'oyasining yana bir ko'rinishi.