Bubble Sort
Bubble sort bu bir elementni o'zidan keyingi element bilan taqqoslab element joyini o'zgartirib amalga oshiriladigan algoritm hisoblanadi.Uning ishlash tezligi BO(n2) n kvadrat ga teng hisoblanadi.Yani bir element almashi uchun o'zidan keyingi barcha element bilan tekshirib alamashtirib chiqish kerak albatta bu eng yomon holatda ishlashi.Masalan 1 dan 10 gacha teskari tartiblangan sonlar arrayi bo'lsa [10,9,8,7,6,5,4,3,2,1] bundagi sonlarni [1,2,3,4,5,6,7,8,9,10] holatiga keltirish uchun 10*10=100 yani n * n = n2 ish bajaramiz.Bunda ish qanday ketadi=> 10 > 9 tenglanadi birinchi shartda 10 katta shuning uchun [9,10,8,7....] holatga keladi va keyingi shart 10>8 ko'rinishida bo'ladi va [9,8,10,7,6....] holatiga keladi.Shu usulda 10 soni 9 indexgacha suriladi keyin 9 elementi tekshirilish boshlanadi va bu ish 1 elementi 0 indexga kelguncha davom etadi bu esa 10 ta operatsiya degani.
Huddi shu misolni endi kodda ko'ramiz.
function bubbleSort(nums) {
let counter = 0
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - i - 1; j++) {
counter+=1 // har safargi ishni sanab turadi
if (nums[j] > nums[j + 1])
let t = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = t;
}
}
}
console.log(counter) // 45 marta ishladi
return nums;
}
console.log(bubbleSort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]));
// Tushuntirish: birinchi loop oxirgi elementga borishi kerakmas shuning
// uchun nums.length -1 qilingan buning sababi inner loop bitta oldinda
// yuradi va n-1(outer loop) > n-2(inner loop) shartni bajarganda
// allaqachon oxirgi element tartiblanadi.Inner loop nums.length - i - 1
// qilinishiga sabab tartiblangan elementlarni yana qayta yurib chiqmaslik
// uchun.Masalan 3ta element tartiblangan va yana 7 ta element qolgan bolsa
// nums.length -3- 1 bo'lyapti va 7 marta ishlaydi.Bu sorting usulida asosi
// inner loop da bajariladi.
// inner loopni ham nums.length -1 holatida ishlashiga misol
function bubbleSort(nums) {
let counter = 0
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - 1; j++) {
counter+=1 // har safargi ishni sanab turadi
if (nums[j] > nums[j + 1])
let t = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = t;
}
}
}
console.log(counter) // 81 marta ishladi
return nums;
}
console.log(bubbleSort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]));
