Qidiruv va Saralash
Qidiruv — ma’lumot ichidan element topish, saralash — tartibga keltirish. Har bir algoritmning vaqt murakkabligi va qachon ishlatilishi muhim.
Linear search O(n) va Binary search O(log n)
Nima bu?
Linear search — massivni boshidan oxirigacha tekshirish, tartib talab qilmaydi, O(n). Binary search — faqat tartiblangan massivda ishlaydi, har qadamda qidiruv maydonini yarmiga qisqartiradi, O(log n).
Kod misoli
// Linear search — tartib muhim emas
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i
}
return -1
}
// Binary search — iterativ
function binarySearch(arr, target) {
let left = 0
let right = arr.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (arr[mid] === target) return mid
if (arr[mid] < target) left = mid + 1
else right = mid - 1
}
return -1
}
// Binary search — rekursiv
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
if (left > right) return -1
const mid = Math.floor((left + right) / 2)
if (arr[mid] === target) return mid
if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right)
return binarySearchRecursive(arr, target, left, mid - 1)
}
// Birinchi va oxirgi paydo bo'lish indexi (duplicate massiv)
function searchRange(nums, target) {
function findBound(isFirst) {
let left = 0
let right = nums.length - 1
let bound = -1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (nums[mid] === target) {
bound = mid
if (isFirst) right = mid - 1
else left = mid + 1
} else if (nums[mid] < target) left = mid + 1
else right = mid - 1
}
return bound
}
return [findBound(true), findBound(false)]
}
const sorted = [1, 3, 5, 7, 9, 11]
console.log(linearSearch([5, 2, 8, 1], 8)) // 2
console.log(binarySearch(sorted, 7)) // 3
console.log(searchRange([1, 2, 2, 2, 3], 2)) // [1, 3]
Imtihonda
- «Binary search qachon ishlatiladi? Shartlari nima?»
- «
n = 1 000 000da linear va binary qancha qadam?» → ~1M vs ~20 - «Rotated sorted array da target qidirish»
Yodlash uchun
Tartiblangan + tez qidiruv → binary search; tartibsiz → linear yoki avval sort.
Bubble Sort, Selection Sort, Insertion Sort — O(n²)
Nima bu?
Uchta oddiy saralash algoritmi, barchasi O(n²) vaqt. Bubble Sort — qo‘shni elementlarni solishtiradi, katta elementlar "suzib" ketadi. Selection Sort — har qadamda eng kichikni tanlaydi. Insertion Sort — kartalar tartiblash kabi, har elementni to‘g‘ri joyga qo‘yadi. Kichik yoki deyarli tartiblangan massivlar uchun insertion sort foydali.
Kod misoli
// Bubble Sort
function bubbleSort(arr) {
const a = [...arr]
for (let i = 0; i < a.length - 1; i++) {
let swapped = false
for (let j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
;[a[j], a[j + 1]] = [a[j + 1], a[j]]
swapped = true
}
}
if (!swapped) break // optimizatsiya: allaqachon tartiblangan
}
return a
}
// Selection Sort
function selectionSort(arr) {
const a = [...arr]
for (let i = 0; i < a.length - 1; i++) {
let minIdx = i
for (let j = i + 1; j < a.length; j++) {
if (a[j] < a[minIdx]) minIdx = j
}
;[a[i], a[minIdx]] = [a[minIdx], a[i]]
}
return a
}
// Insertion Sort
function insertionSort(arr) {
const a = [...arr]
for (let i = 1; i < a.length; i++) {
const key = a[i]
let j = i - 1
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]
j--
}
a[j + 1] = key
}
return a
}
console.log(bubbleSort([64, 34, 25, 12, 22])) // [12, 22, 25, 34, 64]
console.log(selectionSort([64, 34, 25, 12, 22]))
console.log(insertionSort([64, 34, 25, 12, 22]))
Imtihonda
- «Uchta oddiy sort farqi va murakkabligi?»
- «Qaysi biri deyarli tartiblangan massivda tezroq?» → Insertion Sort
- «Production’da nima uchun ishlatilmaydi?» → O(n²) sekin
Yodlash uchun
Intervyuda tushuntirish uchun bilish kerak; amalda Array.sort() yoki merge/quick sort ishlatiladi.
Merge Sort, Quick Sort — O(n log n)
Nima bu?
Samarali saralash algoritmlari — O(n log n) vaqt. Merge Sort — divide & conquer: bo‘lib, saralab, birlashtirish; barqaror, doim O(n log n), lekin O(n) qo‘shimcha xotira. Quick Sort — pivot tanlab, kichik/chap va katta/o‘ng qismlarga ajratish; o‘rtacha O(n log n), eng yomon O(n²).
Gotcha: yuqoridagi kod har doim oxirgi elementni pivot qilib olgani uchun allaqachon tartiblangan yoki teskari tartiblangan massivda eng yomon holat O(n²)ga tushib qoladi (har bo‘linish faqat 1 elementni ajratadi). Buni oldini olish uchun tasodifiy pivot tanlash yoki "median-of-three" (birinchi/o‘rta/oxirgi elementning medianasi) strategiyasi ishlatiladi — bu Senior darajadagi intervyularda tez-tez so‘raladigan optimizatsiya.
Kod misoli
// Merge Sort
function mergeSort(arr) {
if (arr.length <= 1) return arr
const mid = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, mid))
const right = mergeSort(arr.slice(mid))
return merge(left, right)
}
function merge(left, right) {
const result = []
let i = 0
let j = 0
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++])
else result.push(right[j++])
}
return result.concat(left.slice(i)).concat(right.slice(j))
}
// Quick Sort
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pivotIdx = partition(arr, low, high)
quickSort(arr, low, pivotIdx - 1)
quickSort(arr, pivotIdx + 1, high)
}
return arr
}
function partition(arr, low, high) {
const pivot = arr[high]
let i = low - 1
for (let 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
}
const nums = [38, 27, 43, 3, 9, 82, 10]
console.log(mergeSort([...nums])) // [3, 9, 10, 27, 38, 43, 82]
console.log(quickSort([...nums])) // [3, 9, 10, 27, 38, 43, 82]
Imtihonda
- «Merge va Quick sort farqi — vaqt, xotira, barqarorlik?»
- «Quick sort eng yomon holati qachon?» → allaqachon tartiblangan + yomon pivot
- «Merge sort qanday ishlaydi — qadam-baqadam tushuntiring»
Yodlash uchun
Merge = barqaror + O(n) xotira; Quick = in-place + o‘rtacha tez, lekin eng yomon O(n²).
JavaScript Array.sort() — timsort
Nima bu?
JavaScript Array.sort() V8 engine’da Timsort algoritmini ishlatadi — merge sort va insertion sort aralashmasi. O‘rtacha va eng yomon holat O(n log n). Default sort string sifatida solishtiradi — raqamlar noto‘g‘ri tartiblanishi mumkin. Compare function berish shart.
Kod misoli
// XATO — default string sort
console.log([10, 2, 1].sort()) // [1, 10, 2] — "1" < "10" < "2"
// TO'G'RI — raqamli sort
console.log([10, 2, 1].sort((a, b) => a - b)) // [1, 2, 10]
// Kamayish tartibi
console.log([10, 2, 1].sort((a, b) => b - a)) // [10, 2, 1]
// Ob'ekt bo'yicha sort
const users = [
{ name: 'Ali', age: 30 },
{ name: 'Vali', age: 25 },
{ name: 'Hasan', age: 35 },
]
users.sort((a, b) => a.age - b.age)
console.log(users.map((u) => u.name)) // ['Vali', 'Ali', 'Hasan']
// String sort — localeCompare
const words = ['banana', 'apple', 'cherry']
words.sort((a, b) => a.localeCompare(b))
console.log(words) // ['apple', 'banana', 'cherry']
// O'zgartirishlar soni (inversion count) — sort dan foydalanish
function countInversions(arr) {
let count = 0
const sorted = [...arr].sort((a, b) => a - b)
const indexMap = new Map(sorted.map((v, i) => [v, i]))
for (let i = 0; i < arr.length; i++) {
if (indexMap.get(arr[i]) < i) count++
}
return count
}
Imtihonda
- «
[3, 1, 10, 2].sort()natijasi nima? Nega?» - «Ob'ektlarni age bo‘yicha qanday sort qilasiz?»
- «Sort barqarormi (stable)?» → JS sort stable (ES2019+)
Yodlash uchun
Har doim compare function ber: (a, b) => a - b raqamlar uchun, localeCompare stringlar uchun.