Quicksort Algorithm

Tezkor saralash (Quicksort) — bu "Bo'lib ol va hukmronlik qil" (Divide and Conquer) yondashuviga asoslangan eng samarali va keng qo'llaniladigan saralash algoritmlaridan biridir:

1. Massivdan bitta tayanch element (pivot element) tanlanadi va massiv tayanch element atrofida ikkita qism-massivga ajratiladi (partition).

   Bunda tayanch element shunday joylashtiriladiki, undan kichik barcha elementlar chap tomonda, undan katta barcha elementlar esa o'ng tomonda joylashadi.

2. Chap va o'ng qism-massivlar ham xuddi shu usul yordamida rekursiv ravishda ikkiga bo'linadi. Bu jarayon har bir qism-massiv bitta elementdan iborat bo'lib qolguniga qadar davom etadi.

3. Barcha qism-massivlar o'z o'rniga tushgach, natijada to'liq saralangan massiv hosil bo'ladi.

Tezkor saralash algoritmi qanday ishlaydi?

1. Select the Pivot

Tayanch elementni tanlash:

Tezkor saralashning turli xil modifikatsiyalari mavjud bo'lib, ularda tayanch element turli pozitsiyalardan (birinchi, oxirgi, o'rtadagi yoki tasodifiy) tanlanishi mumkin. Bu yerda biz massivning eng o'ngdagi (oxirgi) elementini tayanch element sifatida tanlaymiz.

Tayanch elementni (pivot) tanlash

2. Partition the Array

Massivni qayta tartiblash (Partition):

Endi massiv elementlari qayta guruhlanadi: tayanch elementdan kichik barcha elementlar chapga, kattalari esa o'ngga suriladi.

Kichik elementlarni chapga, kattalarini esa o'ngga joylashtirish

Buning bosqichma-bosqich ishlashi:

a) Ko'rsatkich tayanch elementga o'rnatiladi. Tayanch element birinchi elementdan boshlab qolgan barcha elementlar bilan taqqoslanadi.

Tayanch elementni 1-indeksdagi element bilan taqqoslash

b) Elementdan kattaroq qiymatni kuzatib borish uchun i ko'rsatkichi ishlatiladi. Agar ko'rilayotgan element tayanchdan katta bo'lsa, hech narsa almashtirilmaydi.

Agar element tayanchdan katta bo'lsa, keyingisiga o'tiladi

c) Agar tayanchdan kichikroq element uchrasa, i ko'rsatkichi bir qadam oldinga suriladi va i-element bilan ushbu kichik element o'zaro almashtiriladi (swap).

Tayanchdan kichik element topilganda almashtirish bajariladi

d) Jarayon tayanchdan oldingi oxirgi elementgacha davom ettiriladi:

Navbatdagi elementlarni taqqoslash

Yana bir kichik element almashtirildi

e) Nihoyat, tayanch element i + 1 pozitsiyasidagi element bilan almashtiriladi, natijada tayanch element o'zining mutlaq to'g'ri joyiga tushadi:

Tayanch element yakuniy to'g'ri o'rniga joylashtirildi

3. Qism-massivlarni rekursiv saralash

Tayanch element o'z o'rnini egallagach, uning chap va o'ng tomonidagi qism-massivlar uchun xuddi shu ajratish jarayoni alohida-alohida chaqiriladi:

Chap va o'ng qism-massivlarni ajratish

Tezkor saralashning umumiy bajarilish sxemasi

Yakuniy saralangan massiv

Tezkor saralash algoritmining soxta kodi

quickSort(array, low, high)
  if low < high
    // pivot o'rnini topish
    pivotIndex <- partition(array, low, high)

    // Chap qismni saralash
    quickSort(array, low, pivotIndex - 1)

    // O'ng qismni saralash
    quickSort(array, pivotIndex + 1, high)

partition(array, low, high)
  pivot <- array[high]
  i <- low - 1
  for j <- low to high - 1
    if array[j] <= pivot
      i <- i + 1
      swap array[i] with array[j]
  swap array[i + 1] with array[high]
  return i + 1

Dasturiy namunalar

// Go tilida Quicksort algoritmi
package main

import "fmt"

// Partition funksiyasi: tayanch elementni o'z o'rniga qo'yadi
func partition(arr []int, low, high int) int {
	pivot := arr[high]
	i := low - 1

	for j := low; j < high; j++ {
		if arr[j] <= pivot {
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	arr[i+1], arr[high] = arr[high], arr[i+1]
	return i + 1
}

// Rekursiv Quicksort
func quickSort(arr []int, low, high int) {
	if low < high {
		pi := partition(arr, low, high)

		// Tayanchdan chapdagi qismni saralash
		quickSort(arr, low, pi-1)

		// Tayanchdan o'ngdagi qismni saralash
		quickSort(arr, pi+1, high)
	}
}

func main() {
	data := []int{8, 7, 2, 1, 0, 9, 6}
	fmt.Println("Dastlabki massiv:", data)

	quickSort(data, 0, len(data)-1)

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

Tezkor saralashning murakkabligi

Vaqt murakkabligi

• Eng yomon holat (Worst Case Complexity): O(n^2) — agar tanlangan tayanch element har doim massivdagi eng kichik yoki eng katta element bo'lsa (masalan, allaqachon saralangan massivda oxirgi element pivot qilib tanlansa).
• Eng yaxshi holat (Best Case Complexity): O(n log n) — agar tanlangan tayanch element massivni har doim teng ikkita qismga bo'lsa.
• O'rtacha holat (Average Case Complexity): O(n log n) — amaliyotda ko'p uchraydigan holatlarda.

Xotira murakkabligi

• Xotira murakkabligi O(log n) ga teng (rekursiv chaqiruvlar steki uchun).
• Quicksort beqaror (unstable) saralash algoritmidir, ya'ni teng qiymatli elementlarning dastlabki o'zaro nisbiy tartibi o'zgarishi mumkin.

Tezkor saralashning qo'llanilishi

• Dasturlash tillarining standart kutubxonalarida (masalan, C tilidagi qsort, C++ STL dagi std::sort introsort asosida) asosiy saralash algoritmi sifatida qo'llaniladi.
• Qo'shimcha xotira cheklangan va eng yuqori amaliy tezlik talab qilingan tizimlarda.