Shell saralash algoritmi.
Salom! Bugun yangi Shell saralash algoritmini ko'rib chiqaman.
π Github: ShellSort
β° Time complexity:
O'rtacha - O(N ^ (3/2)),
Eng yomon holatda - O(N ^ 2)
π Space complexity: O(1)
π§βπ» G'oya π§βπ»
Shell sort, uni 1959-yilda kashf etgan, Donald L. Shell-dan nomini olgan. Shell sort Kiritish orqali saralash usulining asosida ishlaydi. Kiritish orqali saralash algoritmida siz elementlarni faqat bir pozitsiyaga sura olasiz. Agar element massivning oxiridan boshiga joylashtirilishi kerak bo'lsa, siz ko'p swap operatsiyasini bajarasiz.
Shell sort algoritmining g'oyasi - bu uzoq masofada joylashgan elementlarni saralash. Bu algoritm orqali siz elementlarni h uzoqlikda saralangan qilasiz. Shu h-ning qiymati 1ga teng bo'lmagunicha uni kamaytiraverasiz. h uzoqlikda saralangan degani bir biridan h uzoqlikda joylashgan elementlarning har bir ro'yxatda saralangan holatda bo'lishi.
π§βπ» Algoritm π§βπ»
h = h * 3 + 1 -> bu Knuth-ning Interval ketma-ketliklar uchun formulasi.
1. Birinchi while loop berilgan massiv hajmi uchun to'g'ri h-ni topish uchun ishlatasiz.
2. Keyin esa nested loop ishlatasiz.
- Birinchi tashqi while loop-ni h-ning qiymatini formula bo'yicha kamaytirish uchun ishlatasiz.
- Ichki for loop-da esa Kiritish orqali saralash [Insertion sort] algoritmini h uzoqlikda joylashgan elementlar uchun ishlatasiz.
- Ichki while loop Kiritish orqali saralashga o'xshab, h uzoqlikda joylashgan elementlar uchun katta elementlarni o'nga suradi va tanlangan elementni o'z joyiga qo'yadi.
Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Geeksforgeeks
3. GIF
Rahmat!
Omad! βοΈπ
@LeetCodin
Salom! Bugun yangi Shell saralash algoritmini ko'rib chiqaman.
π Github: ShellSort
β° Time complexity:
O'rtacha - O(N ^ (3/2)),
Eng yomon holatda - O(N ^ 2)
π Space complexity: O(1)
π§βπ» G'oya π§βπ»
Shell sort, uni 1959-yilda kashf etgan, Donald L. Shell-dan nomini olgan. Shell sort Kiritish orqali saralash usulining asosida ishlaydi. Kiritish orqali saralash algoritmida siz elementlarni faqat bir pozitsiyaga sura olasiz. Agar element massivning oxiridan boshiga joylashtirilishi kerak bo'lsa, siz ko'p swap operatsiyasini bajarasiz.
Shell sort algoritmining g'oyasi - bu uzoq masofada joylashgan elementlarni saralash. Bu algoritm orqali siz elementlarni h uzoqlikda saralangan qilasiz. Shu h-ning qiymati 1ga teng bo'lmagunicha uni kamaytiraverasiz. h uzoqlikda saralangan degani bir biridan h uzoqlikda joylashgan elementlarning har bir ro'yxatda saralangan holatda bo'lishi.
π§βπ» Algoritm π§βπ»
h = h * 3 + 1 -> bu Knuth-ning Interval ketma-ketliklar uchun formulasi.
1. Birinchi while loop berilgan massiv hajmi uchun to'g'ri h-ni topish uchun ishlatasiz.
2. Keyin esa nested loop ishlatasiz.
- Birinchi tashqi while loop-ni h-ning qiymatini formula bo'yicha kamaytirish uchun ishlatasiz.
- Ichki for loop-da esa Kiritish orqali saralash [Insertion sort] algoritmini h uzoqlikda joylashgan elementlar uchun ishlatasiz.
- Ichki while loop Kiritish orqali saralashga o'xshab, h uzoqlikda joylashgan elementlar uchun katta elementlarni o'nga suradi va tanlangan elementni o'z joyiga qo'yadi.
Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Geeksforgeeks
3. GIF
Rahmat!
Omad! βοΈπ
@LeetCodin